【数据结构】栈-顺序栈、链式栈、共享栈

r囧r小猫 2021-11-27 05:20 509阅读 0赞

## 栈的定义 ##

**栈（Stack）**：只允许在一端进行插入或删除操作的线性表  
**栈顶（Top）**：线性表允许进行插入和删除的那一端。  
**栈底（Bottom）**：固定的，不允许进行插入和删除的另一端。

**Tips：**  
1.栈是受限的线性表，所以自然具有线性关系。  
2.栈中元素后进去的必然先出来，即后进先出LIFO（Last In First Out）

<table> 
 <thead> 
  <tr> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td></td> 
  </tr> 
  <tr> 
   <td>C ←Top</td> 
  </tr> 
  <tr> 
   <td>B</td> 
  </tr> 
  <tr> 
   <td>A←Bottom</td> 
  </tr> 
 </tbody> 
</table>

### 顺序栈 ###

栈是线性表的特例，那栈的顺序存储也是线性表顺序存储的简化。栈的顺序存储结构也叫作**顺序栈**。

> 回忆一下：之前在实现顺序表时，我们用的是数组来实现。那实现顺序栈是不是可以也可以用数组呢？

可以。

由于栈是受限的线性表，所以顺序栈需要在顺序表的基础上做点修改。

> 想一下：数组哪一端做栈底比较好？

向数组下标增大的方向延伸

### 顺序栈的存储结构 ###

#define MaxSize 50 		//定义栈中元素的最大个数
    typedef struct{
    Elemtype data[MaxSize];	//存放栈中元素
    int top;				//栈顶指针
    } SqStack;

**Tips：**

1.  Top值不能超过MaxSize
2.  **空栈的判定条件通常定为top==-1，满栈的判定条件通常为top==MaxSize-1，栈中数据元素个数为top+1**

### 顺序栈的操作 ###

#### 1. 判空 ####

bool StackEmpty(SqStack S){
    	if(s.top==-1) 
    		return true;
    	else 
    		return false;
    }

#### 2.进栈 ####

bool Push(SqStack &S,ElemType x){
    	if(S.top==Max-1) 
    		return false;
    	S.data[++S.top]==x; 
    		return true;
    }

#### 3.出栈 ####

bool Pop(SqStack &S，ElemType &x){
    	if(S.top==-1) 
    		return false;
    	x=S.data[S.top--];
    	return true;
    }

#### 4.读取栈顶元素 ####

bool GetTop(SqStack S，ElemType &x){
    	if(S.top==-1) 
    		return false;
    	x=S.data[S.top];
    	return true;
    }

### 共享栈 ###

顺序栈的存储空间大小需要事先开辟好，很多时候对每个栈各自单独开辟存储空间的利用率不如将各个栈的存储空间共享。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]  
**栈满**的条件：指针top1和top2只相差1，即**top1+1==top2**

#### 共享栈的结构 ####

#define MaxSize 100 	//定义栈中元素的最大个数
    typedef struct{
    Elemtype data[MaxSize]; //存放栈中元素
    int top1;				//栈1栈顶指针
    int top2; 				//栈2栈顶指针
    } SqDoubleStack;		//顺序共享栈的简写

#### 共享栈进栈 ####

bool Push(SqDoubleStack &S ，ElemType x，int stackNum){
    if(S.top1+1==s.top2) 
    	return false;		 //栈满
    if(stackNum==1) 
    	S.data[++S.top1]=x;  //栈1有元素进栈
    else if(stackNum==2) 
    	S.data[--S.top2]=x;  //栈2有元素进栈
    return true;
    }

#### 共享栈出栈 ####

bool Pop(SqDoubleStack &S, ElemType &x, int stackNum){
    	if(stackNum==1) {
    		if(S.top1==-1)
    			return false;
    		x=S.data[S.top1--];
    	}
    
    	if(stackNum==2) {
    		if(S.top1==MaxSize)
    			return false;
    		x=S.data[S.top2++];	
    	}
    }

### 链式栈 ###

栈是线性表的特例，线性表的存储结构还有链式存储结构，所以也可以用链表的方式来实现栈。栈的链式存储结构也叫作**链栈**。

> 回忆一下：每个单链表都有头指针，对于栈来说，栈顶指针也是必须的。

可以将头指针当做栈顶指针，所以栈顶放在单链表的头部。  
![在这里插入图片描述][20190724131829680.png]

typedef struct SNode{
    Elemtype data;		 //存放栈中元素
    struct SNode *next ; //栈顶指针
    } SNode，*SLink		 //链栈的结点

typedef struct LinkStack{
    SLink top; 	//栈顶指针
    int count; 	//链栈结点数
    }LinkStack 	//链栈

**Tips：**

1.  链栈一般不存在栈满的情况。
2.  空栈的判定条件通常定为top==NULL；

### 链栈的操作 ###

#### 1.进栈 ####

bool Push(LinkStack *S, ElemType x){
    	SLink p=(SLink)malloc(sizeof(SNode)); //给新元素分配空间
    	p->data=x; 							  //新元素的值
    	p->next=S->top; 					  //p的后继指向栈顶元素
    	S->top=p; 							  //栈顶指针指向新的元素
    	S->count++; 						  //栈中元素个数加1
    	return true;
    }

#### 2. 出栈 ####

bool Pop(LinkStack *S, ElemType&x){
    	if(S->top==NULL) 
    		return false;
    	x=S->top->data; 	 //栈顶元素值
    	Slink p=S->top;		 //辅助指针
    	S->top=S->top->next; //栈顶指针后移
    	free(p); 			 //释放被删除数据的存储空间
    	S->count--; 		 //栈中元素个数减一
    	return true;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]

#### 参考资料 ####

王道数据结构

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70]: /images/20211126/a83f50e6a61649b8aa3a2e9933a99012.png
[20190724131829680.png]: /images/20211126/7a5afcb04f304dd5ac39a05f265d4c91.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzU1MTAzNg_size_16_color_FFFFFF_t_70 1]: /images/20211126/e8344b584e9c48d3971613ae9b8c98e7.png