【数据结构与算法】栈和队列

妖狐艹你老母 2024-04-26 02:21 82阅读 0赞

> ? 本文由 [程序喵正在路上][Link 1] 原创，CSDN首发！  
> ? 系列专栏：[数据结构与算法][Link 2]  
> ? 首发时间：2022年9月28日  
> ? 欢迎关注?点赞?收藏?留言?  
> ? 一以贯之的努力 不得懈怠的人生

#### 阅读指南 ####

*  栈
 *   *  栈的定义
     *  栈的基本操作
     *  栈的常考题型
 *  顺序栈的实现
 *   *  顺序栈的初始化
     *  进栈操作
     *  出栈操作
     *  读取栈顶元素
     *  另一种方式
     *  共享栈
 *  链栈的实现
 *   *  链栈的定义
 *  队列
 *   *  队列的基本操作
 *  队列的顺序实现
 *   *  初始化
     *  循环队列——入队操作
     *  循环队列——出队操作
     *  读取队头元素
     *  判断队空/队满的其他方法
 *  队列的链式实现
 *   *  定义
     *  初始化
     *  入队
     *  出队
 *  双端队列
 *   *  判断输出序列合法性

## 栈 ##

### 栈的定义 ###

线性表是具有相同数据类型的 **n (n≥0)** 个数据元素的有限序列，其中 **n** 为表长，当 **n=0** 时线性表是一个空表。若用 **L** 命名线性表，则其一般表示为

**L** = （**a1, … , ai-1, ai, ai+1, … , an**）

栈（**Stack**）是只允许在一端进行插入或删除操作的线性表，没有存放数据的栈称为空栈，栈顶允许插入和删除，栈底不允许插入和删除

![在这里插入图片描述][8c8ea3cdb9f54eea9195b8106d1e4e82.png]

栈的特点：后进先出

### 栈的基本操作 ###

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>InitStack(&amp;S)</code></td> 
   <td>初始化栈。构造一个空栈 <strong>S</strong>，分配内存空间</td> 
  </tr> 
  <tr> 
   <td><code>DestroyStack(&amp;L)</code></td> 
   <td>销毁栈。销毁并释放栈 <strong>S</strong> 所用的内存空间</td> 
  </tr> 
  <tr> 
   <td><code>Push(&amp;S, x)</code></td> 
   <td>进栈，若栈 <strong>S</strong> 未满，则将 <strong>x</strong> 加入使之成为新栈顶</td> 
  </tr> 
  <tr> 
   <td><code>Pop(&amp;S, &amp;x)</code></td> 
   <td>出栈，若栈 <strong>S</strong> 非空，则弹出栈顶元素，并用 <strong>x</strong> 返回</td> 
  </tr> 
  <tr> 
   <td><code>GetTop(S, &amp;x)</code></td> 
   <td>读栈顶元素。若栈 <strong>S</strong> 非空，则用 <strong>x</strong> 返回栈顶元素</td> 
  </tr> 
  <tr> 
   <td><code>StackEmpty(S)</code></td> 
   <td>判断一个栈 <strong>S</strong> 是否为空，若 <strong>S</strong> 为空，则返回 <strong>true</strong>，否则返回 <strong>false</strong></td> 
  </tr> 
 </tbody> 
</table>

### 栈的常考题型 ###

进栈顺序为：a ➔ b ➔ c ➔ d ➔ e

有哪些合法的出栈顺序？

比如：  
e ➔ d ➔ c ➔ b ➔ a  
b ➔ e ➔ d ➔ c ➔ a

**公式**

**n** 个不同元素进栈，出栈顺序不同排列的个数为  1 n + 1 C 2 n n \\frac\{1\}\{n + 1\}\{C^n\_\{2n\}\} n\+11C2nn，这个公式成为卡特兰数，可采用数学归纳法证明

所以上面那个例子的出栈顺序不同排列的个数为

1 5 + 1 C 10 5 = 10 × 9 × 8 × 7 × 6 6 × 5 × 4 × 3 × 2 × 1 = 42 \\frac\{1\}\{5 + 1\}\{C^5\_\{10\}\} = \\frac\{10 \\times 9 \\times 8 \\times 7 \\times 6\}\{6 \\times 5 \\times 4 \\times 3 \\times 2 \\times 1\} = 42 5\+11C105=6×5×4×3×2×110×9×8×7×6=42

## 顺序栈的实现 ##

### 顺序栈的初始化 ###

### 进栈操作 ###

//进栈
    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;
    }

下面这两行代码也可以写成一行

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

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

### 出栈操作 ###

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

同样地，下面这两行代码也可以写成一行

x = S.data[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;
    }

### 另一种方式 ###

前面我们的顺序栈的栈顶指针是指向栈顶元素，下面我们用栈顶指针指向栈顶元素的上一个位置的方式来写

