队列和循环队列

1. 线性表

1.1 基本概念

 线性表是最基本，最简单，最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其他数据元素均有唯一的前驱元素和后继元素。

1.2 基本特征

 线性表的特征如下：

集合中一定存在唯一的一个“第一个元素”集合中一定存在唯一的一个“最后元素”除最后一个元素外，其他元素均有唯一的后继元素除第一个元素外，其他元素均有唯一的前驱元素

2. 队列

2.1 基本概念

 队列(deque)是一种运算受限的线性表，他的两头都有运算限制，插入只能在表的一段进行（只进不出），而删除只能在表的另一端进行（只出不进）。允许插入的一段称为队尾(rear)，允许删除的一端称为队头(front)。队列的操作原则是先进先出，因而队列又称作FIFO表，队列一般具有两种物理结构：一种是顺序结构，一种是链式结构。

2.2 顺序队列的基本操作

队列类型的定义： #define MAXLEN 1000 struct SeqQueue{ int front,rear; //表示队头和队尾指针 int data[MAXLEN]; //存储数据的数组 }; 队列的初始化： void InitSeqQueue(Queue &q){ q.front = 0; //队头和队尾指针初始化 q.rear = 0; } 判断队列是否为空： bool IsEmpty(Queue &q){ return q.front == q.rear; } 判断队列是否满： bool IsFull(Queue &q){ return q.rear == MAXLEN; } 入队操作： bool Push(Queue &q,int dt){ if(IsFull) return false; //如果队列已满，则无法进行入队操作 q.data[rear++] = dt; return true; } 出队操作： void Pop(Queue &q){ q.front++; } 取队头元素： bool Get(Queue &q,int &dt){ if(IsEmpty(q)) return false; //如果队列为空，则无法进行取队头操作 dt = q.data[front]; //q.front++;去队首元素，不是删除 return true; }

2.3 循环队列

 循环队列(circular queue)是顺序队列的一个空间优化。顺序队列中元素是顺序存储表示的，用一组地址连续的存储单元一次存放从队头到队尾的元素，指针front和rear分别指示队头元素和队尾元素的位置。在有限的空间内，front和rear指针永远是增1的操作，一直到队列满时停止入队。但是，此时该空间并没有完全使用到，空间利用率不高。  解决方案：将顺序队列臆造为一个环状空间，形成循环队列。

1. 实现循环队列的方法如下：

队头、队尾指针加1，可用取模（余数）运算实现。队头指针进1：front = (front+1)%MAXLEN队尾指针进1：rear = (rear+1)%MAXLEN队列初始化：front = rear = 0队空条件：front == rear队满条件：(rear+1)%MAXLEN == front

2. 实现代码

循环队列的类型定义： #define MAXLEN 100 struct CycleQueue{ int front,rear; //队头和队尾的指针 int data[MAXLEN]; //存储数据的数组 }; 队列的初始化： void InitQueue(CycleQueue &q){ q.front = 0; q.rear = 0; } 队列的判空： bool IsEmpty(CycleQueue &q){ return q.front == q.rear; } 队列的判满： bool IsFull(CycleQueue &q){ return (q.rear+1)%MAXLEN == q.front; } 入队操作： bool Push(CycleQueue &q,int dt){ if(IsFull(q)) return false; q.data[q.rear] = dt; q.rear = (q.rear+1)%MAXLEN; return true; } 出队操作： bool Pop(CycleQueue &q){ if(IsEmpty(q)) return false; q.front = (q.front+1)%MAXLEN; return true; } 取队头元素： bool GetFront(CycleQueue &q,int &dt){ if(IsEmpty(q)) return false; dt = q.data[q.front]; return true; }

【例题：】士兵队列训练问题  某部队进行新兵队列训练，将新兵从头开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到2出列，剩下的向小序号方向靠拢，再从头开始进行一至三报数，凡报道三的出列，剩下的向小序号方向靠拢，继续从头开始进行一至二报数 … ,以后从头开始进行一至二报数，一至三报数，知道剩下的人不超过三人为止。输入的士兵人数不超过5000人。输入样例第一行为组数N，接下来N行是士兵数。输出剩下的士兵编号。

参考代码

#include <cstdio> #include <cstring> #include <algorithm> #define N 5002 using namespace std; struct Q{ int f,r; int data[N]; void Init(){ f = r = 0; } bool empty(){ return f == r; } bool IsFull(){ return r == N; } void Push(int dt){ if(IsFull()) exit(0); data[r++] = dt; } void Pop(){ if(empty()) exit(0); f++; } int Gettop(){ return data[f++]; } bool ch(){ return r-f < 4; } }q[2]; int main(){ int T,n,i; puts("input the number of test times:"); scanf("%d",&T); while(T--){ puts("input the number of soliders:"); scanf("%d",&n); q[0].Init(); q[1].Init(); for(i = 0;i<=n;i++){ q[0].Push(i); } int now = 0,pre = 1; //now表示当前存士兵的队列，pre表示另一个存士兵的队列 i = 0; while(!q[now].ch()) //用两个队列模拟报数过程 { q[pre].Init(); if(i & 1){ //根据i的奇偶性来表示当前的报数方式 while(!q[now].empty()){ q[pre].Push(q[now].Gettop()); if(q[now].empty()) break; q[pre].Push(q[now].Gettop()); if(q[now].empty()) break; q[now].Gettop(); } } else{ while(!q[now].empty()){ q[pre].Push(q[now].Gettop()); if(q[now].empty()) break; q[now].Gettop(); } } i ^= 1; swap(now,pre); //交换工作队列 } printf("%d\n",q[now].Gettop()); while(!q[now].empty()){ printf("%d\n",q[now].Gettop()); } puts(" "); } }