## 【数据结构】11 堆栈（顺序存储和链式存储）

news/2024/2/24 7:21:32/文章来源:https://blog.csdn.net/vox520/article/details/136081824

## 定义

（1）Stack CreateStack( int MaxSize)

（2）bool IsFull(Stack)

（3）bool Push(Stack S, ElementType X)

（4）ElementType Pop(Stack S)

A进A出 B进B出
A进B进 B出A出

A进B进C进 C出B出A出
A进B进 B出 C进 C出
A进B进 B出A出 C进C出
A进A出 B进B出 C进C出
A进A出 B进C进 C出B出

1. A在第一位出 A_ _ _
对应3个字符出入栈 -5种情况
2. A在第二位 _ A _ _
只能B出来后A才能出 BA_ _
对应2个字符出入栈 -2种情况
3. A在第三位 _ _ A _
前两位必是 B或者C
最后一位必是D
2种情况
4. A在第四位 _ _ _ A
对应三个字符出入栈 5种情况

## 堆栈的实现

### 顺序栈的实现

``````typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;struct SNode {ElementType* Data;Position Top;int MaxSize;};typedef PtrToSNode Stack;``````

#### 顺序栈的创建

``````Stack CreateStack(int MaxSize) {Stack S = (Stack)malloc(sizeof(SNode) * 1);S->Data = (ElementType * )malloc(sizeof(ElementType) * MaxSize);S->Top = -1;S->MaxSize = MaxSize;return S;
}
``````

#### 进栈

``````
bool IsFull(Stack S) {if (S->Top == S->MaxSize - 1) {return true;}return false;
}bool Push(Stack S, ElementType X) {if (IsFull(S)) {printf("The Stack is full!\n");return false;}(S->Top)++;S->Data[S->Top] = X;return true;}
``````

#### 出栈

``````bool IsEmpty(Stack S) {if (S->Top == -1) {return true;}return false;
}ElementType Pop(Stack S) {if (IsEmpty(S)) {printf("The Stack is empty!\n");return -1;}int temp = S->Data[S->Top];(S->Top)--;return temp;}
``````

#### 完整代码

``````# include <stdio.h>
#include < stdlib.h>typedef int ElementType;
typedef int Position;
typedef struct SNode* PtrToSNode;struct SNode {ElementType* Data;Position Top;int MaxSize;};typedef PtrToSNode Stack;Stack CreateStack(int MaxSize) {Stack S = (Stack)malloc(sizeof(SNode) * 1);S->Data = (ElementType * )malloc(sizeof(ElementType) * MaxSize);S->Top = -1;S->MaxSize = MaxSize;return S;
}bool IsFull(Stack S) {if (S->Top == S->MaxSize - 1) {return true;}return false;
}bool Push(Stack S, ElementType X) {if (IsFull(S)) {printf("The Stack is full!\n");return false;}/*(S->Top)++;S->Data[S->Top] = X;*/S->Data[++(S->Top)] = X;return true;}bool IsEmpty(Stack S) {if (S->Top == -1) {return true;}return false;
}ElementType Pop(Stack S) {if (IsEmpty(S)) {printf("The Stack is empty!\n");return -1;}/*int temp = S->Data[S->Top];(S->Top)--;return temp;*/return (S->Data[(S->Top)--]);}void print_s(Stack S) {int t = S->Top;while (t != -1) {printf("Node: %d\n", S->Data[t]);(t)--;}
}int main() {Stack S = NULL;int MaxSize = 10;S = CreateStack(MaxSize);ElementType X;int N;scanf_s("%d", &N);while (N--) {scanf_s("%d", &X);if (Push(S, X) == false) {printf("Push error!\n");}}print_s(S);int out = Pop(S);printf("out : %d\n", out);print_s(S);}``````

#### 用一个数组实现两个堆栈

