栈和队列是两种重要的线性结构。从数据结构角度看，栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。但从数据类型角度看，它们是和线性表不相同的两类重要的抽象数据类型。
栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶(top)，相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。
栈的修改是按后进先出的原则进行的，因此，栈又称为后进先出(Last In First Out, LIFO)的线性表。
栈与一般线性表的区别
栈与一般线性表的区别：仅存在运算规则不同。
| 一般线性表 | 栈 | |
|---|---|---|
| 逻辑结构 | 一对一 | 一对一 |
| 存储结构 | 顺序表、链表 | 顺序表、链表 |
| 运算规则 | 随机存取 | 后进先出(LIFO) |
队列(queue)是一种先进先出(First In First Out, FIFO)的线性表。它只允许在表的一端进行插入，而在另一端删除元素。
在队列中，允许插入的一端称为队尾(rear)，允许删除的一端则称为队头(front)。
-
假设表达式中允许包含两种括号：圆括号和方括号
-
其嵌套的顺序随意，即：
-
([ ] ( ))或[ ( [ ] [ ] ) ]为正确格式；
-
[ ( ] )为错误格式；
-
( [ () )或(()])为错误格式。
-
-
表达式求值是程序设计语言编译中一个最基本的问题，它的实现需要运用栈。
-
这里介绍的算法是由运算符优先级确定运算顺序的对表达式求值算法——算符优先算法。
-
表达式的组成
-
操作数(operand)：常数、变量。
-
运算符(operator)：算术运算符、关系运算符和逻辑运算符。
-
界限符(delimiter)：左右括弧和表达式结束符。
-
-
任何一个算术表达式都由操作数(常数、变量)、算术运算符(+、-、*、/)和界限符(括号、表达式结束符'#'、虚设的表达式起始符'#')组成。后两者统称为算符。
-
为了实现表达式求值。需要设置两个栈：
一个是算符栈OPTR，用于寄存运算符。
另一个称为操作数栈OPND，用于寄存运算数和运算结果。
-
求值的处理过程是自左至右扫描表达式的每一个字符
-
当扫描到的是运算数，则将其压入栈OPND，
-
当扫描到的是运算符时
-
若这个运算符比OPTR栈顶运算符的优先级高，则入栈OPTR，继续向后处理
-
若这个运算符比OPTR栈顶运算符优先级低，则从OPND栈中弹出两个运算数，从栈OPTR中弹出栈顶运算符进行运算，并将运算结果压入栈OPND。
-
-
继续处理当前字符，直到遇到结束符为止。
-
假设在舞会上，男士和女士各自排成一队。舞会开始时，依次从男队和女队的队买务出一人配成舞伴。如果两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。
显然，先入队的男士或女士先出队配成舞。因此该问题具有典型的先进先出特性，可以用队列作为算法的数据结构。
-
首先构造两个队列
-
依次将从男元素出队配成舞伴
-
某队为空，则另外一队等待着则是下一舞曲第一个可获得舞伴的人。
ADT Stack{
数据对象：
D = {ai | ai ∈ ElemSet, i = 1,2,...,n, n≥0}
数据关系：
R1 = {<ai-1, ai> | ai-1, ai∈D, i = 1,2,...,n}
约定an端为栈顶，a1端为栈底
基本操作：
初始化、进栈、出栈、取栈顶元素等
}ADT Stack
存储方式：同一般线性表的顺序存储结构完全相同，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。栈底一般在低地址端。
-
附设top指针，指示栈顶元素在顺序栈中的位置。
-
另设base指针，指示栈底元素在顺序栈中的位置。
-
用stacksize表示栈可使用的最大容量。
但是，为了方便操作，通常top指示真正的栈顶元素之上的下标地址。
空栈：base == top是栈空标志
栈满：top - base == stacksize
-
栈满时的处理方法：
-
报错，返回操作系统
-
分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈
-
使用数组作为顺序栈存储方式的特点：简单、方便、但易产生溢出（数组大小固定）
-
上溢(overflow)：栈已经满，又要压入元素
-
下溢(underflow)：栈已经空，还要弹出元素
注：上溢是一种错误，使问题的处理无法进行；而下溢一般认为是一种结束条件，即问题处理结束。
顺序栈的表示
#define MAXSIZE 100
struct SqStack{
SElemType *base; // 栈底指针
SElemType *top; // 栈顶指针
int stacksize; // 栈可用最大容量
};算法3.1 顺序栈的初始化
// 构造一个空栈
State InitStack(SqStack &S){
S.base = new SElemType[MAXSIZE];
if(!S.base) exit(OVERFLOW); // 存储分配失败
S.top = S.base; // 栈顶指针等于栈底指针
S.stacksize = MAXSIZE;
return OK;
}补充算法1 判断顺序栈是否为空
// 若栈为空，返回TRUE；否则返回FALSE
State StackEmpty(SqStack &S){
if(S.top == S.base)
return TRUE;
else
return FALSE;
}补充算法2 求顺序栈的长度
int StackLength(SqStack S)
{
return S.top - S.base;
}补充算法3 清空顺序栈
Status ClearStack(SqStack &S){
if(S.base) S.top = S.base;
return OK;
}补充算法4 销毁顺序栈
Status DestoryStack(SqStack &S){
if(S.base){
delete S.base;
S.stacksize = 0;
S.base = S.top = NULL;
}
return OK;
}算法3.2 顺序栈的入栈
-
步骤：
-
判断是否栈满，若满则出错
-
元素e压入栈顶
-
栈顶指针加1
-
Status Push(SqStack &S, SElemType e){
if(S.top - S.base == S.stacksize) // 栈满
return ERROR;
*S.top = e;
S.top++;
// 等同于
// *S.top++ = e;
return OK;
}算法3.3 顺序栈的出栈
-
步骤：
-
判断是否栈空，若空则出错
-
获取栈顶元素e
-
栈顶指针减1
-
Status Pop(SqStack &S, SElemType &e){
if(S.top == S.base) return ERROR;
S.top--;
e = *S.top;
// 等同于
e = *--S.top;
return OK;
}链栈是运算受限的单链表，只能在链表头部进行操作。定义链栈的结构类型：
struct StackNode{
SElemType data;
StackNode *next;
};
typedef StackNode *LinkStack;-
链表的头指针就是栈顶
-
不需要头结点
-
基本不存在栈满的情况
-
空栈相当于，栈指针指向空
-
插入和删除仅在栈顶处执行
算法3.5 链栈的初始化
void InitStack(LinkStack &S){
// 构造一个空栈，栈顶指针置为空
S = NULL;
return OK;
}补充算法1 判断链栈是否位空
Status StackEmpty(LinkList S){
if(S == NULL) return TRUE;
else return FALSE;
}算法3.6 链栈的入栈
Status Push(LinkStack &S, SElemType e){
p = new StackNode; // 生成新结点p
p->data = e; // 将新结点数据域置为e
p->next = S; // 将新结点插入栈顶
S = p; // 修改栈顶指针
return OK;
}算法3.7 链栈的出栈
Status Pop(LinkStack &S, SElemType &e){
if(S == NULL) return ERROR;
e = S->data;
p = S;
S = S->next;
delete p;
return OK;
}算法3.8 取栈顶的元素
SElemType GetTop(LinkStack S){
if(S != NULL){
return S->data;
}
}-
递归的定义
-
若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归的；
-
若一个过程直接地或间接地调用自己，则称这个过程是递归的过程。
-
-
常用到递归方法的三种情况：
-
递归定义的数学函数
-
具有递归特性的数据结构
-
二叉树
-
广义表
-
-
可递归求解的问题
-
迷宫问题
-
汉诺塔问题
-
-
-
递归问题——用分治法求解
-
分治法：对于一个较为复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
-
必备的三个条件
-
能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，且这些处理对象是变化有规律的
-
可以通过上述转换而使得问题简化
-
必须有一个明确的递归出口，或称递归边界
-
-
分治法求解递归问题算法的一般形式
void p(参数表){ // 基本项 if(递归结束条件) 可直接求解步骤; // 递归边界 // 归纳项 else p(较小的参数); }
-
-
递归的优缺点
-
优点：结构清晰，程序易读
-
缺点：每次调用要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息。时间开销大。
-
-
实现递归转非递归
-
方法1：尾递归、单向递归变为循环结构
-
方法2：自用栈模拟系统的运行时栈
-
-
队列描述
-
队列(Queue)是仅在表尾进行插入操作，在表头进行删除操作的线性表。
-
表尾即an端，称为队尾；表头即a1端，称为队头；
-
它是一种先进先出(FIFO)的线性表
-
队列的物理存储可以用顺序存储结构，也可用链式存储结构。相应地队列的存储方式也分为两种，即顺序队列和链式队列。
队列的顺序表示——用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 // 最大队列长度
typedef struct{
QElemType *base; // 初始化的动态分配存储空间
int front; // 头指针，即队头下标
int rear; // 尾指针
}SqQueue;顺序队列存在的问题
顺序队列的真溢出问题：即front=0，rear=MAXQSIZE时，队列中存满，为真溢出；
而当入队、出队操作之后，随着front和rear移动，出现front!=0，rear=MAXQSIZE时，为假溢出。
顺序队列假上溢解决办法
-
解决假上溢的方法
-
将队中元素依次向队头方向移动。缺点：浪费时间。每移动一次，队中元素都要移动。
-
将队空间设想成一个循环的表，即分配给队列的m个存储单元可以循环使用，当rear为maxqsize时，若向量的开始端空着，又可从头使用空着的空间。当front为maxqsize时，也是一样。
-
-
引入循环队列——解决假上溢的问题
base[0]接在base[MAXQSIZE-1]之后，若rear+1==M，则rear=0；实现方法：利用模运算(mod, %)
插入元素：(尾指针后移一位)
Q.base[Q.rear] = x; Q.rear = (Q.rear+1) % MAXQSIZE;删除元素：(头指针后移一位)
x = Q.base[Q.front]; Q.front = (Q.front + 1) % MAXQSIZE;针对循环队列，判断队空、对满时，front都与rear相等，因此可解决的方案有：
-
另外设一个标态以区别队空和队满
-
另设一个变量，记录元素个数
-
少用一个能素空间
-
-
循环队列解决队满时判断方法——少用一个元素空间
队空时：front == rear
队满时：(rear+1)% MAXQSIZE == front;
循环队列的类型定义
#define MAXQSIZE 100 // 最大队列长度
typedef struct{
QElemType *base; // 初始化的动态分配存储空间
int front; // 头指针，若队列不为空，指向队列头元素
int rear; // 尾指针，若队列不为空，指向队尾元素的下一个位置
}SqQueue;循环队列的操作——队列的初始化(算法3.11)
Status InitQueue(SqQueue &Q){
Q.base = new QElemType[MAXQSIZE];
if(!Q.base) exit(OVERFLOW); // 存储分配失败
Q.front = Q.rear = 0;
return OK;
}循环队列的操作——求队列的长度(算法3.12)
int QueueLength(SqQueue Q){
return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
}循环队列的操作——循环队列入队(算法3.13)
Status EnQueue(SqQueue &Q, QElemType e){
if((Q.rear + 1) % MAXQSIZE == Q.front) return ERROR; // 队满
Q.base[Q.rear] = e; // 新元素加入队尾
Q.rear = (Q.rear + 1) % MAXQSIZE; // 队尾指针+1
return OK;
}循环队列的操作——循环队列出队(算法3.14)
Status DeQueue(SqQueue &Q, QElemType &e){
if(Q.rear == Q.front) return ERROR; // 队空
e = Q.base[Q.front]; // 保存队头元素
Q.front = (Q.front + 1) % MAXQSIZE; // 队头指针+1
return OK;
}循环队列的操作——取循环队列队头元素(算法3.15)
QElemType GetHead(SqQueue Q){
if(Q.rear != Q.front){ // 不为空
return Q.base[Q.front]; // 返回队头指针元素的值，队头指针不变
}
}若用户无法估计所用队列的长度，则宜采用链队列。
链式队列的类型定义
#define MAXQSIZE 100 // 最大队列长度
struct Qnode{
QElemType data;
Qnode *next;
};
typedef Qnode *QueuePtr;
struct LinkQueue{
QueuePtr front; // 队头指针
QueuePtr rear; // 队尾指针
};链队列的操作——链队列的初始化(算法3.16)
Status InitQueue(LinkQueue &Q){
Q.front = new QueuePtr();
Q.rear = new QueuePtr();
Q.front->next = NULL;
return OK;
}链队列的操作——销毁链队列(补充)
Status DestoryQueue(LinkQueue &Q){
while(Q.front){
p = Q.front->next;
delete (Q.front);
Q.front = p;
}
return OK;
}链队列的操作——将元素e入队(算法3.17)
Status EnQueue(LinkQueue &Q, QElemType e){
p = new QueuePtr;
if(!p) exit(OVERFLOW); // 存储分配失败
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}链队列的操作——链队列的出队(算法3.18)
Status DeQueue(LinkQueue &Q, QElemType &e){
if(Q.front == Q.rear) return ERROR; // 队空
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if(Q.rear == p) Q.rear = Q.front;
delete p;
return OK;
}链队列的操作——求链队列的队头元素(算法3.19)
Status GetHead(LinkQueue &Q, QElemType &e){
if(Q.front == Q.rear) return ERROR;
e = Q.front->next->data;
return OK;
}选择题
-
设栈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
-
若一个栈以向量
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]。
算法设计题
-
将编号为0和1的两个栈存放于一个数组空间
V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长(见图)。试编写双栈初始化，判断栈空、栈满、进栈和出栈等算法的函数。双栈数据结构的定义如下：struct DblStack{ int top[2], bot[2]; // 栈顶和栈底指针 SElemType* V; // 栈数组 int m; // 栈最大可容纳元素个数 };
-
回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符序列是否为回文。（提示：将一半字符入栈）
-
设从键盘输入一整数的序列：a1, a2, a3,..., an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai = -1时，输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。
-
从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以"$"作为输入结束，操作数之间用空格分隔，操作符只可能有+、-、、／四种运算。例如： 23434 + 2$。
-
假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
- 下面所示的序列中哪些是合法的？
A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO
- 通过对上述的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false(假定被判定的操作序列已存入一维数组中)。
-
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意：不设头指针），试编写相应的置空队列、判断队列是否为空、入队和出队等算法。
-
假设以数组
Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dequeue)算法。 -
如果允许在循环队列的两端都可以进行插入和删除操作。要求：
-
写出循环队列的类型定义；
-
写出“从队尾删除”和“从队头插入”的算法。
-
-
已知Ackermann函数定义如下：Ack(m, n) =
-
n + 1, 当m = 0时
-
Ack(m-1, 1), 当m≠0, n=0时
-
Ack(m-1, Ack(m, n-1)), 当m≠0, n≠0时
-
写出计算Ack(m, n)的递归算法，并根据此算法给出Ack(2, 1)的计算过程。
-
写出计算Ack(m,n)的非递归算法。
-
-
已知f为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法：
-
求链表中的最大整数；
-
求链表的结点个数；
-
求所有整数的平均值。
-