#define MaxSize 10		//定义栈中元素的最大个数
    typedef int ElemType;
    
    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;
    }
    
    //进栈
    bool Push(SqStack &S, ElemType x) {
        
    	if (S.top == MaxSize)		//栈满
    		return false;
    
    	S.data[S.top++] = x;
    	return true;
    }
    
    //出栈
    bool Pop(SqStack &S, ElemType &x) {
        
    	if (S.top == 0)	//栈空
    		return false;
    
    	x = S.data[--S.top];	
    	return true;
    }
    
    //读取栈顶元素
    bool GetTop(SqStack S, ElemType &x) {
        
    	if (S.top == 0)	//栈空
    		return false;
    
    	x = S.data[--S.top];		//x记录栈顶元素
    	return true;
    }

### 共享栈 ###

共享栈就是两个栈共享同一片空间

![在这里插入图片描述][3ba963b2bcb4463189adc9a88381bb07.png]

#define MaxSize 10
    typedef int ElemType;
    
    typedef struct{
        
    	ElemType data[MaxSize];
    	int top0;		//0号栈栈顶指针
    	int top1;		//1号栈栈顶指针
    }ShStack;
    
    //初始化栈
    void InitStack(ShStack &S) {
        
    	S.top0 = -1;
    	S.top1 = MaxSize;
    }

栈满的条件：`top0 + 1 = top1`

是不是挺有意思的

## 链栈的实现 ##

### 链栈的定义 ###

typedef int ElemType;
    
    typedef struct LinkNode{
        
    	ElemType data;			//数据域
    	struct LinkNode *next;	//指针域
    }*LiStack;

你会发现，其实链栈的定义和单链表的定义一模一样，所以它们的基本操作的实现方式也大致一样

## 队列 ##

队列（**Queue**）是只允许在一端进行插入，在另一端进行删除的线性表

特点 —— 先进队列的元素先出队

### 队列的基本操作 ###

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><code>InitQueue(&amp;Q)</code></td> 
   <td>初始化队列。构造一个空队列 <strong>Q</strong>，分配内存空间</td> 
  </tr> 
  <tr> 
   <td><code>DestroyQueue(&amp;Q)</code></td> 
   <td>销毁队列。销毁并释放栈 <strong>Q</strong> 所用的内存空间</td> 
  </tr> 
  <tr> 
   <td><code>EnQueue(&amp;Q, x)</code></td> 
   <td>入队，若队列 <strong>Q</strong> 未满，则将 <strong>x</strong> 加入使之成为新的队尾</td> 
  </tr> 
  <tr> 
   <td><code>DeQueue(&amp;Q, &amp;x)</code></td> 
   <td>出队，若队列 <strong>Q</strong> 非空，则删除队头元素，并用 <strong>x</strong> 返回</td> 
  </tr> 
  <tr> 
   <td><code>GetHead(Q, &amp;x)</code></td> 
   <td>读队头元素。若队列 <strong>Q</strong> 非空，则用 <strong>x</strong> 返回队头元素</td> 
  </tr> 
  <tr> 
   <td><code>QueueEmpty(Q)</code></td> 
   <td>判断一个队列 <strong>Q</strong> 是否为空，若 <strong>Q</strong> 为空，则返回 <strong>true</strong>，否则返回 <strong>false</strong></td> 
  </tr> 
 </tbody> 
</table>

## 队列的顺序实现 ##

### 初始化 ###

typedef int ElemType;
    #define MaxSize 10
    
    typedef struct{
        
    	ElemType data[MaxSize];		//用静态数组存放队列元素
    	int front, rear;			//队头指针和队尾指针
    }SqQueue;
    
    //初始化队列
    void InitQueue(SqQueue &Q) {
        
    	Q.front = Q.rear = 0;
    }
    
    //判断队列是否为空
    bool QueueEmpty(SqQueue Q) {
        
    	if (Q.rear == Q.front)	//队列为空
    		return true;
    	else
    		return false;
    }

### 循环队列——入队操作 ###

//入队操作
    bool EnQueue(SqQueue &Q, ElemType x) {
        
    	if ((Q.rear + 1) % MaxSize == Q.front)	//判断队列是否已满
    		return false;
    
    	Q.data[Q.rear] = x;					//新元素插入队列 
    	Q.rear = (Q.rear + 1) % MaxSize;	//队尾指针加1取模
    	return true;
    }

![在这里插入图片描述][d9deb19df733492bb69e71b27be747a9.png]

### 循环队列——出队操作 ###

//出队操作
    bool DeQueue(SqQueue &Q, ElemType &x) {
        
    	if (Q.rear == Q.front)		//判断队列是否为空
    		return false;
    
    	x = Q.data[Q.front];
    	Q.front = (Q.front + 1) % MaxSize;
    	return true;
    }

### 读取队头元素 ###

//获得队头元素的值，用x返回
    bool GetHead(SqQueue Q, ElemType &x) {
        
    	if (Q.rear == Q.front)		//判断队列是否为空
    		return false;
    
    	x = Q.data[Q.front];
    	return true;
    }

