void print(LinkQueue Q) { cout<<"打印链队列"<<endl; QNode *p=Q.front->next; while(p!=0) { cout<<p->data<<" "; p=p->next; } cout<<endl; }
int main(int argc, char* argv[]) { int b[7]={2,6,8,9,11,15,20}; LinkQueue Q; InitQueue(Q); for(int i=0;i<7;i++) EnQueue(Q,b[i]); print(Q); while(!Empty(Q)) { int e; GetTop(Q,e); cout<<e<<endl; DeQueue(Q,e); //print(Q); } cout<<endl;
int DeQueue(SqQueue &Q,QElemType &e) {//删除队头元素 if(Q.length==0)return 0; e=Q.base[Q.front];//返回值 Q.front=(Q.front+1)%Q.maxsize;//位置后移 Q.length--; return 1; } ///////// int GetHead(SqQueue Q,QElemType &e) {//得到队头元素 if(Q.length==0)return 0; e=Q.base[Q.front]; return 1; }
当length== MAXSIZE时，队列满。
具体实现如下： #include "stdafx.h" #include <iostream> using namespace std; typedef int QElemType; typedef struct { QElemType *base;//顺序队列所占空间 的首地址 int front;//队头位置 int rear;//队尾元素的下一个位置 int length;//队列中元素的个数 int maxsize;//队列的空间总数 }SqQueue;
J5 J6
用front指向队头元素，rear指向队尾元 素的下一个位置，用length指示队列中 有多少元素,用MAXSIZE指示线性空间 总的长度。
向队列尾部插入元素时， rear=(rear+1)% MAXSIZE;length++; 从队列头部删除元素时, front=(front+1)%MAXSIZE;length--;
void InitQueue(LinkQueue &Q) { Q.front=Q.rear=new QNode;//队列设立头结 点以便于操作 (Q.front)->next=0; } ///// int EnQueue(LinkQueue &Q,ElemType e) {//数据元素e入队 QNode *p=new QNode;//生成新结点 if(p==0)return 0; p->data=e; p->next=0; Q.rear->next=p;//将新结点插入到尾部 Q.rear=p; return 1; }
int GetTop(LinkQueue Q,ElemType &e) {//得到对头元素的值 if(Q.front==Q.rear )return 0; e=Q.front->next->data; return 1;
} /////// bool Empty(LinkQueue &Q) {//判断队列是否为空 if(Q.front==Q.rear )return true; return false; } ////////
int main(int argc, char* argv[]) { int b[5]={1,2,3,4,5}; SqQueue Q; InitQueue(Q,10); for(int i=0;i<5;i++) { EnQueue(Q,b[i]); print(Q); } for(;;) { if(Empty(Q))break; int e; DeQueue(Q,e); cout<<e<<" "; } return 0; }
return 0;
}
3.4.3 循环队列 这种方法是基于连续空间的。
循环队列演示
Q.front Q.reJ2 J3
Q.rear
Q.front Q.rear
J3 J4 J5 J6
Q.rear
Q.front
J3 J4 J5 J6
Q.rear
J7
J8
Q.front
int InitQueue(SqQueue &Q,int n) {//初始化队列 Q.base=new QElemType[n];//申请顺序空间 if(Q.base==0)return 0; Q.rear=Q.front=0; Q.length=0; Q.maxsize=n; return 1; } //////// int EnQueue(SqQueue &Q,QElemType e) {//元素入队 if(Q.length==Q.maxsize)return 0; Q.base[Q.rear]=e;//元素入队 Q.rear=(Q.rear+1)%Q.maxsize ;位置后移 Q.length++;//元素个数增加 return 1; }
3.4 队列 3.4.1 队列的定义及特点 队列是一种只允许在表的一端进行插入，在 另一端进行删除操作的线性表，因此具有先 进先出的特性。队列中允许进行插入的一端 称为队尾，允许删除的另一端称为队头，当 队列中没有元素时称为空队。 队列的基本操作有： 1、构造一个空的队列 2、在队尾部插入元素 3、在队头删除元素 4、得到队头元素 5、判断队列是否为空
bool Empty(SqQueue Q) {//判断队列是否为空 if(Q.length==0)return true; return false; } ///////// void print(SqQueue Q) { int k=Q.front; for(int i=1;i<=Q.length;i++) { cout<<Q.base[k]<<" "; k=(k+1)%Q.maxsize; } cout<<endl; }
3.4.2 链队列---队列的链式表示和实现 采用单链表的形式，为了操作方便，使用头结点，使用队头指针front、队尾指 针tail。 front指向链表的第一个元素，rear指向链表的最后一个元素。 具体实现如下： #include "stdafx.h" #include<iostream> using namespace std; typedef int ElemType ; typedef struct QNode { ElemType data;//数据域 QNode *next;//指针域 }QNode,*QueuePtr;//链式队列的结点 typedef struct { QueuePtr front;//指向队头的指针 QueuePtr rear;//指向队尾元素的指针 }LinkQueue;
3.4.4VC++中queue模板的使用
int DeQueue(LinkQueue &Q,ElemType &e) {//从队头删除元素 if(Q.front==Q.rear )return 0;//若队列为 空则不能删除 QNode *p=Q.front->next; Q.front->next=p->next; e=p->data; if(p==Q.rear)Q.rear=Q.front;//当队列中 只有一个元素时，要特别注意尾指针的指向 delete p; return 1; }