队列 讲义实现
顺序队列
基本操作和顺序链表和顺序栈差不多,注意其有两个指针,头尾指针头出(删除元素)尾进(添加元素)
实现
#include <iostream>
using namespace std;
const int QUEUE_INIT_SIZE = 20;
const int OVERFLOW = 0;
const int ERROR = 0;
const int OK = 1;
const int EMPTY = 0;
typedef int Status;
template <class T>
class SqQueue
{
public:
SqQueue();
//~SqQueue();
Status EnQueue(T e);
Status DeQueue(T &e);
int QueueLength() const;
Status IsEmpty();
void DispQueue();
private:
T *base; //内存空间首地址
T *front; //头指针
T *rear; //尾指针
int queueSize; //队列的长度
};
//初始化顺序队列
template <class T>
SqQueue<T>::SqQueue()
{
base = new T[QUEUE_INIT_SIZE];
if(!base)
{
cerr << "存储分配失败!"<<endl;
}
front = rear = base; //注意此处的赋值顺序,将base赋值给front和rear
queueSize = QUEUE_INIT_SIZE;
}
template <class T>
SqQueue<T>::~SqQueue()
{
T *p = front;
while(p != rear)
{
p++;
delete front;
front = p;
}
}
//顺序入队
template <class T>
Status SqQueue<T>::EnQueue(T e)
{
if(rear-base >= queueSize)
{
return ERROR;
}
*rear++ = e; //先赋值,再加指针
return OK;
}
//顺序队列出队
template <class T>
Status SqQueue<T>::DeQueue(T &e)
{
if(rear == front)
{
return ERROR;
}
e = *front++; //先减指针,再取值
return OK;
}
template <class T>
int SqQueue<T>::QueueLength() const
{
return (rear-front);
}
template <class T>
Status SqQueue<T>::IsEmpty()
{
if(front == rear)
{
return EMPTY;
}
else
{
return !EMPTY;
}
}
template <class T>
void SqQueue<T>::DispQueue()
{
T *p = front;
while(p != rear)
{
cout << *p << " ";
p++;
}
cout<< endl;
}
int main()
{
SqQueue<int> queue1;
cout << "Enter a queue!~" <<endl;
for(int i=0; i<10; i++)
{
queue1.EnQueue(i);
}
queue1.DispQueue();
cout << "The length of the queue is " << queue1.QueueLength()<<endl;
int temp = 0;
cout << "The first five nodes are out of the queue, they are: ";
for(int i=0; i<5; i++)
{
queue1.DeQueue(temp);
cout << temp << " ";
}
cout << endl;
cout << "The rest of the queue are: ";
queue1.DispQueue();
cout << "Now, the length of the queue is " <<queue1.QueueLength()<<endl;
cout << "The queue is empty? "<<queue1.IsEmpty()<<endl;
for(int i=0; i<5; i++)
{
queue1.DeQueue(temp);
cout << temp << " ";
}
queue1.DispQueue();
cout << "The queue is empty? " << queue1.IsEmpty()<<endl;
return 0;
}
循环队列
#include <iostream>
using namespace std;
const int QUEUE_INIT_SIZE = 20;
const int OVERFLOW = 0;
const int ERROR = 0;
const int OK = 1;
const int EMPTY = 0;
typedef int Status;
template <class T>
class CircularQueue
{
public:
CircularQueue();
~CircularQueue();
Status EnQueue(T e);
Status DeQueue(T &e);
int QueueLength() const;
Status IsEmpty();
void DispQueue();
private:
T *base; //内存空间首地址
int front; //头指针
int rear; //尾指针
int queueSize; //队列的长度
};
template <class T>
CircularQueue<T>::CircularQueue()
{
base = new T[QUEUE_INIT_SIZE];
if(!base)
{
cerr << "存储分配错误!~"<<endl;
}
front = rear = 0;
queueSize = QUEUE_INIT_SIZE;
}
template <class T>
CircularQueue<T>::~CircularQueue()
{
delete[] base;
}
template <class T>
int CircularQueue<T>::QueueLength() const
{
//确保其为一个正数再取模
return (rear-front+QUEUE_INIT_SIZE) % QUEUE_INIT_SIZE;
}
template <class T>
void CircularQueue<T>::DispQueue()
{
int p = front;
while(p != rear)
{
cout<< base[p] << " ";
p = (p + 1) % QUEUE_INIT_SIZE;
}
cout << endl;
}
template <class T>
Status CircularQueue<T>::EnQueue(T e)
{
if((rear+1)%QUEUE_INIT_SIZE == front)
{
return ERROR;
}
base[rear] = e;
rear = (rear + 1) % QUEUE_INIT_SIZE;
return OK;
}
template <class T>
Status CircularQueue<T>::DeQueue(T &e)
{
if(rear == front)
{
return EMPTY;
}
e = base[front];
front = (front + 1) % QUEUE_INIT_SIZE;
return OK;
}
template <class T>
Status CircularQueue<T>::IsEmpty()
{
return (rear == front)?EMPTY:!EMPTY;
}
int main()
{
CircularQueue<int> queue1;
cout << "Enter a queue!~" <<endl;
for(int i=0; i<10; i++)
{
queue1.EnQueue(i);
}
queue1.DispQueue();
cout << "The length of the queue is " << queue1.QueueLength()<<endl;
int temp = 0;
cout << "The first five nodes are out of the queue, they are: ";
for(int i=0; i<5; i++)
{
queue1.DeQueue(temp);
cout << temp << " ";
}
cout << endl;
cout << "The rest of the queue are: ";
queue1.DispQueue();
cout << "Now, the length of the queue is " <<queue1.QueueLength()<<endl;
cout << "The queue is empty? "<<queue1.IsEmpty()<<endl;
for(int i=0; i<5; i++)
{
queue1.DeQueue(temp);
cout << temp << " ";
}
queue1.DispQueue();
cout << "The queue is empty? " << queue1.IsEmpty()<<endl;
return 0;
}
注意 成员函数操作数据成员时一定要避免修改数据成员。。。
链队列
#include <iostream>
using namespace std;
const int OVERFLOW = 0;
const int ERROR = 0;
const int OK = 1;
const int EMPTY = 0;
typedef int Status;
template <class T>
struct Node
{
T data;
Node<T> *next;
};
template <class T>
class LinkQueue
{
public:
LinkQueue();
~LinkQueue();
Status EnQueue(T e);
Status DeQueue(T &e);
int QueueLength();
Status IsEmpty();
void DispQueue();
private:
Node<T> *front;
Node<T> *rear;
};
template <class T>
LinkQueue<T>::LinkQueue()
{
front = new Node<T>;
front->next = NULL;
rear = front;
}
template <class T>
LinkQueue<T>::~LinkQueue()
{
Node<T> *p = front;
while(p != rear)
{
p = p->next;
delete front;
front = p;
}
delete rear;
}
template <class T>
Status LinkQueue<T>::EnQueue(T e)
{
Node<T> *p = new Node<T>;
if(!p)
{
return ERROR;
}
p->data = e;
p->next = NULL;
rear->next = p;
rear = p; //修改尾指针
return OK;
}
template <class T>
Status LinkQueue<T>::DeQueue(T &e)
{
Node<T> *p;
if(front == rear)
{
return ERROR;
}
p = front->next;
e = p->data;
front->next = p->next;
if(rear == p) //只有两个元素的情况,此时需要修改rear指针
{
rear = front;
}
delete p;
return OK;
}
template <class T>
int LinkQueue<T>::QueueLength()
{
int count = 0;
Node<T> *p = front;
while(p != rear)
{
++count;
p = p->next;
}
return count;
}
template <class T>
Status LinkQueue<T>::IsEmpty()
{
return (front == rear)?EMPTY:!EMPTY;
}
template <class T>
void LinkQueue<T>::DispQueue()
{
Node<T> *p = front->next;
while(p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout<<endl;
}
int main()
{
LinkQueue<int> queue1;
cout << "Enter a queue!~" <<endl;
for(int i=0; i<10; i++)
{
queue1.EnQueue(i);
}
queue1.DispQueue();
cout << "The length of the queue is " << queue1.QueueLength()<<endl;
int temp = 0;
cout << "The first five nodes are out of the queue, they are: ";
for(int i=0; i<5; i++)
{
queue1.DeQueue(temp);
cout << temp << " ";
}
cout << endl;
cout << "The rest of the queue are: ";
queue1.DispQueue();
cout << "Now, the length of the queue is " <<queue1.QueueLength()<<endl;
cout << "The queue is empty? "<<queue1.IsEmpty()<<endl;
for(int i=0; i<5; i++)
{
queue1.DeQueue(temp);
cout << temp << " ";
}
queue1.DispQueue();
cout << "The queue is empty? " << queue1.IsEmpty()<<endl;
return 0;
}
队列的应用
//队列报数的例子
char *number(int n)
{
char *result = new char;
int i=0;
int e = 0;
CircularQueue<int> q;
for(i=1; i<=n; i++)
{
q.EnQueue(i);
}
i = 0;
//一个出队
//接下来的一个先出队再进队
while(q.IsEmpty() != EMPTY)
{
q.DeQueue(e);
*(result + i++) = e+48; //将字符变为数字
if(q.IsEmpty() != EMPTY)
{
q.DeQueue(e);
q.EnQueue(e);
}
}
*(result + i) = '\0';
return result;
}