##### 结构体
``````typedef struct DSNode* DStack;
struct DSNode
{ElementType* Data;Position Top1;Position Top2;int MaxSize;
};``````
##### 创建
``````DStack CreateDStack(int MaxSize) {DStack S = (DStack)malloc(sizeof(DSNode) * 1);S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);S->Top2 = -1;S->Top1 = MaxSize;S->MaxSize = MaxSize;return S;
}
``````
##### 入栈
``````
bool PushX(DStack S, ElementType X, int Tag) {if (S->Top1 - S->Top2 == 1) {printf("the stack is full!\n");return false;}if (Tag == 1) {(S->Top1)--;S->Data[S->Top1] = X;}else{(S->Top2)++;S->Data[S->Top2] = X;}return true;
}
``````
##### 出栈
``````
ElementType PopX(DStack S, int Tag) {if (Tag == 1) {if (S->Top1 == S->MaxSize) {printf("the stack1 is empty!\n");return -1;}else {return S->Data[(S->Top1)++];}}else {if (S->Top2 == -1) {printf("the stack2 is empty!\n");return -1;}else {return S->Data[(S->Top2)--];}}}``````
##### 完整代码
``````# include <stdio.h>
#include < stdlib.h>typedef int ElementType;
typedef int Position;typedef struct DSNode* DStack;
struct DSNode
{ElementType* Data;Position Top1;Position Top2;int MaxSize;
};DStack CreateDStack(int MaxSize) {DStack S = (DStack)malloc(sizeof(DSNode) * 1);S->Data = (ElementType*)malloc(sizeof(ElementType) * MaxSize);S->Top2 = -1;S->Top1 = MaxSize;S->MaxSize = MaxSize;return S;
}bool PushX(DStack S, ElementType X, int Tag) {if (S->Top1 - S->Top2 == 1) {printf("the stack is full!\n");return false;}if (Tag == 1) {(S->Top1)--;S->Data[S->Top1] = X;}else{(S->Top2)++;S->Data[S->Top2] = X;}return true;
}ElementType PopX(DStack S, int Tag) {if (Tag == 1) {if (S->Top1 == S->MaxSize) {printf("the stack1 is empty!\n");return -1;}else {return S->Data[(S->Top1)++];}}else {if (S->Top2 == -1) {printf("the stack2 is empty!\n");return -1;}else {return S->Data[(S->Top2)--];}}}void print_ds(DStack S) {printf("print S1:\n");int t = S->Top1;while (t != S->MaxSize) {printf("Node: %d\n", S->Data[t]);(t)++;}printf("print S2:\n");t = S->Top2;while (t != -1) {printf("Node: %d\n", S->Data[t]);(t)--;}
}int main() {int MAXSIZE = 10;DStack S = CreateDStack(MAXSIZE);ElementType X;int N;scanf_s("%d", &N);while (N--) {scanf_s("%d", &X);if (PushX(S, X, 1) == false) {printf("Push error!\n");}if (PushX(S, X, 2) == false) {printf("Push error!\n");}}print_ds(S);int out = PopX(S,1);printf("out : %d\n", out);print_ds(S);}``````

### 链式存储的实现

#### 数据结构

``````typedef int ElementType;
typedef struct SNode* PtrToSNode;struct SNode {ElementType Data;PtrToSNode Next;
};typedef PtrToSNode Stack;``````

#### 创建

``````
Stack CreateStack(Stack S) {S = (Stack)malloc(sizeof(SNode) * 1);S->Next = NULL;return S;
}
``````

#### 入栈

``````
bool Push(Stack S, ElementType X) {Stack temp = (Stack)malloc(sizeof(SNode));temp->Data = X;temp->Next = S->Next;S->Next = temp;return true;}
``````

#### 出栈

``ElementType Pop(Stack S) {if (S->Next == NULL) {printf("the stack is empty!\n");return -1;}ElementType re = S->Next->Data;S->Next = S->Next->Next;return re;}``

#### 完整代码

