1. Definiation
What is a queue?
A queue is a list. With a queue, inseration is done at one end (known as rear) whereas deletion is performed at the other end (known as front).
2. Operations
指针对列
无法自定义队长
// array queue
#include<iostream>
using namespace std;struct Node
{int data;
};class Queue
{
public://初始化Queue(){front = -1;rear = -1;}//判断是否为空bool isEmpty(){if (rear == front)return true;return false;}//判队满bool isFull(){if (rear - front == 10)return true;return false;}//入队列void EnQueue(int item){if (!isFull()){rear += 1;node[rear].data = item;}else{cout << "Full" << endl;}}//出队列void DiQueue(){if (!isEmpty()){front += 1;}else{cout << "Empty" << endl;}}//取队头int GetHead(){if (!isEmpty()){int temp = node[front+1].data;return temp;}else{cout << "Empty" << endl;return 0;}}//得队长int GetSize(){return rear - front;}private:int front; //队头指针总是指向队头元素的前一个位置int rear;Node node[10];
};
可自定义队长
//自己动手写queue
//array queue
template<typename Object>
struct Node
{Object data;
};template<typename Object>
class Queue
{
public://初始化Queue(int m){init(m);}Queue&operator=(Queue&q){if (this == &q)return *this;clear();for (int i = 0; i < q.curSize; i++)this->EnQueue(q.list[i].data);return *this;}Queue(Queue&q){init(q.maxsize);*this = q;}//删除队列~Queue(){delete list;}//判断是否为空bool isEmpty(){if (curSize == 0)return true;return false;}//判队满bool isFull(){if (curSize == maxsize)return true;return false;}//入队列void EnQueue(int item){if (!isFull()){rear += 1;list[rear].data = item;curSize++;}else{cout << "Full" << endl;}}//出队列void DiQueue(){if (!isEmpty()){front += 1;curSize--;}else{cout << "Empty" << endl;}}//取队头int GetHead(){if (!isEmpty()){int temp = list[front + 1].data;return temp;}else{cout << "Empty" << endl;return 0;}}//得队长int GetSize(){return curSize;}//清空队列void clear(){for (int i = 0; i<curSize; i++){if (isEmpty()){return;}else{rear--;}}curSize = 0;}private:int front;int rear;int maxsize;int curSize;Node<Object>* list;void init(int m){front = -1;rear = -1;maxsize = m;curSize = 0;list = new Node<Object>[maxsize];}
};
一般的数组队列会出现假溢出的问题，为了解决这个问题，我们可以利用循环队列
需要注意的是，你设计的队列大小与实际可以用到的队列大小是不一样的，总是-1
// circular queue
#include<iostream>
using namespace std;struct Node
{int data;
};class CirQueue
{
public://初始化CirQueue(){rear = 3;front = 3;}//判空bool isEmpty(){if (front == rear)return true;return false;}//判满，牺牲队列的一个空间来判满bool isFull(){if ((rear + 1) % 4 == front)return true;return false;}//入队void EnQueue(int item){if (!isFull()){rear = (rear + 1) % 4;node[rear].data = item;}else{cout << "Full" << endl;}}//出队void DiQueue(){if (!isEmpty()){front = (front + 1) % 4;}else{cout << "Empty" << endl;}}//取队头int GetHead(){if (!isEmpty()){return node[(front+1)%4].data;}else return -1;}
private:int front;int rear;Node node[4];
};
其实不用游标来判断队空与队满就不用牺牲一个空间了
//自己动手写queue
//circular queue
template<typename Object>
struct Node
{Object data;Node(const Object &d = Object()) :data(d){}
};template<typename Object>
class CircularQueue
{
public://the big threeCircularQueue(int m){init(m);}CircularQueue(CircularQueue& cq){init(cq.maxSize);*this = cq;}~CircularQueue(){delete[] node;}CircularQueue& operator=(CircularQueue &cq){if (this == &cq)return *this;clear();for (int i = 0; i<cq.curSize; i++)this->EnQueue(cq.node[i].data);return *this;}//判空bool isEmpty(){return curSize == 0;}//判满bool isFull(){return curSize == maxSize;}//入队void EnQueue(Object item){if (!isFull()){curSize++;}rear = (rear + 1) % maxSize;node[rear].data = item;}//出队void DIQueue(){if (!isEmpty()){head = (head + 1) % maxSize;curSize--;}}//取队头Object GetHead(){return node[(head + 1) % maxSize].data;}//得队长int GetSize(){return curSize;}//清空队列void clear(){head = maxSize - 1;rear = maxSize - 1;curSize = 0;}private:int head;int rear;int maxSize;int curSize;Node<Object>*node;void init(int m){head = m - 1;rear = m - 1;maxSize = m;curSize = 0;node = new Node<Object>[maxSize];}
};
链表队列
就无什么假溢出的问题了
template<typename Type>
struct Node
{Type data;Node*next;Node*prev;Node(const Type& d = Type(), Node*p = NULL, Node *n = NULL) :data(d), prev(p), next(n){}
};template<typename Type>
class Queue
{
public:Queue(){init();}Queue(Queue& q){init();*this = q;}~Queue(){clear();delete head;delete tail;}const Queue& operator= (const Queue& q){if (this == &q)return *this;clear();Node<Type>*p = q.head->next;while (p->next != q.tail){this.EnQueue(p->data);p = p->next;}return *this;*/}bool IsEmpty(){return size == 0;}void EnQueue(Type item){Node<Type>*p = new Node<Type>;p->data = item;p->prev = tail->prev;tail->prev->next = p;tail->prev = p;p->next = tail;size++;}void DIQueue(){if (!IsEmpty()){Node<Type>*p = head->next;head->next = p->next;p->next->prev = head;delete p;size--;}}Type GetHead(){return (head->next->data);}void clear(){while (head->next != tail){DIQueue();}size = 0;}int GetSize(){return size;}private:Node<Type>*tail;Node<Type>*head;int size;void init(){head = new Node<Type>;tail = new Node<Type>;head->next = tail;tail->prev = head;size = 0;}
};