队列元素个数：`(rear + MaxSize - front) % MaxSize`

### 判断队空/队满的其他方法 ###

*  可以定义一个 **size** 变量，初始值为 **0**  
    每次入队 **size+1**，每次出队 **size-1**，判断时根据 **size** 的值来判断即可
 *  定义一个 **tag** 变量  
    每次执行入队操作后，**tag** 的值变为 **1**；每次执行出队操作后，**tag** 的值变为 **0**  
    判断队满的条件——`Q.rear == Q.front && tag == 1`  
    判断队空的条件——`Q.rear == Q.front && tag == 0`

## 队列的链式实现 ##

### 定义 ###

typedef int ElemType;
    
    typedef struct LinkNode{
        	//链式队列结点
    	ElemType data;
    	struct LinkNode *next;
    };
    
    typedef struct{
        
    	LinkNode *front, *rear;		//队列的队头和队尾指针
    }LinkQueue;

### 初始化 ###

**带头结点**

//初始化队列（带头结点）
    void InitQueue(LinkQueue &Q) {
        
    	//初始时，front、rear 都指向头结点
    	Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
    	Q.front->next = NULL;
    }
    
    //判断队列是否为空
    bool IsEmpty(LinkQueue Q) {
        
    	if (Q.front == Q.rear)
    		return true;
    	else
    		return false;
    }

**不带头结点**

//初始化队列（不带头结点）
    void InitQueue(LinkQueue &Q) {
        
    	//初始时，front、rear 都指向NULL
    	Q.front = Q.rear = NULL;
    }
    
    //判断队列是否为空
    bool IsEmpty(LinkQueue Q) {
        
    	if (Q.front == NULL)
    		return true;
    	else
    		return false;
    }

### 入队 ###

**带头结点**

//入队（带头结点）
    void EnQueue(LinkQueue &Q, ElemType x) {
        
    	LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    	s->data = x;
    	s->next = NULL;
    	Q.rear->next = s;	//新结点插入到rear之后
    	Q.rear = s;			//修改表尾指针
    }

**不带头结点**

//入队（不带头结点）
    void EnQueue(LinkQueue &Q, ElemType x) {
        
    	LinkNode *s = (LinkNode*)malloc(sizeof(LinkNode));
    	s->data = x;
    	s->next = NULL;
    
    	//不带头结点的队列，第一个元素入队时需要特别处理
    	if (Q.front == NULL) {
        
    		Q.front = s;		//修改队头队尾指针
    		Q.rear = s;
    	}
    	else {
        
    		Q.rear->next = s;	//新结点插入到rear之后
    		Q.rear = s;			//修改表尾指针
    	}
    }

### 出队 ###

**带头结点**

//出队（带头结点）
    bool DeQueue(LinkQueue &Q, ElemType &x) {
        
    	if (Q.front == Q.rear)		//判断队列是否为空
    		return false;
    
    	LinkNode *p = Q.front->next;
    	x = p->data;				//用x返回队头元素
    	Q.front->next = p->next;	//修改头结点的next指针
    	if (Q.rear == p)			//此次是最后一个结点出队
    		Q.rear = Q.front;		//修改rear指针
    	free(p);					//释放结点空间
    	return true;
    }

**不带头结点**

//出队（不带头结点）
    bool DeQueue(LinkQueue &Q, ElemType &x) {
        
    	if (Q.front == Q.rear)		//判断队列是否为空
    		return false;
    
    	LinkNode *p = Q.front;
    	x = p->data;				//用x返回队头元素
    	Q.front = p->next;			//修改front指针
    
    	if (Q.rear == p)			//此次是最后一个结点出队
    		Q.rear = Q.front = NULL;	
    
    	free(p);					//释放结点空间
    	return true;
    }

## 双端队列 ##

双端队列是允许从两端插入、两端删除的线性表，如果只从某一端插入和删除，那么它就相当于一个栈

双端队列有两种：

1.  输入受限的双端队列——只允许从一端插入、两端删除的线性表
2.  输出受限的双端队列——只允许从两端插入、一端删除的线性表

### 判断输出序列合法性 ###

若数据元素输入序列为 1, 2, 3, 4，则哪些输出序列是合法的，哪些是非法的？

从栈、输入受限的双端队列、输出受限的双端队列 3 个方面依次判断

[Link 1]: https://blog.csdn.net/weixin_62511863?spm=1011.2421.3001.5343
[Link 2]: https://blog.csdn.net/weixin_62511863/category_11984530.html?spm=1001.2014.3001.5482
[8c8ea3cdb9f54eea9195b8106d1e4e82.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/74a7c5de394241ff989073a9210ab41f.png
[3ba963b2bcb4463189adc9a88381bb07.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/1f06c77d70c04a9eaf5de41da480a362.png
[d9deb19df733492bb69e71b27be747a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/26/0d0c7d9aa0ed4ac88045aa2145cd0253.png