队列及其企业级应用
队列的故事导入
Jack 在一个著名软件外包公司上班，公司每年要接很多的外包项目给各个开发团队开发，现在刚 刚接到一个项目，要实现银行排队叫号系统, 基本需求是:
取号：
1. 银行用户进入银行大厅办理业务
2. 用户从自动排号机上取号
3. 自动取号机生成号码以及当前等待人数信息给用户
叫号:
1. 当银行业务员(1 位或多位)处理完业务以后，会指示叫号系统呼叫下一位（按排队次序）正在等待的用 户，用户达到窗口以后，银行业务员会将用户的号码从叫号系统中删除。
如果你是 Jack ,你该如何设计这个功能?
队列的原理精讲
队列是一种受限的线性表，(Queue)，它是一种运算受限的线性表,先进先出(FIFO First In First Out)
- 队列是一种受限的线性结构
- 它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。
生活中队列场景随处可见: 比如在电影院, 商场, 或者厕所排队。。。。。。
队列的算法实现
顺序存储
采用数组来保存队列的元素，设立一个队首指针 front ，一个队尾指针 rear，分别指向队首和队尾元素。则 rear-front 即为存储的元素个数！
#define MaxSize 5 //队列的最大容量 typedef int DataType; //队列中元素类型 typedef struct Queue { DataType queue[MaxSize]; int front; //队头指针 int rear; //队尾指针 }SeqQueue;
队列初始化：
//队列初始化，将队列初始化为空队列 void InitQueue(SeqQueue *SQ) { if(!SQ) return ; SQ->front = SQ->rear = 0; //把对头和队尾指针同时置0 }
队列为空：
//判断队列为空 int IsEmpty(SeqQueue *SQ) { if(!SQ) return 0; if (SQ->front == SQ->rear) { return 1; } return 0; }
队列为满：
//判断队列是否为满 int IsFull(SeqQueue *SQ) { if(!SQ) return 0; if (SQ->rear == MaxSize) { return 1; } return 0; }
入队：将新元素插入 rear 所指的位置，然后 rear 加 1。
//入队,将元素data插入到队列SQ中 int EnterQueue( SeqQueue *SQ,DataType data) { if(!SQ) return 0; if(IsFull(SQ)) { cout<<"无法插入元素 "<<data<<", 队列已满!"<<endl; return 0; } SQ->queue[SQ->rear] = data; //在队尾插入元素data SQ->rear++; //队尾指针后移一位 return 1; }
打印队列中的元素
//打印队列中的各元素 void PrintQueue(SeqQueue* SQ) { if(!SQ) return ; int i = SQ->front; while(i<SQ->rear) { cout<<setw(4)<<SQ->queue[i]; i++; } cout<<endl; }
1.删除 front 所指的元素, 后面所有元素前移 1 并返回被删除元素
//出队，将队列中队头的元素data出队，后面的元素向前移动 int DeleteQueue(SeqQueue* SQ, DataType *data) { if(!SQ || IsEmpty(SQ)) { cout<<"队列为空！"<<endl; return 0; } if(!data) return 0; *data = SQ->queue[SQ->front]; for(int i=SQ->front+1; i<SQ->rear; i++) {//移动后面的元素 SQ->queue[i-1]=SQ->queue[i]; } SQ->rear--;//队尾指针前移一位 return 1; }
2.删除 front 所指的元素，然后加 1 并返回被删元素
//出队，将队列中队头的元素data出队，出队后队头指针front后移一位 int DeleteQueue2(SeqQueue* SQ,DataType* data) { if (!SQ || IsEmpty(SQ)) { cout<<"队列为空！"<<endl; return 0; } if(SQ->front>=MaxSize) { cout<<"队列已到尽头!"<<endl; return 0; } *data = SQ->queue[SQ->front]; //出队元素值 SQ->front = (SQ->front)+1; //队首指针后移一位 return 1; }
#include <stdio.h> #include <assert.h> #include <Windows.h> #include <iostream> #include <iomanip> using namespace std; #define MaxSize 5 //队列的最大容量 typedef int DataType; //队列中元素类型 typedef struct Queue { DataType queue[MaxSize]; int front; //队头指针 int rear; //队尾指针 }SeqQueue;
取队首元素：返回 front 指向的元素值
//获取队首元素 int GetHead(SeqQueue* SQ,DataType* data) { if (!SQ || IsEmpty(SQ)) { cout<<"队列为空!"<<endl; } return *data = SQ->queue[SQ->front]; }
清空队列
//清空队列 void ClearQueue(SeqQueue* SQ) { SQ->front = SQ->rear = 0; }
完整代码实现：
//队列初始化，将队列初始化为空队列 void InitQueue(SeqQueue *SQ) { if(!SQ) return ; SQ->front = SQ->rear = 0; //把对头和队尾指针同时置0 } //判断队列为空 int IsEmpty(SeqQueue *SQ) { if(!SQ) return 0; if (SQ->front == SQ->rear) { return 1; } return 0; } //判断队列是否为满 int IsFull(SeqQueue *SQ) { if(!SQ) return 0; if (SQ->rear == MaxSize) { return 1; } return 0; } //入队,将元素data插入到队列SQ中 int EnterQueue( SeqQueue *SQ,DataType data) { if(!SQ) return 0; if(IsFull(SQ)) { cout<<"无法插入元素 "<<data<<", 队列已满!"<<endl; return 0; } SQ->queue[SQ->rear] = data; //在队尾插入元素data SQ->rear++; //队尾指针后移一位 return 1; } //出队，将队列中队头的元素data出队，后面的元素向前移动 int DeleteQueue(SeqQueue* SQ, DataType *data) { if(!SQ || IsEmpty(SQ)) { cout<<"队列为空！"<<endl; return 0; } if(!data) return 0; *data = SQ->queue[SQ->front]; for(int i=SQ->front+1; i<SQ->rear; i++) {//移动后面的元素 SQ->queue[i-1]=SQ->queue[i]; } SQ->rear--;//队尾指针前移一位 return 1; } //出队，将队列中队头的元素data出队，出队后队头指针front后移一位 int DeleteQueue2(SeqQueue* SQ,DataType* data) { if (!SQ || IsEmpty(SQ)) { cout<<"队列为空！"<<endl; return 0; } if(SQ->front>=MaxSize) { cout<<"队列已到尽头!"<<endl; return 0; } *data = SQ->queue[SQ->front]; //出队元素值 SQ->front = (SQ->front)+1; //队首指针后移一位 return 1; } //打印队列中的各元素 void PrintQueue(SeqQueue* SQ) { if(!SQ) return ; int i = SQ->front; while(i<SQ->rear) { cout<<setw(4)<<SQ->queue[i]; i++; } cout<<endl; } //获取队首元素，不出队 int GetHead(SeqQueue* SQ,DataType* data) { if (!SQ || IsEmpty(SQ)) { cout<<"队列为空!"<<endl; } return *data = SQ->queue[SQ->front]; } //清空队列 void ClearQueue(SeqQueue* SQ) { if(!SQ) return ; SQ->front = SQ->rear = 0; } //获取队列中元素的个数 int getLength(SeqQueue* SQ) { if(!SQ) return 0; return SQ->rear-SQ->front; } int main() { SeqQueue *SQ = new SeqQueue; DataType data = -1; //初始化队列 InitQueue(SQ); //入队 for(int i=0; i<7; i++) { EnterQueue(SQ, i); } //打印队列中的元素 printf("队列中的元素(总共%d 个)：", getLength(SQ)); PrintQueue(SQ); cout<<endl; //出队 //for(int i=0; i<10; i++) { if(DeleteQueue2(SQ, &data)) { cout<<"出队的元素是："<<data<<endl; } else { cout<<"出队失败！"<<endl; } //} //打印队列中的元素 printf("出队一个元素后，队列中剩下的元素："); PrintQueue(SQ); cout<<endl; system("pause"); return 0; }
下一小节将介绍队列的链式存储
