单选题
题解
初始化创建空队列时，令front=rear=0，每当插入新的队列尾元素时，rear增1，每当删除一个队列首元素时，front增1。因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
front ：0+2=2，
rear 4+2=6——>0.
函数题
6-1 另类循环队列 (20分)
如果用一个循环数组表示队列，并且只设队列头指针Front，不设尾指针Rear，而是另设Count记录队列中元素个数。请编写算法实现队列的入队和出队操作。
函数接口定义：
bool AddQ( Queue Q, ElementType X ); ElementType DeleteQ( Queue Q );
其中Queue结构定义如下：
typedef int Position; typedef struct QNode *PtrToQNode; struct QNode { ElementType *Data; /* 存储元素的数组 */ Position Front; /* 队列的头指针 */ int Count; /* 队列中元素个数 */ int MaxSize; /* 队列最大容量 */ }; typedef PtrToQNode Queue;
注意：如果队列已满，AddQ函数必须输出“Queue Full”并且返回false；如果队列是空的，则DeleteQ函数必须输出“Queue Empty”，并且返回ERROR。
输入样例：
4 Del Add 5 Add 4 Add 3 Del Del Add 2 Add 1 Add 0 Add 10 End
输出样例：
Queue Empty 5 is out 4 is out Queue Full 3 2 1 0
代码
#include <stdio.h> #include <stdlib.h> #define ERROR -1 typedef int ElementType; typedef enum { addq, delq, end } Operation; typedef enum { false, true } bool; typedef int Position; typedef struct QNode *PtrToQNode; struct QNode { ElementType *Data; /* 存储元素的数组 */ Position Front; /* 队列的头、尾指针 */ int Count; /* 队列中元素个数 */ int MaxSize; /* 队列最大容量 */ }; typedef PtrToQNode Queue; Queue CreateQueue( int MaxSize ) { Queue Q = (Queue)malloc(sizeof(struct QNode)); Q->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); Q->Front = 0; Q->Count = 0; Q->MaxSize = MaxSize; return Q; } bool AddQ( Queue Q, ElementType X ); ElementType DeleteQ( Queue Q ); Operation GetOp(); /* 裁判实现，细节不表 */ int main() { ElementType X; Queue Q; int N, done = 0; scanf("%d", &N); Q = CreateQueue(N); while ( !done ) { switch( GetOp() ) { case addq: scanf("%d", &X); AddQ(Q, X); break; case delq: X = DeleteQ(Q); if ( X!=ERROR ) printf("%d is out\n", X); break; case end: while (Q->Count) printf("%d ", DeleteQ(Q)); done = 1; break; } } return 0; } /* 你的代码将被嵌在这里 */ bool AddQ(Queue Q, ElementType X) { if (Q->MaxSize==Q->Count) { printf("Queue Full\n"); return ERROR; } ++Q->Count; Q->Data[(Q->Front + Q->Count) % Q->MaxSize] = X; return true; } ElementType DeleteQ(Queue Q) { if (Q->Count==0) { printf("Queue Empty\n"); return ERROR; } --Q->Count; Q->Front = (Q->Front + 1) % Q->MaxSize; return Q->Data[Q->Front]; }
6-2 双端队列 (25分)
双端队列（deque，即double-ended queue的缩写）是一种具有队列和栈性质的数据结构，即可以（也只能）在线性表的两端进行插入和删除。若以顺序存储方式实现双端队列，请编写例程实现下列操作：
Push(X,D)：将元素X插入到双端队列D的头；
Pop(D)：删除双端队列D的头元素，并返回；
Inject(X,D)：将元素X插入到双端队列D的尾部；
Eject(D)：删除双端队列D的尾部元素，并返回。
函数接口定义：
bool Push( ElementType X, Deque D ); ElementType Pop( Deque D ); bool Inject( ElementType X, Deque D ); ElementType Eject( Deque D );
其中Deque结构定义如下：
typedef int Position; typedef struct QNode *PtrToQNode; struct QNode { ElementType *Data; /* 存储元素的数组 */ Position Front, Rear; /* 队列的头、尾指针 */ int MaxSize; /* 队列最大容量 */ }; typedef PtrToQNode Deque;
注意：Push和Inject应该在正常执行完操作后返回true，或者在出现非正常情况时返回false。当Front和Rear相等时队列为空，Pop和Eject必须返回由裁判程序定义的ERROR。
输入样例：
3 Pop Inject 1 Pop Eject Push 2 Push 3 Eject Inject 4 Inject 5 Inject 6 Push 7 Pop End
输出样例：
Deque is Empty! 1 is out Deque is Empty! 2 is out Deque is Full! Deque is Full! 3 is out Inside Deque: 4 5
代码
#include <stdio.h> #include <stdlib.h> #define ERROR -1 typedef int ElementType; typedef enum { push, pop, inject, eject, end } Operation; typedef enum { false, true } bool; typedef int Position; typedef struct QNode *PtrToQNode; struct QNode { ElementType *Data; /* 存储元素的数组 */ Position Front, Rear; /* 队列的头、尾指针 */ int MaxSize; /* 队列最大容量 */ }; typedef PtrToQNode Deque; Deque CreateDeque( int MaxSize ) { /* 注意：为区分空队列和满队列，需要多开辟一个空间 */ Deque D = (Deque)malloc(sizeof(struct QNode)); MaxSize++; D->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); D->Front = D->Rear = 0; D->MaxSize = MaxSize; return D; } bool Push( ElementType X, Deque D ); ElementType Pop( Deque D ); bool Inject( ElementType X, Deque D ); ElementType Eject( Deque D ); Operation GetOp(); /* 裁判实现，细节不表 */ void PrintDeque( Deque D ); /* 裁判实现，细节不表 */ int main() { ElementType X; Deque D; int N, done = 0; scanf("%d", &N); D = CreateDeque(N); while (!done) { switch(GetOp()) { case push: scanf("%d", &X); if (!Push(X, D)) printf("Deque is Full!\n"); break; case pop: X = Pop(D); if ( X==ERROR ) printf("Deque is Empty!\n"); else printf("%d is out\n", X); break; case inject: scanf("%d", &X); if (!Inject(X, D)) printf("Deque is Full!\n"); break; case eject: X = Eject(D); if ( X==ERROR ) printf("Deque is Empty!\n"); else printf("%d is out\n", X); break; case end: PrintDeque(D); done = 1; break; } } return 0; } /* 你的代码将被嵌在这里 */ // 头插 bool Push(ElementType X, Deque D) { // 算尾部位置，如果满了返回false if ((D->Rear + 1) % (D->MaxSize) == D->Front) return false; // 减完了才能用公式 D->Front--; D->Front = (D->MaxSize + D->Front) % (D->MaxSize); D->Data[D->Front] = X; return true; } // 头删 ElementType Pop(Deque D) { if (D->Front == D->Rear) return ERROR; ElementType d = D->Data[D->Front]; D->Front++; D->Front = D->Front % (D->MaxSize); return d; } // 尾插 bool Inject(ElementType X, Deque D) { // 算尾部位置，如果满了返回false if ((D->Rear + 1) % (D->MaxSize) == D->Front) return false; D->Data[D->Rear] = X; D->Rear = (D->Rear + 1) % D->MaxSize; return true; } // 尾删 ElementType Eject(Deque D) { if (D->Front == D->Rear) return ERROR; if (!D->Rear) D->Rear = D->MaxSize; D->Rear--; ElementType d = D->Data[D->Rear]; return d; }
编程题
7-1 堆栈模拟队列 (25分)
设已知有两个堆栈S1和S2，请用这两个堆栈模拟出一个队列Q。
所谓用堆栈模拟队列，实际上就是通过调用堆栈的下列操作函数:
int IsFull(Stack S)：判断堆栈S是否已满，返回1或0；
int IsEmpty (Stack S )：判断堆栈S是否为空，返回1或0；
void Push(Stack S, ElementType item )：将元素item压入堆栈S；
ElementType Pop(Stack S )：删除并返回S的栈顶元素。
实现队列的操作，即入队void AddQ(ElementType item)和出队ElementType DeleteQ()。
输入格式:
输入首先给出两个正整数N1和N2，表示堆栈S1和S2的最大容量。随后给出一系列的队列操作：A item表示将item入列（这里假设item为整型数字）；D表示出队操作；T表示输入结束。
输出格式:
对输入中的每个D操作，输出相应出队的数字，或者错误信息ERROR:Empty。如果入队操作无法执行，也需要输出ERROR:Full。每个输出占1行。
输入样例:
3 2 A 1 A 2 A 3 A 4 A 5 D A 6 D A 7 D A 8 D D D D T
输出样例:
ERROR:Full 1 ERROR:Full 2 3 4 7 8 ERROR:Empty
代码
模拟队列
#include<stdio.h> #include<iostream> #include<stack> #include<string> using namespace std; stack<int>s1, s2; //定义两个栈 int n1, n2; //两个栈的容量 int main() { char c; int m, p, q; cin >> n1 >> n2; if (n1 > n2) swap(n1, n2); // 保证更大的容量的S2作为输出栈 getchar(); while (1) { // 无限循环输入 cin >> c; if (c == 'T') break; // 输入字符为T时结束 if (c == 'A') { cin >> m; if (s1.size() == n1 && s2.size() != 0) // 只有当s1为满，s2不为空时才是满的情况 printf("ERROR:Full\n"); else if (s1.size() == n1 && s2.size() == 0) { // 当s1为满，s2为空时，先将s1里面所有的元素转移到s2，再将新加入的元素放置s1 q = n1; while (q--) { p = s1.top(); s1.pop(); s2.push(p); } s1.push(m); } else if (s1.size() != n1) // 若s1不满，可直接将新入的元素放置s1里面 s1.push(m);; } if (c == 'D') { //输入字符为D时要出队 if (s1.size() == 0 && s2.size() == 0) //只有当s1,s2均为空时才为队空的情况 printf("ERROR:Empty\n"); else if (s1.size() != 0 && s2.size() == 0) { //若s2为空，s1不空，则先把s1里面所有元素转移至s2，再输出s2的栈顶元素 q = s1.size(); while (q--) { p = s1.top(); s1.pop(); s2.push(p); } cout << s2.top() << endl; s2.pop(); } else if (s2.size() != 0) { //如果s2不为空，可直接输出s2栈顶元素 cout << s2.top() << endl; s2.pop(); } } } return 0; }
直接用queue
#include<bits/stdc++.h> using namespace std; queue<int> q; int main() { int m,n,i,a; char c; cin>>m>>n; n+=m; for(i=0;;i++) { cin>>c; if(c=='T') return 0; if(c=='A') { cin>>a; if(q.size()==n) { cout<<"ERROR:Full"<<endl; } else { q.push(a); } } else if(c=='D') { if(q.size()==0) { cout<<"ERROR:Empty"<<endl; } else { cout<<q.front()<<endl; q.pop(); } } } return 0; }
