[入门必看]数据结构3.1：栈

[入门必看]数据结构3.1：栈

• 第三章 栈、队列和数组
• 3.1 栈
• • 知识总览
  • • 3.1.1_栈的基本概念
    • 3.1.2_栈的顺序存储实现
    • 3.1.3_栈的链式存储实现
  • 3.1.1_栈的基本概念
  • • 栈的基本操作
    • 栈的常考题型
  • 3.1.2_栈的顺序存储实现
  • • 初始化操作
    • 进栈操作
    • 出栈操作
    • 读栈顶元素操作
    • 另一种方式实现
    • 共享栈
  • 3.1.3_栈的链式存储实现
• 知识回顾与重要考点
• • 3.1.1_栈的基本概念
  • 3.1.2_栈的顺序存储实现
  • 3.1.3_栈的链式存储实现

---

第三章 栈、队列和数组

小题考频：23
大题考频：4

---

3.1 栈

难度：☆☆

知识总览

3.1.1_栈的基本概念

3.1.2_栈的顺序存储实现

3.1.3_栈的链式存储实现

---

3.1.1_栈的基本概念

数据结构三要素——逻辑结构、数据的运算、存储结构（物理结构）

存储结构不同，运算的实现方式不同

栈（Stack）是只允许在一端进行插入或删除操作的线性表

逻辑结构：与普通线性表相同
数据的运算：插入、删除操作有区别

stack整齐的一堆：

从顶部放入，从顶部取出。

• 重要术语：栈顶、栈底、空栈
  

栈的基本操作

回顾线性表的基本操作
InitList(&L)：初始化表。构造一个空的线性表L，分配内存空间。
DestroyList(&L)：销毁操作。销毁线性表，并释放线性表L所占用的内存空间。

创、销

ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e。
ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。

增、删

LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。
GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。

查、改（也要查）

其他常用操作：
Length(L)：求表长。返回线性表L的长度，即L中数据元素的个数。
PrintList(L)：输出操作。按前后顺序输出线性表L的所有元素值。
Empty(L)：判空操作。若L为空表，则返回true，否则返回false。

• 栈的基本操作
  InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。
  DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。

创、销

Push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。
Pop(&S,&x)：出栈，若栈S非空，则弹出栈顶元素，并用x返回。

增、删；
返回栈顶元素、删除栈顶元素

GetTop(S, &x)：读栈顶元素。若栈S非空，则用x返回栈顶元素

查：栈的使用场景中大多只访问栈顶元素；
返回栈顶元素、不删除栈顶元素

其他常用操作：
StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。

栈的常考题型

• Q：进栈顺序：
  a->b->c->d->e
  有哪些合法的出栈顺序？

• A：n个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n+1}{C}_{2n}^n$。
  上述公式称为卡特兰（Catalan）数，可采用数学归纳法证
  明（不要求掌握）。
  $$\frac{1}{5+1}{C}_{10}^5=\frac{10\times 9\times 8\times 7\times 6}{6\times 5\times 4\times 3\times 2\times 1}=42$$

出栈和入栈穿插进行，会得到不同的出栈顺序

---

3.1.2_栈的顺序存储实现

初始化操作

• 顺序栈结构体：

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
	ElemType data[Maxsize] //静态数组存放栈中元素
	int top; //栈顶指针
} SqStack; //Sq：sequence - 顺序

void testStack( ){
	SqStack S; //声明一个顺序栈(分配空间)
	//……
}

栈顶指针top，记录数组下标，从0开始。

• 初始化顺序栈：

//初始化栈
void InitStack(SqStack &S){
	S.top = -1; //初始化栈顶指针
}

data[0]此时还没有元素，栈顶指针不能指向0

• 判断顺序栈空：

bool StackEmpty(SqStack S){
	if(S.top == -1) //栈空
		return true;
	else //不空
		return false;
}

---

进栈操作

• 新元素入栈：

//新元素入栈
bool Push(Sqstack &S, ElemType x){
	if(S.top == MaxSize - 1) //栈满，报错
		return false; 
	S.top = S.top + 1; //指针先加1
	S.data[S.top] = x; //新元素入栈
	return true; 
}

由于top指针，永远指向此时栈顶元素位置；
当新元素入栈时，先让top指针+1，然后往top指针指向的位置放入新元素。

注意：

	S.top = S.top + 1; //指针先加1
	S.data[S.top] = x; //新元素入栈

等价于

S.data[++S.top] = x;

小心错误写法：
S.data[S.top++] = x;
这句等价于：
S.data[S.top] = x;
S.top = S.top + 1;

---

出栈操作

• 元素出栈：