``````# include <stdio.h>
#include < stdlib.h>typedef int ElementType;
typedef struct SNode* PtrToSNode;struct SNode {ElementType Data;PtrToSNode Next;
};typedef PtrToSNode Stack;Stack CreateStack(Stack S) {S = (Stack)malloc(sizeof(SNode) * 1);S->Next = NULL;return S;
}bool Push(Stack S, ElementType X) {Stack temp = (Stack)malloc(sizeof(SNode));temp->Data = X;temp->Next = S->Next;S->Next = temp;return true;}ElementType Pop(Stack S) {if (S->Next == NULL) {printf("the stack is empty!\n");return -1;}ElementType re = S->Next->Data;S->Next = S->Next->Next;return re;}void prints(Stack S) {Stack t = S->Next;while (t != NULL) {printf("Node: %d\n", t->Data);t = t->Next;}
}int main() {Stack S = NULL;S = CreateStack(S);ElementType X;int N;scanf_s("%d", &N);while (N--) {scanf_s("%d", &X);if (Push(S, X) == false) {printf("Push error!\n");}}prints(S);ElementType out = Pop(S);printf("out : %d\n", out);prints(S);}
``````

### 3D高斯溅射：面向三维场景的实时渲染技术

1. 前言 高斯溅射技术【1】一经推出&#xff0c;立刻引起学术界和工业界的广泛关注。相比传统的隐式神经散射场渲染技术&#xff0c;高斯溅射依托椭球空间&#xff0c;显性地表示多目图像的三维空间关系&#xff0c;其计算效率和综合性能均有较大的提升&#xff0c;且更容易理…

### Java+SpringBoot：高校竞赛管理新篇章

✍✍计算机编程指导师 ⭐⭐个人介绍&#xff1a;自己非常喜欢研究技术问题&#xff01;专业做Java、Python、微信小程序、安卓、大数据、爬虫、Golang、大屏等实战项目。 ⛽⛽实战项目&#xff1a;有源码或者技术上的问题欢迎在评论区一起讨论交流&#xff01; ⚡⚡ Java实战 |…

### 树莓派编程基础与硬件控制

1.编程语言 Python 是一种泛用型的编程语言&#xff0c;可以用于大量场景的程序开发中。根据基于谷歌搜 索指数的 PYPL&#xff08;程序语言流行指数&#xff09;统计&#xff0c;Python 是 2019 年 2 月全球范围内最为流行 的编程语言 相比传统的 C、Java 等编程语言&#x…

### 生成树技术华为ICT网络赛道

9.生成树 目录 9.生成树 9.1.生成树技术概述 9.2.STP的基本概念及工作原理 9.3.STP的基础配置 9.4.RSTP对STP的改进 9.5.生成树技术进阶 9.1.生成树技术概述 技术背景&#xff1a;二层交换机网络的冗余性与环路 典型问题1&#xff1a;广播风暴 典型问题2&#xff1a;MA…

### Linux开发：PAM1 介绍

PAM（Pluggable Authentication Modules ）是Linux提供的一种通用的认证方式，他可以根据需要动态的加载认证模块，从而减少认证开发的工作量以及提供认证的灵活度。 1.PAM的框架 PAM的框架由一下几个部分构成 1)应用程序，即需要使用认证服务的程序，这些应用程序是使用抽象…

### 单例模式 C++

6 种 单例 的手写&#xff0c;都是懒汉&#xff08;饿汉代码在 “懒汉 / 饿汉的区别”&#xff09; 目录 ✊前言 &#x1f33c;GPT解析 &#x1f33c;概念解析 RAII 懒汉 / 饿汉的区别 特点 举例 单例 -- 伪代码 适用场景 单例 -- 实现方式 优缺点 &#x1f382;手…

### 【Iceberg学习二】Branch和Tag在Iceberg中的应用

Iceberg 表元数据保持一个快照日志&#xff0c;记录了对表所做的更改。快照在 Iceberg 中至关重要&#xff0c;因为它们是读者隔离和时间旅行查询的基础。为了控制元数据大小和存储成本&#xff0c;Iceberg 提供了快照生命周期管理程序&#xff0c;如 expire_snapshots&#xf…