数据结构 3.32.链式队列 （青岛大学 周强）

 1 //链式队列
 2 #include<iostream>
 3 
 4 using namespace std;
 5 
 6 struct Node{
 7     int data;
 8     Node* next;//C++不用写struct Node *next,因为Node可以指代类型
 9     //构造函数
10     Node(int x){
11         data = x;
12         next = NULL;
13     }
14 }
15 
16 class Queue{
17     private://队首队尾的指针应该是私有的 不是公共的
18         Node* front;
19         Node* rear;
20     public:
21     //链表有两种 带“空头结点（不保存数据只有next起引导作用）” 和不带“空头结点的”（一开始就存放数据的）
22     //下面采用不带 空头结点 的链表
23         Queue(){
24             front = rear = NULL;
25         }
26         
27         ~Queue(){
28             Node* tmp;
29             while(front != NULL){
30                 tmp = front;
31                 front = front->next;
32                 delete tmp;
33             }
34         }
35 
36         bool isEmpty(){
37             return front == NULL;
38         }
39 
40         // bool isFull() 不考虑队满 因为是链式队列 内存有多少用多少...
41         //因为内存有多少用多少 不考虑用完的情况 所以enQueue返回类型用了void
42         void enQueue(int x){
43             /**谨记要考虑空队的情况 rear和front都指向这个元素*/
44             Node* tmp;
45             tmp = new Node(x);//上面有构造函数了 
46             if(isEmpty()){
47                 //调试语句 cout << "Empty" << tmp->data << endl;
48                 front = rear = tmp;
49             }
50             else{
51                  //调试语句 cout << "Not Empty" << tmp->data << endl;
52                 //在队尾挂一个点 不需要tmp->next =NULL了 因为构造函数里面写了
53                 rear->next = tmp;
54                 //记住新加入的元素要变成表尾
55                 rear = tmp;
56             }
57         }
58 
59         bool deQueue(int *px){
60             if(isEmpty()) return false;
61             else{
62                 //谨记考虑出队之后队伍为空的情况
63                 *px = front->data;
64                 //调试语句 cout << "*px" << *px << endl;
65                 Node * tmp;
66                 tmp = front;
67                 front = front->next;//表头指针往后移动 指向第二个点
68                 delete tmp;
69                 if(front == NULL) rear = NULL;//出队前就它一个元素 出队之后空了
70                 return true;
71             }
72         }
73 }
74 
75 int main(){
76     Queue q;
77     q.enQueue(11);
78     q.enQueue(22);
79     q.enQueue(33);
80     q.enQueue(44);
81     q.enQueue(55);
82     int x;
83     x = 0;
84     cout << q.deQueue(&x) << endl;
85     cout << x << endl;
86     return 0;
87 }

银行排队

 1 //银行排队 队列应用 模拟单队列排队
 2 用程序简单模拟一个单队列多窗口的排队模式：
 3 设某银行有一个固定能容纳N个顾客的等候区，顾客想进银行，若等候区有空则可进，否则被拒绝进入。
 4 每当银行柜员叫号时，等候区中最先进入的顾客离开等候区前往柜台办理业务，若叫号时等候区无人，则此次叫号作废。
 5 
 6 输入格式:
 7 第一行输入一个不大于20的正整数N，表示银行等候区能容纳的人数，
 8 接下来用若干行表示依时间顺序先后发生的“顾客想进银行”或“叫号”事件，格式分别是：
 9 
10 顾客想进银行，用 In <id> 表示，其中<id>是顾客编号，为不大于100000的正整数；
11 叫号，用Calling表示。
12 最后一行是一个#符号，表示输入结束。
13 注意：
14 
15 题目输入保证每个顾客的编号是独一无二的，即：不会出现想进银行的顾客与已经在等候区的顾客编号相同的情况。
16 保证后一个事件一定在前一个事件完成之后才发生，即：不需要考虑事件之间的“同步”问题。
17 输出格式:
18 对于输入的每个事件，按同样顺序在一行内输出事件的结果，格式分别是：
19 
20 顾客想进银行，若顾客进入，则输出 <id> joined. Total:<t> 其中<id>是该顾客的编号，<t>是顾客进入后，等候区的人数
21 顾客想进银行，若因等候区满而被拒绝，则输出 <id> rejected. 其中<id>是该顾客的编号
22 叫号，若有顾客前往柜台，则输出 <id> called. Total:<t> 其中<id>是该顾客的编号，<t>是顾客去柜台后，等候区的人数
23 叫号，等候区无人，则输出 No one!
24 输入样例:
25 3
26 In 101
27 In 102
28 In 103
29 In 104
30 Calling
31 In 105
32 Calling
33 Calling
34 Calling
35 Calling
36 #
37 输出样例:
38 101 joined. Total:1
39 102 joined. Total:2
40 103 joined. Total:3
41 104 rejected.
42 101 called. Total:2
43 105 joined. Total:3
44 102 called. Total:2
45 103 called. Total:1
46 105 called. Total:0
47 No one!
48 
49 #include<iostream>
50 #include<queue>
51 
52 using namespace std;
53 
54 int main(){
55     int N;
56     cin >> N;
57     queue<string> q;
58     string op, id;
59     cin >> op;
60     while(op != '#'){
61         if(op == "IN"){
62             cin >> id;
63             if(q.size() == N){
64                 cout << id << " rejected." << endl;
65             }
66             else{
67                 q.push(id);
68                 cout << id << " joined. Total:" << q.size() << endl;
69             }
70         }
71         else{
72             if(q.empty()){
73                 cout << "No one!" << endl;
74             }
75             else{
76                 id = q.front();
77                 q.pop();
78                 cout << id << " called. Total:" << q.size() << endl;
79             }
80         }
81         cin >> op;
82     }
83     return 0;
84 }