(1)栈、队列和线性表的异同。
(2)顺序栈的基本运算算法设计。
(3)链栈的基本运算算法设计。
(4)顺序队的基本运算算法设计。
(5)环形队列和非环形队列的特点。
(6)链队的基本运算算法设计。
(7)利用栈/队列求解复杂的应用问题。
1、栈的定义：后进先出表
2、栈的基本运算
（1）置空栈：s=NULL；
（2）判栈空：empty(s)；
（3) 入栈：push(s,x);
（4) 出栈：pop(s)；
（5) 读栈顶元素：top(s).
3、栈的存储结构
（1）顺序栈：即栈的顺序存储结构，是利用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设top指针指示栈顶元素在顺序栈中的位置。利用栈底位置相对不变的特性，两个顺序栈可以共享一个一维数据空间，以互补余缺。具体实现时可以将两个栈的栈底分别设在空间的两端，让它们的栈顶各自向中间延伸。
（2）链栈：可以克服顺序栈所带来的大量数据元素移动的不足。链栈中头指针就是栈顶指针。
4、栈的应用：表达式求值、括号匹配、递归调用，即将递归过程转变为非递归过程。
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int top; //栈指针
} SqStack; //顺序栈类型
void InitStack(SqStack *&s)
{
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
void DestroyStack(SqStack *&s)
{
free(s);
}
bool StackEmpty(SqStack *s)
{
return(s->top==-1);
}
bool Push(SqStack *&s,ElemType e)
{
if (s->top==MaxSize-1) //栈满的情况，即栈上溢出
return false;
s->top++;
s->data[s->top]=e;
return true;
}
bool Pop(SqStack *&s,ElemType &e)
{
if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top];
s->top--;
return true;
}
bool GetTop(SqStack *s,ElemType &e)
{
if (s->top==-1) //栈为空的情况，即栈下溢出
return false;
e=s->data[s->top];
return true;
#include <iostream>
using namespace std;
typedef char ElemType;
typedef struct linknode
{
ElemType data; //数据域
struct linknode *next; //指针域
} LinkStNode; //链栈类型
void InitStack(LinkStNode *&s)
{
s=(LinkStNode *)malloc(sizeof(LinkStNode));
s->next=NULL;
}
void DestroyStack(LinkStNode *&s)
{
LinkStNode *p=s->next;
while (p!=NULL)
{
free(s);
s=p;
p=p->next;
}
free(s); //s指向尾结点,释放其空间
}
bool StackEmpty(LinkStNode *s)
{
return(s->next==NULL);
}
void Push(LinkStNode *&s,ElemType e)
{ LinkStNode *p;
p=(LinkStNode *)malloc(sizeof(LinkStNode));
p->data=e; //新建元素e对应的结点p
p->next=s->next; //插入p结点作为开始结点
s->next=p;
}
bool Pop(LinkStNode *&s,ElemType &e)
{ LinkStNode *p;
if (s->next==NULL) //栈空的情况
{
return false;
}
p=s->next; //p指向开始结点
e=p->data;
s->next=p->next; //删除p结点
free(p); //释放p结点
return true;
}
bool GetTop(LinkStNode *s,ElemType &e)
{ if (s->next==NULL) //栈空的情况
{
return false;
}
e=s->next->data;
return true;
}
1、定义：先进先出表
2、队列的存储结构：
（1）顺序队列：设置两个指针：队头指针和队尾指针。
（2）链队列：增加一个头结点，令头指针指向头结点。
3、循环队列：
//非循环队列
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队头和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=-1;
}
void DestroyQueue(SqQueue *&q) //销毁队列
{
free(q);
}
bool QueueEmpty(SqQueue *q) //判断队列是否为空
{
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e) //进队
{
if (q->rear==MaxSize-1) //队满上溢出
{
return false;
}
q->rear++; //队尾增1
q->data[q->rear]=e; //rear位置插入元素e
return true; //返回真
}
bool deQueue(SqQueue *&q,ElemType &e) //出队
{
if (q->front==q->rear) //队空下溢出
{
return false;
}
q->front++;
e=q->data[q->front];
return true;
}
-----------------------------------------------------------
//循环队列
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct
{
ElemType data[MaxSize];
int front,rear; //队首和队尾指针
} SqQueue;
void InitQueue(SqQueue *&q)
{ q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
void DestroyQueue(SqQueue *&q)
{
free(q);
}
bool QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
bool enQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%MaxSize==q->front) //队满上溢出
{
return false;
}
q->rear=(q->rear+1)%MaxSize;
q->data[q->rear]=e;
return true;
}
bool deQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear) //队空下溢出
{
return false;
}
q->front=(q->front+1)%MaxSize;
e=q->data[q->front];
return true;
}
#include <iostream>
using namespace std;
typedef char ElemType;
typedef struct DataNode
{
ElemType data;
struct DataNode *next;
} DataNode; //链队数据结点类型
typedef struct
{
DataNode *front;
DataNode *rear;
} LinkQuNode; //链队类型
void InitQueue(LinkQuNode *&q)
{
q=(LinkQuNode *)malloc(sizeof(LinkQuNode));
q->front=q->rear=NULL;
}
void DestroyQueue(LinkQuNode *&q)
{
DataNode *p=q->front,*r;//p指向队头数据结点
if (p!=NULL) //释放数据结点占用空间
{ r=p->next;
while (r!=NULL)
{ free(p);
p=r;r=p->next;
}
}
free(p);
free(q); //释放链队结点占用空间
}
bool QueueEmpty(LinkQuNode *q)
{
return(q->rear==NULL);
}
void enQueue(LinkQuNode *&q,ElemType e)
{
DataNode *p;
p=(DataNode *)malloc(sizeof(DataNode));
p->data=e;
p->next=NULL;
if (q->rear==NULL) //若链队为空,则新结点是队首结点又是队尾结点
q->front=q->rear=p;
else
{ q->rear->next=p; //将p结点链到队尾,并将rear指向它
q->rear=p;
}
}
bool deQueue(LinkQuNode *&q,ElemType &e)
{
DataNode *t;
if (q->rear==NULL) //队列为空
return false;
t=q->front; //t指向第一个数据结点
if (q->front==q->rear) //队列中只有一个结点时
q->front=q->rear=NULL;
else //队列中有多个结点时
q->front=q->front->next;
e=t->data;
free(t);
return true;
}
（1）若让元素 1，2，3，4，5 依次进栈，则出栈次序不可能出现在（ ） 种情况。
A．5，4，3，2，1
B．2，1，5，4，3
C．4，3，1，2，5
D．2， 3，5，4，1
答案：C
解释：栈是后进先出的线性表，不难发现 C 选项中元素 1 比元素 2 先 出栈，违背了栈的后进先出原则，所以不可能出现 C 选项所示的情况。
（2）若已知一个栈的入栈序列是 1，2，3，…，n，其输出序列为 p1， p2，p3，…，pn，若 p1=n，则 pi 为（ ）。
A．i
B．n-i
C．n-i+1
D．不确定
答案：C
解释：栈是后进先出的线性表，一个栈的入栈序列是 1，2，3，…，n， 而输出序列的第一个元素为 n，说明 1，2，3，…，n 一次性全部进栈，再进行输出，所以 p1=n，p2=n-1，…，pi=n-i+1。
（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。
A ． r-f
B ． (n+f-r)%n
C ． n+r-f
D．（n+r-f)%n
答案：D
解释：对于非循环队列，尾指针和头指针的差值便是队列的长度，而对于循环队列，差值可能为负数，所以需要将差值加上 MAXSIZE（本题为 n）， 然后与 MAXSIZE（本题为 n）求余，即（n+r-f)%n。
（4）链式栈结点为：(data,link)，top 指向栈顶. 若想摘除栈顶结点，并将删除结点的值保存到 x 中，则应执行操作（ ）。
A．x=top->data;top=top->link；
B．top=top->link;x=top->link；
C．x=top;top=top->link；
D．x=top->link；
答案：A
解释：x=top->data 将结点的值保存到 x 中，top=top->link 栈顶指针指 向栈顶下一结点，即摘除栈顶结点。
（5）设有一个递归算法如下
int fact(int n) //n 大于等于 0
{
if(n<=0) return 1;
else return n*fact(n-1);
}
则计算 fact(n)需要调用该函数的次数为（ ）。
A． n+1
B． n-1
C． n
D． n+2
答案：A
解释：特殊值法。设 n=0，易知仅调用一次 fact(n)函数，故选 A。
（6）栈在 （ ）中有所应用。
A．递归调用
B．函数调用
C．表达式求值
D．前 三个选项都有
答案：D
解释：递归调用、函数调用、表达式求值均用到了栈的后进先出性质。
（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A．队列
B．栈
C．线性表
D．有序表
答案：A
解释：解决缓冲区问题应利用一种先进先出的线性表，而队列正是一种先进先出的线性表。
（8）设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5 和 e6 依次进入栈 S，一个元素出栈后即进入 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5 和 e1，则栈 S 的容量至少应该是（ ）。
A．2
B．3
C．4
D． 6
答案：B
解释：元素出队的序列是 e2、e4、e3、e6、e5 和 e1，可知元素入队的序列是 e2、e4、e3、e6、e5 和 e1，即元素出栈的序列也是 e2、e4、e3、e6、e5 和 e1，而元素 e1、e2、e3、e4、e5 和 e6 依次进入栈，易知栈 S 中最多同时存在 3 个元素，故栈 S 的容量至少为 3。
（9）若一个栈以向量 V[1…n]存储，初始栈顶指针 top 设为 n+1，则元素x 进栈的正确操作是( )。
A．top++; V[top]=x;
B．V[top]=x; top++;
C．top–; V[top]=x;
D．V[top]=x; top–;
答案：C
解释：初始栈顶指针 top 为 n+1，说明元素从数组向量的高端地址进栈，又因为元素存储在向量空间 V[1…n]中，所以进栈时 top 指针先下移变为 n，之后将元素 x 存储在 V[n]。
（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
A．线性表的顺序存储结构
B．队列
C. 线性表的链式存储结构
D. 栈
答案：D
解释：利用栈的后进先出原则。
（11）用链接方式存储的队列，在进行删除运算时（ ）。
A. 仅修改头指针
B. 仅修改尾指针
C. 头、尾指针都要修改
D. 头、尾指针可能都要修改
答案：D
解释：一般情况下只修改头指针，但是，当删除的是队列中最后一个元素时，队尾指针也丢失了，因此需对队尾指针重新赋值。
（12）循环队列存储在数组 A[0…m]中，则入队时的操作为（ ）。
A. rear=rear+1
B. rear=(rear+1)%(m-1)
C. rear=(rear+1)%m
D. rear=(rear+1)%(m+1)
答案：D
解释：数组 A[0…m]中共含有 m+1 个元素，故在求模运算时应除以 m+1。
（13）最大容量为 n 的循环队列，队尾指针是 rear，队头是 front，则队空的条件是（）。
A. (rear+1)%n==front
B. rear==front
C. rear+1==front
D. (rear-1)%n==front
答案：B
解释：最大容量为 n 的循环队列，队满条件是(rear+1)%n==front，队空条件是 rear==front。
（14）栈和队列的共同点是（ ）。
A. 都是先进先出
B. 都是先进后出
C. 只允许在端点处插入和删除元素
D. 没有共同点
答案：C
解释：栈只允许在栈顶处进行插入和删除元素，队列只允许在队尾插入元素和在队头删除元素。
（15）一个递归算法必须包括（ ）。
A. 递归部分
B. 终止条件和递归部分
C. 迭代部分
D. 终止条件和迭代部分
答案：B