3、队列操作的代码实现
#include <iostream>
#define MAXN 5
using namespace std;
//队列
int queue[MAXN] = {0}; //头指针
int front = 0; //尾指针
int rear = 0;
//入队
void addqueue(int value){
if(rear >= MAXN){
cout<<"队满!"<<endl; }else{
queue[rear] = value; rear++;
}
}
//出队
int delqueue(){
int r;
if(front == rear){
cout<<"队空"<<endl;
r = -1;
}else{
r = queue[front];
front++;
}
return r; }
//显示队
void display(){
int i;
for(i = front;i < rear;i++){
cout<<queue[i]<<" "; } cout<<endl;
}
int main(){
int order;//口令 int value,t; cout<<"输入指令"<<endl; while(1 == 1){
cout<<"1入队,2出队,3显示！"<<endl; cin>>order; if(order == 1){
cin>>value;
addqueue(value);
display();
}else if(order == 2){
t = delqueue();
if(t != -1){
cout<<t<<"已经出队"<<endl; display();
}else{
cout<<"队列已空"<<endl; }
}else if(order == 3){
display();
}else{
cout<<"口令错误！"<<endl; }
} }
10 20 30
0 1 2 3 4
front=-1 rear=2
4、循环队列的使用
上述通过数组来实现队列的方法，如果进行插入一次，删除一次的操作，只要数组使用
过一遍数组就会被用光。当数组仿真队列的元素全部出队以后，队的首部就会出现需多空位
无法使用，导致空间浪费。
解决方法：
将线型数组模拟成环形数组。但无论在线型数组中还是环形数组中，都有一个问题：无
法判断队空还是队满；
因为队空的条件是：
front==rear;
队满的条件也是：
front==rear;
为了解决这个问题，我们在入队时少用一个数据元素空间。
这样，判断队满的方式为：(rear + 1) % MAXN == front。
判断队空的方式为：rear == front。
循环队列求队列元素个数：(rear-front+n)%n。
#include <iostream>
#define MAXN 5
using namespace std;
//队列
int queue[MAXN] = {0}; //头指针
int front = 0; //尾指针
int rear = 0;
//入队
void addqueue(int value){
//元素从未出队的情况下，队满
if(front == 0 && (rear + 1) % MAXN == front){
cout<<"队满"<<endl; //有元素出队，队满
}else if((rear + 1) % MAXN == front){
cout<<"队满"<<endl; }else{
queue[rear] = value;
rear = (rear + 1) % MAXN;
}
}
//出队
int delqueue(){
int r;
if(front == rear){
cout<<"队空"<<endl;
r = -1;
}else{
r = queue[front];
queue[front] = -1;//出队标记
front = (front + 1) % MAXN;
}
return r; }
//显示队
void display(){
if(front == rear){
cout<<"队空"<<endl;
}else{
int i = front;
do{
cout<<queue[i]<<" ";
i = (i + 1) % MAXN;
}while(i != rear);
}
cout<<endl;
}
int main(){
int order;//口令 int value,t; cout<<"输入指令"<<endl; while(1 == 1){
cout<<"1入队,2出队,3显示！"<<endl; cin>>order; if(order == 1){
cin>>value;
addqueue(value);
display();
}else if(order == 2){
t = delqueue();
if(t != -1){
cout<<t<<"已经出队"<<endl; display();
}else{
cout<<"队列已空"<<endl; }
}else if(order == 3){
display();
}else{
cout<<"口令错误！"<<endl; }
} }
【noip2012 普及组】2．（ ）是一种先进先出的线性表。
A．栈 B．队列 C．哈希表（散列表） D．二叉树
答案：B
【noip2011普及组】11．广度优先搜索时，需要用到的数据结构是（ ）。
A．链表 B．队列 C．栈 D．散列表
答案：B
2.5 栈练习题
1、若已知一个栈的入栈顺序是 1，2，3，…，n，其输出（出栈）序列为 P1，P2，P3，…，
Pn，若 P1 是 n，则 Pi 是( )。
A)i B)n-1 C)n-i+1 D)不确定
2、以下哪一个不是栈的基本运算( )。
A)删除栈顶元素 B)删除栈底的元素
C)判断栈是否为空 D)将栈置为空栈
3、设栈 S 的初始状态为空,现有 5 个元素组成的序列{1,2,3,4,5},对该序列在 S 栈上
依次进行如下操作(从序列中的 1 开始,出栈后不再进栈)：进栈,进栈,进栈,出栈,进栈,出
栈,进栈,问出栈的元素序列是:_________,栈中元素个数______，栈顶元素为:______。
4、已知元素（8，25，14，87，51，90，6，19，20），问这些元素以怎样的顺序进入栈，
才能使出栈的顺序满足：8 在 51 前面；90 在 87 的后面；20 在 14 的后面；25 在 6 的前面；
19 在 90 的后面。（ ）。
A 20，6，8，51，90，25，14，19，87
B 51，6，19，20，14，8，87，90，25
C 19，20，90，8，6，25，51，14，87
D 6，25，51，8，20，19，90，87，14
E 25，6，8，51，87，90，19，14，20
5、[多选]设栈 S 的初始状态为空，元素 a, b, c, d, e, f, g 依次入栈，以下出栈序
列不可能出现的有
（ ）。
A. a, b, c, e, d, f, g
B. b, c, a, f, e, g, d
C. a, e, c, b, d, f, g
D. d, c, f, e, b, a, g
E. g, e, f, d, c, b, a
6、某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口（出入同一口）。已
知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，
进，进，进，出,出”。假设车辆入站的顺序为 1，2，3，……，则车辆出站的顺序为（ ）。
A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6
D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5
7、设栈 S 的初始状态为空，元素 a, b, c, d, e 依次入栈，以下出栈序列不可能出现
的有（ ）。
A. a, b, c, e, d B. b, c, a, e, d
C. a, e, c, b, d D. d, c, e, b, a
8、设栈 S 的初始状态为空，元素 a，b，c，d，e，f 依次入栈 S，出栈的序列为 b，d，
c，f，e，a，则栈 S 的容量至少应该是（ ）。
A. 6 B. 5 C. 4 D. 3 E. 2
9、设有一顺序栈 S，元素 s1,s2,s3,s4,s5,s6 依次进栈，如果有 6 个元素出栈的顺序
是 s2,s3,s6,s5,s4,s1，则栈的容量至少是（ ）。
A、2 B、3 C、4 D、5
10、设有一顺序栈已含 3 个元素，如下图所示，元素 a4 正等待进栈。那么下列 4 个序
列中不可能出现的出栈序列是（ ）。
0 1 2 3
a1 a2 a3
top
A、a3,a1,a4,a2 B、a3,a2,a4,a1
C、a3,a4,a2,a1 D、a4,a3,a2,a1
11、若一个栈的输入序列为 1,2,3,….n，输出序列的第一个元素是 i，则第 j 个输出元
素是（ ）。
A、i – j – 1 B、i-j C、j-i+1 D、不确定
12、设一个站的输入序列是 1,2,3,4,5，则下列序列中，是栈的合法输出序列的是（ ）。
A、5,1,2,3,4 B、4,5,1,3,2 C、4,3,1,2,5 D、3,2,1,5,4
参考答案：
1.C 2.B 3.出栈序列为{3，4}，栈顶指针值为 3，栈顶元素为 5。 4.D 5.CE
6.C 7.C 8.D 9.C 10.A
11.D 12.D