栈与队列
将栈和队列相关的知识点、代码实现和算法应用整理如下。
目录
栈和队列
栈
栈（Stack）是一种仅在表末进行插入和删除的线性表。对栈来说，表尾称为栈顶，表头称为栈底。不包含元素的空表称为空栈。
栈的ADT
//栈的ADT
ADT Stack{
数据对象：D={ai|ai ∈ Elemset , i=1,2,3...n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3...n}，约定an为为栈顶，a1为栈底
基本操作：
InitStack(&S)
操作结果：构造一个空的栈。
DestroyStack(&S)
初始条件：栈S已存在。
操作结果：销毁栈S的存储空间。
ClearStack(&S)
初始条件：栈S已存在。
操作结果：将S重置为空栈。
IsEmpty(S)
初始条件：栈S已存在。
操作结果：若S为空栈，返回True，否则返回false。
IsFull(S)
初始条件：栈S已存在。
操作结果：若S已满，返回True，否则返回false。
StackLength(S)
初始条件：栈S已存在。
操作结果：返回S中已经存放数据元素的个数。
GetTop(S,&e)
初始条件：栈S已存在。
操作结果：用e返回栈顶数据元素。
Push(&S,e)
初始条件：栈S已存在。
操作结果：将元素e压入栈中，成功则返回true，如果栈满打印错误信息并返回false。
Pop(&S,&e)
初始条件：栈S已存在。
操作结果：将栈顶元素出栈并赋值给e，成功则返回true，如果栈空打印错误信息并返回false。
StackTraverse(S)
初始条件：栈S已存在。
操作结果：从栈底到栈顶依次输出栈中的数据元素。
}
栈的表示和实现
这里对栈的实现使用顺序结构进行实现。
//栈的定义
#define MAXSIZE 100 //栈所能容纳的最多元素个数
using namespace std;
typedef int Elem; //栈内元素类型
typedef struct SqStack{
Elem *base; //栈底指针，指向分配的连续的数组空间
Elem *top; //栈顶指针，指向栈顶元素的后一个位置
int size; //栈的大小
}SqStack;
//元素的打印函数，用于输出Elem，对数据元素的访问进行封装
void PrintData(Elem x){
printf("%d",x);
}
栈的常用函数实现
//初始化栈，分配栈空间，并初始化栈顶指针
bool InitStack(SqStack &S){ //分配MAXSIZE+1个空间，栈顶指针指向栈顶元素的后一个位置
S.base=(Elem*)malloc(sizeof(Elem)*(MAXSIZE+1));
if(S.base==NULL) return false; //如果分配空间失败
S.top=S.base; //初始化栈顶指针
S.size=MAXSIZE;
return true;
}
//销毁栈，释放栈所占有的内存空间
void DestoryStack(SqStack &S){
free(S.base);
}
//清空栈，将S清除为空栈
void ClearStack(SqStack &S){
S.top=S.base; //惰性删除，直接将栈顶指针对齐到栈底
}
//判断栈空
bool IsEmpty(SqStack S){
return S.top==S.base; //如果栈顶和栈底相同，则是空栈
}
//判断栈满
bool IsFull(SqStack S){
return S.top-S.base==MAXSIZE; //如果栈顶这栈底的距离为MAXSIZE就是栈满
}
//返回栈的长度，即栈中现有的元素个数
int StackLength(SqStack S){
return S.top-S.base;
}
//读取栈顶元素,并用e返回
void GetTop(SqStack S,Elem &e){
if(IsEmpty(S)){ //如果栈空，打印错误信息并返回
printf("Stack is empty!\n");
return;
}
e=*(S.top-1); //top指向栈顶元素的后一个位置，因此-1 取元素
}
//入栈
bool Push(SqStack &S,Elem e){
if(IsFull(S)){ //如果栈满，无法入栈，打印错误信息
printf("Stack is full!\n");
return false;
}
*S.top++=e; //栈顶指针的位置进行填装，然后栈顶指针后移
return true;
}
//出栈
bool Pop(SqStack &S,Elem &e){
if(IsEmpty(S)){ //如果栈空，无法出栈，打印错误信息
printf("Stack is empty!\n");
return false;
}
e=*--S.top; //因为top指向栈顶元素的后一个位置，先将top减一，再读取栈顶的元素
}
//从栈底到栈顶依次输出栈中元素
void StackTraverse(SqStack S){
printf("栈中元素个数：%d，栈底到栈顶元素依次为：\n栈底 ",StackLength(S));
for(Elem *p=S.base;p!=S.top;p++){
PrintData(*p); putchar(' ');
}
printf("栈顶\n");
}
用于测试栈的main函数
int main(void){
Elem temp;
SqStack S;
printf("-------------------------------------\n");
printf("初始化栈，把0-25压入栈中.\n");
InitStack(S);
for(int i=0;i<=25;i++){
temp=i;
Push(S,temp);
}
StackTraverse(S);
printf("-------------------------------------\n");
printf("读取并打印栈顶元素：");
GetTop(S,temp);
PrintData(temp); putchar('\n');
printf("-------------------------------------\n");
printf("出栈并打印出栈元素：");
Pop(S,temp);
PrintData(temp); putchar('\n');
StackTraverse(S);
printf("-------------------------------------\n");
printf("空栈出栈测试：");
ClearStack(S);
Pop(S,temp);
printf("-------------------------------------\n");
printf("满栈入栈测试：");
for(int i=0;i<101;i++){
temp=i;
Push(S,temp);
}
printf("-------------------------------------\n");
return 0;
}
测试结果：
-------------------------------------
初始化栈，把0-25压入栈中.
栈中元素个数：26，栈底到栈顶元素依次为：
栈底 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 栈顶
-------------------------------------
读取并打印栈顶元素：25
-------------------------------------
出栈并打印出栈元素：25
栈中元素个数：25，栈底到栈顶元素依次为：
栈底 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 栈顶
-------------------------------------
空栈出栈测试：Stack is empty!
-------------------------------------
满栈入栈测试：Stack is full!
-------------------------------------
栈的应用
使用栈进行括号的匹配
一个算术表达式中包含() [] {}三种英文括号，编写一个算法来判别运算表达式中的三种括号是否匹配。
//这里直接使用了C++的stl中的stack，为了使得代码更加简短，并且可以直接复制使用
//需要包含stack头文件
#include<iostream>
#include<stack>
#include<string>
using namespace std;
bool BracketCheck(string str){
stack<char> s;
int i=0;
while(i<str.size()){
if(s.empty()){
s.push(str[i++]); continue; //如果是[])))这种情况中间可能遇到栈空，所以加此特判
}
switch(str[i]){
case '{':
case '[':
case '(': s.push(str[i]); break; //左括号则入栈
case '}': if(s.top()!='{') return false; //如果是右括号则和栈顶元素进行匹配，如果不匹配返回false
s.pop();break; //如果匹配，则出栈并继续循环
case ']': if(s.top()!='[') return false;
s.pop();break;
case ')': if(s.top()!='(') return false;
s.pop();break;
default : break;
}
i++;
}
if(s.empty()) return true; //如果字符串遍历完毕后栈中没有剩余，则说明匹配
else return false; //如果有剩余，则说明不匹配
}
int main(void){
string str;
cout<<"请输入一串带括号的表达式，进行表达式括号匹配的检测(输入q 结束)：";
while(1){
cin>>str;
if(str=="q") break;
if(BracketCheck(str)) cout<<"括号匹配！"<<endl;
else cout<<"括号不匹配！"<<endl;
cout<<"请继续输入要进行括号匹配检测的表达式(输入q 结束)：";
}
cout<<"Bye!";
return 0;
}
运行可测试结果：
请输入一串带括号的表达式，进行表达式括号匹配的检测(输入q 结束)：(){}[]
括号匹配！
请继续输入要进行括号匹配检测的表达式(输入q 结束)：{{{}}}((([[[]]])))
括号匹配！
请继续输入要进行括号匹配检测的表达式(输入q 结束)：{{()[]
括号不匹配！
请继续输入要进行括号匹配检测的表达式(输入q 结束)：()[]]]
括号不匹配！
请继续输入要进行括号匹配检测的表达式(输入q 结束)：(3+1)
括号匹配！
请继续输入要进行括号匹配检测的表达式(输入q 结束)：(4+6]
括号不匹配！
请继续输入要进行括号匹配检测的表达式(输入q 结束)：q
Bye!
栈的知识点补充
栈的性质
1.栈的出栈和入栈
由于栈的操作方式，如果已知入栈序列和出栈序列，则对于出栈序列来说，某个元素之前的只能是在其之前进栈的元素。
【例题】：
如果已知入栈序列是1，2，3，4，5…n,出栈序列为p1,p2,p3…pn；若p2=3，则p1可能是1和2，因为在3后边的元素不可能比3更早出栈。
2.进出栈的序列个数
n个不同的元素进栈，出栈序列的个数为:
栈的相关算法（伪代码）
1.用栈判别单链表是否对称
设单链表的头指针为L，带头结点，结构为data和next，data为字符型，设计使用栈的算法判断链表的全部n个字符是否中心对称。
//算法思想：
//前半部分入栈，然后出栈和后半部分进行比对，如果字符相同则继续比对，直到栈空；如果最后栈不空则不对称
bool dc(LinkList L, int n){
int i; //自定义栈的指针，指向栈顶的后一个位置，初始化为0
char [n/2]; //字符栈
LinkList p=L->next; //p为遍历的工作指针
for(i=0;i<n/2;i++){ //前一半入栈
s[i]=p->data; //入栈赋值
p=p->next; //遍历指针更新
}
i--; //由于for循环的边界判定，要对i进行减1修正
if(n%2==1) p=p->next; //如果n个字符串是奇数个，则p要后移一位，跨过中间结点
while(p!=NULL&&s[i]==p->data){ //后半部分进行不对，当链表未结尾并且比对成功（即对称位置字符串相同）
i--; //出栈修改栈顶指针
p=p->next; //遍历指针后移
}
if(i==-1) return true; //如果while循环结束后，栈空则说明比对成功，字符序列对称
else return false; //否则表示不对称
}
对于循环双链表，可以从头指针开始，两个指针p向前遍历，q向后依次遍历比对。如果是奇数个元素，比对成功的结束条件是两个最后指向最中间的结点（即p==q）；如果是偶数个元素，则比对成功时的结束条件为p走到了q的前边（即p->next==q）。
设两个栈S1和S2，都采用顺序栈的方式，并且共享
[0，1，2，...maxsize-1]的空间，为充分利用空间，减少溢出，请设计与S1和S2相关的入栈和出栈算法。其中，共享栈的示意图如下所示：
//1.共享栈的类型定义说明
#define MAXSIZE 100 //栈空间大小
typedef int Elemtype; //栈中元素类型
typedef struct {
Elemtype stack[MAXSIZE]; //顺序栈的数组
int top[2]; //共享栈的两个栈顶指针,指向栈顶元素，分别初始化为-1和MAXSIZE
}ShareStack;
ShareStack S; //用于操作的栈的声明
//2.入栈函数
bool Push(int i,Elemtype x){ //i表示入栈的栈号，其中0代表左边的栈，1代表右边的栈，x为入栈元素
bool ret=true; //为了统一函数的返回出口
if(i<0||i>1){ //如果入栈的栈号不正确，输出错误信息
printf("栈号错误！")；
ret=false;
}
if(S.top[1]-S.top[0]==1){ //判定栈是否已经满了，当栈满时，两个栈顶指针刚好相差一，所有的空间都被利用
printf("栈已满！")；
ret=false;
}
switch(i){
case 0:S.stack[++S.top[0]]=x; break; //如果是插入左侧的栈，先增加栈顶指针再赋值入栈
case 1:S.stack[++S.top[1]]=x; break; //如果是插入右侧的栈，先增加栈顶指针再赋值入栈
default: break;
}
return ret; //返回是否入栈成功
}
//3.出栈函数
Elemtype Pop(int i){
if(i<0||i>1){ //如果出栈的栈号不正确，则错误退出
printf("栈号错误！")；
exit(0);
}
switch(i){
case 0:
if(S.top[0]==-1){ //判断是否为空，左侧栈的判别栈顶指针是否等一-1
printf("栈空");
exit(0);
}
else return S.stack[S.top[0]--]; //不空时返回栈顶元素，并更新栈顶指针
break;
case 1:
if(S.top[1]==MAXSIZE){ //判断是否为空，左侧栈的判别栈顶指针是否等一-1
printf("栈空");
exit(0);
}
else return S.stack[S.top[1]++]; //不空时返回栈顶元素，并更新栈顶指针
break;
}
}
3.利用栈实现递归函数的非递归计算
//算法思想
//用一个栈纪律，栈中每一个元素保存n和对应的Pn(x)的值
//在P0(x),P1(x)可以得到P2(x)的基础上，以此递推关系可层层得到后序结果
//因此，每次从栈顶P1和P2开始，读两个元素算出下一个，向下递推得到相应的后序结果
double P(int n,double x){ //参数为n层函数和自变量x
struct stack{ //定义栈中元素的结构体
int n0; //存放n值
double val; //存放Pn(x)
}ST[MAXSIZE]; //顺序栈
int top=-1;
double fv1=1,fv2=2*x; //用于递推的两个自变量，f1表示第一个数，fv2表示第二个数
for(i=n;i>=2;i--) //先赋值n，由于前两个已经由fv1和fv2记录，所以只需要赋值到2即可
ST[top++].n0=i;
while(top>=0){ //如果栈不空则循环，最终栈空时刚好计算出Pn(x)
ST[top].val=2*x*fv2-2*x(ST[top].n0-1)*fv1; //递归关系
fv1=fv2; fv2=ST[top].val; //更新递推关系式子中的两个值，为下一次递归做准备
top--; //栈顶指针更新
}
if(n==0) return fv1; //特殊判定，如果n=0
else return fv2; //如果n不是0.则根据计算结果，返回fv2即Pn(x)
}