bool Pop(Sqstack &S, ElemType &x){
	if(S.top == -1) //栈空，报错
		return false; 
	x = S.data[S.top]; //栈顶元素先出栈
	S.top = S.top - 1; //指针再减1
	return true;
}

x加了引用符号，出栈操作中操作的x和函数调用者定义的变量x相同。

注意：

	x = S.data[S.top]; //栈顶元素先出栈
	S.top = S.top - 1; //指针再减1

等价于

x = S.data[S.top--];

小心错误写法：
x = S.data[–S.top];
这句等价于：
S.top = S.top + 1;
x = S.data[S.top];

---

读栈顶元素操作

• 读栈顶元素：

//读栈顶元素
bool GetTop(SqStack S, ElemType &x){
	if(S.top == -1) //栈空，报错
		return false;
	x = S.data[S.top]; //x记录栈顶元素
	return true;
}

和出栈操作唯一的区别是：
x = S.data[S.top–];
出栈操作会让top指针减减（S.top–）即往下移一位

---

另一种方式实现

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
	ElemType data[Maxsize] //静态数组存放栈中元素
	int top; //栈顶指针
} SqStack; 

//初始化栈
void InitStack(SqStack &S){
	S.top = 0; //初始化栈顶指针
}

//判断栈空
bool StackEmpty(SqStack S){
	if(S.top == 0} //栈空
		return true;
	else //不空
		return false;
}


void testStack(){
	SqStack S; //声明一个顺序栈（分配空间）
	InitStack(S);
	//……
}

S.top = 0; //初始化栈顶指针

此时初始栈顶指针指向0；

此时top指针指向了下一个可以插入元素的位置。

• 入栈操作步骤为：
  Step1：先把新的数据元素x放到top所指向的位置
  Step2：再让top指针+1

//进栈
S.data[S.top] = x;
S.top = S.top + 1;

等价于：

S.data[S.top++] = x;

• 出栈操作步骤为：
  Step1：先让top指针-1
  Step2：再把top指向的元素传回去。

//出栈
S.top = S.top - 1;
x = S.data[S.top];

等价于：

x = S.data[--S.top];

• 判断栈满：

S.top == MaxSize;

注意审题！top指针指向栈顶元素，还是栈顶元素后面的一个位置！两种方式实现代码是不一样的！

• 顺序栈的缺点：栈的大小不可变

分配大片的存储空间，会导致内存资源的浪费，可以使用共享栈的方式来提高这一整片内存空间的利用率。

---

共享栈

——两个栈共享同一片空间
设置两个栈顶指针 - 0号栈、1号栈栈顶指针

• 0号栈栈顶指针初始化为-1；
  往0号栈中放入数据元素，从下往上依次递增。
  

• 1号栈栈顶指针初始化为MaxSize；
  往1号栈中放入数据元素，从上往下依次递增。
  

代码实现：

#define MaxSize 10 //定义栈中元素的最大个数
typedef struct{
	ElemType data[Maxsizel; //静态数组存放栈中元素
	int top0; //0号栈栈顶指针
	int top1; //1号栈栈顶指针
}ShStack;

//初始化栈
void InitStack(ShStack &S){
	S.top0 = -1; //初始化栈顶指针
	S.top1 = MaxSize;
}

//判断栈满的条件
S.top0 + 1 == S.top1

在逻辑上，实现了两个栈；
在物理上，两个栈共享同一片存储空间。
提高了内存资源的利用率

---

3.1.3_栈的链式存储实现

单链表中
头结点的后插操作 - 对应：进栈
头结点的后删操作 - 对应：出栈
链栈和单链表类似。

• 链栈的定义：

typedef struct Linknode{
 	ElemType data; //数据域
 	struct Linknode *next; //指针域
 }*LiStack; //栈类型定义

带头结点的初始化：

不带头结点的初始化：

两种方式初始化，判断栈空的方式不一样。

---

知识回顾与重要考点

3.1.1_栈的基本概念

• 插入和删除只能在栈顶进行，后进先出（LIFO）

---

3.1.2_栈的顺序存储实现

• 初始化时top = -1，可以让栈顶指针指向当前的栈顶元素；
  初始化时top = 0，也可以让栈顶指针指向下一个可以插入数据元素的位置。

• 所有的基本操作都可以在$O(1)$的时间复杂度内完成

• 销毁一个顺序栈：
  在逻辑上把这个栈给清空，接下来回收这个栈所占用的内存资源
  逻辑上清空一个栈，只需要让top指针指向初始化的位置即可。
  本节中使用变量声明的方式分配相应的内存空间，没有使用malloc函数，所以函数运行结束后系统自动回收内存。
  

---

3.1.3_栈的链式存储实现