队列有链式队列和数组循环队列
这里实现一个循环队列和其基本操做：出列，入列，下面的代码中把出列操作拿出的队首元素用指针来返回了，也可以实现一个函数来查看队首的元素
判断队满有两种方式：
1.使用front和rear的相对位置来确定
2.使用一个额外的size变量，更加简单
rear的两种初始化方法：
1.rear从0开始：指向队尾元素的下一个空位
2.从下标为capacity开始，指向队尾元素
这里我们使用第一种方法
代码：
1 //数组实现循环队列
2 #include<stdio.h>
3 #include<stdlib.h>
4 struct Queue {
5 int* data;//动态分配
6 int capacity;//容量
7 int front;//队首
8 int rear;//队尾
9 //判断队满的方式：可以使用front和rear的相对位置来确定，也可以使用一个size变量
10
11 };
12
13 //初始化
14 void init(struct Queue* pq, int capacity) {
15 pq->capacity = capacity;
16 pq->data = (int*)malloc(sizeof(int)*(capacity+1));
17 /*队尾rear是指向最后一个元素之后的位置，如果每个位置都放入一个元素，那rear最后的循环+1会==0，初始时rear==front也为0，这样就无法
18 判断队满还是队空，所以我们让这个数组永远填不满：填cpapcity个元素，
19 但是数组的容量为capacity+1，让rear最后指向最后一个元素后的空位则
20 ，当rear再循环+1就和front相同，就满了*/
21 /*rear从0开始：指向队尾元素的下一个空位
22 从下标为capacity-1开始，指向队尾元素*/
23 pq->front = pq->rear = 0;
24 }
25 //判断队满
26 int isFull(const struct Queue* pq) {/*如果初始化为0，每次入队是在rear的位置放入元素，然后rear+1*/
27 if ((pq->rear + 1) % (pq->capacity + 1) == pq->front)
28 //rear最后指向capacity+1的位置,也就是下标为capacity的位置，循环+1 = 0
29 {//可以用0-5（0-capacity）算一算：容量为6 = capacity+1
30 return 1;
31 }
32 else {
33 return 0;
34 }
35 }
36 //判断队空
37 int isEmpty(const struct Queue* pq) {
38 if (pq->rear == pq->front) {
39 return 1;
40 }
41 else {
42 return 0;
43 }
44 }
45 //入队
46 int enQueue(struct Queue* pq,int x) {
47 if (isFull(pq) ){
48 return 0;
49 }
50 else {
51 pq->data[pq->rear] = x;//在rear处添加元素
52 //循环+1
53 pq->rear = (pq->rear + 1) % (pq->capacity + 1);
54 return 1;
55 }
56 }
57 //出队
58 int deQueue(struct Queue* pq,int *px) {
59 if (isEmpty(pq)) {
60 return 0;
61 }
62 else {
63 *px = pq->data[pq->front];
64 pq->front = (pq->front + 1) % (pq->capacity + 1);
65 return 1;
66 }
67 }
68 int main()
69 {
70 struct Queue q;
71 init(&q, 5);//因为要修改queue的内容，所以传入q的地址和容量
72 enQueue(&q,11);
73 enQueue(&q, 22);
74 enQueue(&q, 33);
75 enQueue(&q, 44);
76 enQueue(&q, 55);
77 int x;
78 deQueue(&q, &x);
79 printf("%d\n", x);
80 }
栈的简单应用：
例-3 简单模拟单队列排队 (20分)
用程序简单模拟一个单队列多窗口的排队模式：
设某银行有一个固定能容纳N个顾客的等候区，顾客想进银行，若等候区有空则可进，否则被拒绝进入。
每当银行柜员叫号时，等候区中最先进入的顾客离开等候区前往柜台办理业务，若叫号时等候区无人，则此次叫号作废。
输入格式:
第一行输入一个不大于20的正整数N，表示银行等候区能容纳的人数，
接下来用若干行表示依时间顺序先后发生的“顾客想进银行”或“叫号”事件，格式分别是：
-
顾客想进银行，用In <id>表示，其中<id>是顾客编号，为不大于100000的正整数； -
叫号，用Calling表示。
最后一行是一个#符号，表示输入结束。
注意：
- 题目输入保证每个顾客的编号是独一无二的，即：不会出现想进银行的顾客与已经在等候区的顾客编号相同的情况。
- 保证后一个事件一定在前一个事件完成之后才发生，即：不需要考虑事件之间的“同步”问题。
输出格式:
对于输入的每个事件，按同样顺序在一行内输出事件的结果，格式分别是：
-
顾客想进银行，若顾客进入，则输出<id> joined. Total:<t>其中<id>是该顾客的编号，<t>是顾客进入后，等候区的人数 -
顾客想进银行，若因等候区满而被拒绝，则输出<id> rejected.其中<id>是该顾客的编号 -
叫号，若有顾客前往柜台，则输出<id> called. Total:<t>其中<id>是该顾客的编号，<t>是顾客去柜台后，等候区的人数 -
叫号，等候区无人，则输出No one!
输入样例:
3
In 101
In 102
In 103
In 104
Calling
In 105
Calling
Calling
Calling
Calling
#
输出样例:
101 joined. Total:1
102 joined. Total:2
103 joined. Total:3
104 rejected.
101 called. Total:2
105 joined. Total:3
102 called. Total:2
103 called. Total:1
105 called. Total:0
No one!
1 //例 - 3 简单模拟单队列排队(20分)
2 #include<iostream>
3 #include<string>
4 #include<queue>
5 using namespace std;
6 int main()
7 {
8 int n;
9 queue<string> q;
10 cin >> n;
11 string id, op;
12 while (cin >> op) {
13 if (op == "#") {
14 break;
15 }
16 else {
17 if (op == "In") {
18 cin >> id;
19 if (q.size() == n) {
20 cout << id << " rejected." << endl;
21 }
22 else {
23 q.push(id);
24 cout << id << " joined. Total:" << q.size() << endl;
25 }
26 }
27 if (op == "Calling") {
28 if (q.empty()) {
29 cout << "No one!" << endl;
30 }
31 else{
32 id = q.front();
33 q.pop();
34 cout << id << " called. Total:" << q.size() << endl;
35 }
36 }
37 }
38 }
39 return 0;
40 }