[TOC]

一、顺序栈

  • 存储结构：顺序存储
  • 后进后出，插入和删除只在栈顶进行
  • 递归
  • 附设指针top指示栈顶元素在顺序栈的位置

1.定义

1
2
3
4
5
6
7
8
9
10
11
12
#define MAXSIZE 100 //存储空间的初始分配量

typedef struct{

int *base; //栈底指针，在构造前和销毁后，base的值为NULL

int *top; //栈顶指针,指向栈顶元素的下一个位置

int stacksize; //栈可用的最大容量

}SqStack;
SqStack S;

①看栈空

S.top = -1; //指针指向元素

S.top = NULL;

S.top = 0; //指针指向栈顶元素的下一个位置

s.top = S.base;

②看栈长

length = S.top - S.base; //指针指向栈顶元素的下一个位置

③看栈满

top - base = stacksize; //指针指向栈顶元素的下一个位置

2.初始化

  • 分配存储空间，new int[]
  • 如果分配失败，!base，返回-1
  • 否则使空栈，栈顶=栈底
  • 使定义中的stacksize获得最大容量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int InitStack(SqStack &S){
//构造一个空栈

S.base = new int[MAXSIZE]; //为顺序栈分配一个指定最大容量的存储空间

if(S.base==NULL) return -1; //存储分配失败

S.top = S.base; //空栈

S.stacksize = MAXSIZE; //stacksize置为最大容量

return 1;

}

3.入栈

  • 判断栈满
  • 否则对e取值
  • 移动指针
1
2
3
4
5
6
7
8
9
10
11
12
int Push(SqStack &S,int e){
//插入元素e为新的栈顶

if(S.top-S.base = stacksize) return -1; //栈满

*S.top++ = e;  //元素e压入栈顶后，指针+1

//等价于*S.top = e; S.top++;

return 1;

}

4.出栈

  • 判断栈空
  • 否则栈顶-1
  • 出栈元素赋给元素e
1
2
3
4
5
6
7
8
9
10
11
12
int Pop(SqStack &S,int &e){
//删除S的栈顶元素，用e返回其值

if(S.top == S.base) return -1; //栈空

e = *--S.top; //栈顶指针-1，将栈顶元素赋给e

//等价于--S.top; e=*S.top;

return 1;

}

5.取栈顶元素

  • 判断栈非空
  • 返回当前栈顶元素的值，不修改指针
1
2
3
4
5
6
7
8
int GetTop(SqStack S){
//返回S的栈顶元素，不修改栈顶指针

if(S.top! = S.base) //栈非空

return *(S.top-1); //这是因为栈顶指针指向的不是真实元素，而是元素的下一个

}

二、链栈

1.定义

1
2
3
4
5
6
7
8
9
typedef struct StackNode {

int data;    

struct StackNode* next; 

}StackLink, *Linkstack;

LinkStack S;

链栈是操作受限的单链表，只能在链表的头部进行操作，故没有必要附加头结点。

  • 栈顶指针就是链表的头结点。
  • 链栈插入与删除仅在栈顶处执行(头插法/头删法)。
  • 栈无栈满问题，空间可扩充适合于多栈操作。

2.初始化

1
2
3
4
5
6
7
8
int InitStack(LinkStack &S){
//构造一个空栈S，栈顶指针置空

S= NULL;

return 1;

}

3.入栈

  • 为入栈元素e分配空间，用指针p指向 p= new LinkStack
  • 对新结点赋值e
  • 把新结点插入到栈顶
  • 修改栈顶指针为p
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Push(LinkStack &S,int e){
//在栈顶插入元素e

p = new LinkStack; //生成新结点
if(!p) return -1;

p->data = e; //赋值

p->next = S; //将新栈顶插入

S = p; //使p成为栈顶指针

return 1;

}

4.出栈

  • 判断栈空
  • 否则将栈顶元素赋值给e
  • 用结点p临时保存栈顶元素的空间
  • 下移栈顶指针
  • 释放p结点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Pop(LinkStack &S，int &e){
//删除S的栈顶元素，用e返回其值

if(S=NULL) return -1; //栈空

e = S->data; //赋值

LinkStack* p;

p = S; //用p临时保存栈顶元素空间

S = S->next; //下移栈顶指针

free(p); //释放

return 1;

}

5.读栈顶元素

  • 当栈非空，返回S的值，栈顶S保持不变
1
2
3
4
5
6
7
8
int GetTop(LinkStack S){
//返回S的栈顶元素，不修改栈顶指针

if(S!=NULL) 

return S->data;

}

三、用堆栈求解后缀表达式

1.定义

后缀表达式是一种不需要括号的表达式，其本身是对栈的一种应用。

与之对应的是中缀表达式，即我们现在使用的四则运算。

2.运算规则

顺序：从左到右入栈。

对于数字直接入栈，对于运算符号，就把栈最上面的两个数出栈，进行运算后再重新入栈。式子最后的结果出栈。

栈顶元素永远在运算符的右边。

3.例子

1
2
3
4
5
6
7
8
9
（1）令P代表入栈，O代表出栈。当利用堆栈求解后缀表达式1 2 3 + * 4 –时，堆栈操作序列是：

A.PPPOOPOO

B.PPOOPPOOPPOO

C.PPPOOPOOPPOO

D.PPPOOPOOPPOOPO

1、2、3：进栈，PPP

+：对最顶上的3、2出栈，计算2+3=5，把结果进栈，OOP

*：对5、1出栈，计算5x1=5，把结果进栈，OOP

4：进栈，P

-：对4、5出栈，计算4-5=-1，把结果进栈，OOP

最后输出结果：O

答案为D。

1
2
3
4
5
6
7
8
9
（2）表达式`a*(b+c)-d`的后缀表达式是：

A.`a b c + * d -`

B.`a b c d * + -`

C.`a b c * + d -`

D.`- + * a b c d`

数字优先进栈，所以abc

括号内的式子优先计算，所以首先遇到+，为abc+

算完加法算乘法，所以abc+*

继续将d进栈，然后算减法，所以是abc+*d-

答案为A。