数据结构与算法学习之队列及队列的相关操作

队列也是一张表，它是一种插入操作在一端删除操作在另一端进行的表。队列的操作主要要抓住两个核心位置队头front和队尾rear。队列的主要操作就是入队与出队了。同样，队列也可以使用数组和链表两种方式实现。

下面是本人在学习队列操作时利用链表方式实现的代码：

/***************************************************************************//*********************队列的非顺序存储结构实现(链表实现)**********************//*********************Shanghai Jiaotong EE zhouguiyin***********************/#include <iostream>using namespace std;typedef int Elemtype;class Queueitem {public:Elemtype data; Queueitem *next;};class Queue {public:Queue(); //构造函数初始化一个带有头结点空队列~Queue();void Isempty();void Print();void Qinsert(Elemtype);Elemtype Qdelete();Elemtype Getfront();private:Queueitem *front; //队头指针Queueitem *rear; //队尾指针};Queue::Queue() {Queueitem *p = new Queueitem;p->next=NULL;front=rear=p;}Queue::~Queue() {Queueitem *sp = front->next;while(rear!=sp) {front->next=sp->next;delete sp;sp=front->next;}delete rear; //删除队尾节点delete front; //删除头节点rear=front=NULL;}void Queue::Isempty() {if (front==rear)cout<<"The queue is empty!"<<endl;elsecout<<"The queue is non-empty!"<<endl;}void Queue::Print() {Queueitem *iter = front->next;if (front==rear) cout<<"There is no element for printing!"<<endl;else {do {cout<<iter->data<<endl;iter=iter->next;}while(iter!=NULL);}}void Queue::Qinsert(Elemtype x) {Queueitem *p = new Queueitem;p->data=x;p->next=NULL;rear->next=p;rear=p;}Elemtype Queue::Qdelete() {Elemtype x;if (front==rear) cout<<"The queue is empty and can not delete!"<<endl;else {Queueitem *p = front->next;front->next=p->next;if(p->next==NULL) //重要！！当删除最后一个元素时，别把rear误删了 rear=front;x=p->data;delete p;}return x;}Elemtype Queue::Getfront() {if (front == rear) {cout<<"There is no element to get!"<<endl;return 0;}elsereturn front->next->data;}int main() {Queue q;q.Isempty();q.Qinsert(1);q.Qinsert(3);q.Qinsert(5);q.Qinsert(9);q.Isempty();q.Print();Elemtype x = q.Getfront();cout<<x<<endl;Elemtype y = q.Qdelete();cout<<y<<endl;Elemtype z = q.Qdelete();cout<<z<<endl;q.Print();}