数据结构（C++）---队列

队列和栈一样，同样都是操作受限的线性表，不同于栈，队列只能从一边进，从另一边出（双端队列除外）。同样，队列有两种存储方式，以此可以分为顺序队和链队。具体的性质就不说了，本篇主要是用C++实现这两种队列。

一、循环队列

class SeqQueue { private: int * base; int front; //队头 int rear; //队尾 int size; //队大小 public: SeqQueue(int Queuesize=100) { base = new int[Queuesize]; //再堆中申请内存，并用base指针指向这块内存的首地址 front = 0; rear = 0; size = Queuesize; } ~SeqQueue() { delete[] base; } int Empty_Queue() //判空 { return (front == rear) } int En_Queue(int e) //入队 { if( (rear+1)%size!=front ) //判断循环队列有没有满 { rear = (rear+1)%size; base[rear] = e; return 1; } else return 0; } int De_Queue(int &e) //出队 { if(front != rear) //判断循环队列是否有元素 { front = (front+1)%size; e = base[front]; return 1; } else return 0; } int Front_Queue(int &e) //取队头元素 { if(front != rear) { e = base[(front+1)%size]; return 1; } else return 0; } };

二、链队列

class LinkQueue { private: QueueNode *front; //指向对头元素 QueueNode *rear; //指向队尾元素 public: LinkQueue() { front = NULL; rear = NULL; } ~LinkQueue() { QueueNode *p,*q; p = front; while(p) { q=p; p=p->next; delete q; } front = NULL; rear = NULL; } int Empty_Queue() //判空 { return (front==NULL&&rear==NULL); } int En_Queue(int e) //入队 { QueueNode *p=new QueueNode; if(p) //申请节点成功 { p->data=e; if(rear) //非空 { rear->next=p; } else //空 { front=rear=p; return 1; } } else return 0; } int De_Queue(int &e) //出队 { QueueNode *p; if(!Empty_Queue) { p = front; e = p->data; front = front->next; if(!front) //如果此时队为空，则队尾指针置为NULL { rear = NULL; delete p; } } int Front_Queue(int &e) //取对头元素 { if(!Empty_Queue()) { e=front->data; return 1; } else return 0; } } }