关键词：
顺序栈以及链式栈
一、的基本概念
1.栈只允许在一段进行删除或插入操作的线性表
2.三个术语
①栈顶top ：线性表允许进行插入删除的那一端
②栈底bottom：固定的，不允许进行插入和删除的另一端
③空栈：不含任何元素的空表
3.栈只能对栈顶进行操作
4.后进先出LIFO
5.n个不同元素进栈，出栈元素不同排列个数为，例如，五个元素就有=42种
6.栈的基本操作：初始化、判空、出栈、进栈、读栈、销毁栈
二、栈的储存
- 栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储
- 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。
- 栈的顺序存储类型描述：
#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack
int data[MaxSize]; //存放栈中的元素
int top; //栈顶指针
SqStack;
4.采用链式存储的栈称为链栈，链栈便于多个栈共享存储空间和提高其效率，且不存在栈满上溢的情况。通常采用单链表实现，并且所有操作都是在单链表的表头进行的。在本文中主要是介绍了顺序栈下的一些基本操作，关于链栈的实现与单链表类似，
5.链式存储描述：
typedef struct LinkNode
int data; //数据域
struct LinkNode *next; //指针域
*LiStack; //栈类型定义
三、顺序栈的基本操作
1.初始化
//初始化
void InitStack(SqStack &S)
S.top = -1;
也可以设置成top=0，表示指向下一个要存储的位置
2.判空操作
栈空条件：S.top == -1; 栈满条件：S.top ==MaxSize-1。
//判栈空
bool Empty(SqStack S)
if(S.top == -1)
return true;
else
return false
3.进栈操作
由于初始设置S.top=-1，故栈顶指针先加一，再入栈。
//入栈
void Push(SqStack &S, int x)
if(S.top == MaxSize-1)
cout<<"栈满"<<endl;
return;
S.data[++S.top] = x; //指针先加一，再入栈
4.出栈操作
//出栈
void Pop(SqStack &S, int &x)
if(S.top == -1)
cout<<"栈空"<<endl;
return;
x = S.data[S.top--]; //先出栈，指针再减一
5.读取栈顶操作
//读栈顶元素
int GetTop(SqStack S)
if(S.top == -1)
cout<<"栈空"<<endl;
return -1;
else
return S.data[S.top];
6.遍历栈
//遍历栈
void PrintStack(SqStack S)
while(S.top != -1)
cout<<S.data[S.top--]<<" ";
cout<<endl;
四、共享栈
1.图例
2.描述
typedef struct
ElemType data[MaxSize]; //静态数组存放栈中元素
int top1; //1号栈栈顶指针
int top2; //2号栈栈顶指针
ShStack;
3.初始化
//1.初始化共享栈
void InitShStack(ShStack& S)
S.top1 = -1; //初始化1号栈栈顶指针
S.top2 = MaxSize; //初始化2号栈栈顶指针
4.判空
//2. 1号栈判空
bool Stack1Empty(ShStack S)
return (S.top1 == -1);
//2. 2号栈判空
bool Stack2Empty(ShStack S)
return (S.top2 == MaxSize);
5.判断栈满
Top1-top2==1
6.入栈
//4. 1号栈入栈操作：新元素入栈(先存再加)
bool Push1(ShStack& S, ElemType x)
if (S.top1+1 == S.top2) //栈满，报错
return false;
S.data[++S.top1] = x;
return true;
//5. 2号栈入栈操作：新元素入栈(先存再加)
bool Push2(ShStack& S, ElemType x)
if (S.top1 + 1 == S.top2) //栈满，报错
return false;
S.data[--S.top2] = x;
return true;
7.出栈
//6. 1号栈出栈操作：栈顶元素出栈
bool Pop1(ShStack& S, ElemType& x)
if (S.top1 == -1) //1号栈栈空，报错
return false;
x = S.data[S.top1--];
return true;
//7. 2号栈出栈操作：栈顶元素出栈
bool Pop2(ShStack& S, ElemType& x)
if (S.top2 == MaxSize) //2号栈栈空，报错
return false;
x = S.data[S.top2++];
return true;
8.栈顶读栈
//8. 1号栈读取栈顶元素操作
bool GetTop1(ShStack S, ElemType& x)
if (S.top1 == -1) //1号栈栈空，报错
return false;
x = S.data[S.top1];
return true;
//9. 2号栈读取栈顶元素操作
bool GetTop2(ShStack S, ElemType& x)
if (S.top2 == MaxSize) //2号栈栈空，报错
return false;
x = S.data[S.top2];
return true;
四、链式栈的基本操作
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
//2.定义链栈结构体
typedef struct LinkStackNode
ElemType data;//存数据
struct LinkStackNode *next;//存下个节点的地址
LinkStack;
//3.初始化链栈
int initLinkStack(LinkStack *L)
L = (LinkStack *) malloc(sizeof(LinkStack));//申请内存
if(!L->data) return 0;//申请失败
L->data = 0;//初始化链栈头结点数据域
L->next = NULL;//初始化链栈头结点指针域
return 1;
//4.入栈
int push(LinkStack *L, ElemType e)
LinkStack *n;//新节点
n = (LinkStack *) malloc(sizeof(LinkStack));
if(!n->data) return 0;
n->data = e;//存入数据
n->next = L->next;//链栈栈顶元素链入新节点，新节点变成栈顶
L->next = n;//新节点链入链栈头结点末尾
return 1;
//5.出栈
int pop(LinkStack *L, ElemType *e)
if(!L->next) return 0;//栈空，返回0
LinkStack *d = L->next;//出栈指针指向栈顶
*e = d->data;//赋值
L->next = d->next;//头结点跳过出栈节点，链入出栈节点的下一节点
free(d);//释放内存
return 1;
//6.取栈顶
int getTop(LinkStack *L, ElemType *e)
if(!L->next) return 0;
*e = L->next->data;
return 1;
void printStack(LinkStack *L)
LinkStack *p = L;//遍历指针
while (p)
p = p->next;
printf("%d ", p->data);
printf("\\n");
//7.演示
int main()
LinkStack L;
initLinkStack(&L);
ElemType e;
printf("入栈元素：");
scanf("%d", &e);
push(&L, e);
getTop(&L, &e);
printf("栈顶元素：%d\\n",e);
pop(&L, &e);
printf("出栈元素：%d", e);
printf("\\n入栈元素(Ctrl + C结束)：");
while (scanf("%d", &e) != EOF)
push(&L, e);
printf("入栈元素(Ctrl + C结束)：");
printf("\\n遍历元素：");
printStack(&L);
return 0;
(王道408考研数据结构)第三章栈和队列-第一节：栈基本概念顺序栈和链栈基本操作(代码片段)
文章目录一：栈基本概念（1）栈的定义（2）压栈和出栈（3）进栈出栈变化形式（4）栈的操作二：栈的顺序存储结构及其操作实现（1）顺序栈的定义（2）进栈（3）出... 查看详情
(王道408考研数据结构)第三章栈和队列-第二节：队列基本概念顺序栈和链栈基本操作
文章目录一：队列基本概念（1）队列的定义（2）入队和出队（3）队列的操作二：队列的顺序存储结构（循环队列）及其操作实现（1）单纯的顺序存储的不足之处及font指针和rear指针（2）循环队列概念及队空队满条件（3）循环... 查看详情
3.1栈的顺序存储结构(代码片段)
<?phpheader("content-type:text/html;charset=utf-8");/***栈的顺序存储结构的基本操作**包括*1.顺序栈的初始化__contruct()*2.销毁栈destroyStack()*3.清空栈clearStack()*4.判断栈是否为空stackEmpty()*5.获取栈顶元素getTop()*6.进栈操作push()*7.出栈操作pop() 查看详情
数据结构3.栈和队列(代码片段)
....1栈的基本概念（1）栈的定义（2）栈的基本操作3.1.2栈的顺序存储结构（1）顺序栈的实现（2）栈的基本运算（3）共享栈3.1.3栈的链式存储结构3.2队列3.2.1队列的基本概念（1）队列的定义（2）队列常见的基本操作3.2.2队列的顺序... 查看详情
栈和队列分别的顺序结构和链式结构(代码片段)
...表，要记住他俩本身就费劲。难受的是他俩还能分别考虑顺序结构和链式结构，很复杂，容易混淆。其实比起FILO（先进后出）和FIFO（先进先出）等特点，更重要的是对指针的把握。进出顺序是在逻辑层面的，只要理解就行，难... 查看详情
线性表--单调栈(代码片段)
...)3.2单调递减栈模板(python代码)总结前言栈的存储结构分为顺序存储结构和链式存储结构，并且为了解决 查看详情
栈的实现（c语言）---数据结构(代码片段)
文章目录1.栈的简介1.1栈的特点1.2栈的相关概念2.栈的顺序存储2.1初始化栈2.1入栈2.3出栈2.4获取栈顶元素2.5获取栈的大小2.6判断栈是否为空2.7栈的销毁2.8测试部分3.栈的链式存储3.1链式存储的简单介绍3.2链式存储中入栈和出栈的简... 查看详情
栈的实现（c语言）---数据结构(代码片段)
文章目录1.栈的简介1.1栈的特点1.2栈的相关概念2.栈的顺序存储2.1初始化栈2.1入栈2.3出栈2.4获取栈顶元素2.5获取栈的大小2.6判断栈是否为空2.7栈的销毁2.8测试部分3.栈的链式存储3.1链式存储的简单介绍3.2链式存储中入栈和出栈的简... 查看详情
线性表之栈(代码片段)
...的子弹最后才能出； 按照存储结构可以分为两种栈：顺序栈链式栈栈的结构体定义：顺序栈： //顺序栈的结构体定义typedefstructintdata[MaxSize];//栈顶指针inttop;SqStack;链式栈：//链栈结构 查看详情
杠上数据结构-栈(代码片段)
...质是一种线性表，那么栈的存储结构也有两种：顺序存储结构(顺序栈)链式存储结构(链式栈)栈顺序存储结构栈的顺 查看详情
数据结构之栈以及栈的基本操作(代码片段)
栈文章目录栈前言进栈出栈的变化形式栈的实现栈的顺序存储结构：栈的链式存储结构：文件的创建栈结构的定义栈的初始化入栈出栈获取栈顶元素获取栈中有效元素个数检测栈是否为空销毁栈括号匹配问题前言栈是限... 查看详情
数据结构学习笔记——链式存储结构实现栈(代码片段)
...实现例子一、链栈的定义有两种方式实现栈，分别是顺序存储结构和链式存储结构，这里我们把通过链式存储结构实现的栈成为链栈&# 查看详情
栈的实现（c语言）---数据结构(代码片段)
文章目录1.栈的简介1.1栈的特点1.2栈的相关概念2.栈的顺序存储2.1初始化栈2.1入栈2.3出栈2.4获取栈顶元素2.5获取栈的大小2.6判断栈是否为空2.7栈的销毁2.8测试部分3.栈的链式存储3.1链式存储的简单介绍3.2链式存储中入栈和出栈的简... 查看详情
栈的顺序存储和链式存储(代码片段)
...n;//取栈顶元素publicObjectpeek()throwsStackEmptyException; 顺序存储结构实现 顺序栈是使用顺序存储结构实现的堆栈，即利用一组地址连续的存储单元依次存放堆栈中的数据元素。由于堆栈是一种特殊的线性表，因此在线... 查看详情
java------栈(代码片段)
栈1.顺序栈1.1代码实现2.链式栈2.1代码实现1.顺序栈数组尾插O（1），尾删O（1）头插O（n），头删O（n）1.1代码实现importjava.util.Arrays;importjava.util.EmptyStackException;public 查看详情
用自定义链式栈解决力扣括号匹配问题(代码片段)
...必须用相同类型的右括号闭合。2、左括号必须以正确的顺序闭合。3、注意空字符串可被认为是有效字符串。来 查看详情
数据结构与算法栈与队列c语言版(代码片段)
...3.2栈、队列与一般线性表的区别3.3栈的表示和操作的实现顺序栈与顺序表=================顺序栈的表示顺序栈初始化判断顺序栈是否为空求顺序栈的长度清空顺序栈销毁顺序栈顺... 查看详情
数据结构--栈（stack）(代码片段)
栈1.栈的定义2.顺序栈2.1代码设计解析2.2源代码1.栈的定义定义：栈：一种先进后出，后进先出的数据结构（如箱子存放东西）栈和队列都是受到限制的顺序表栈分为顺序栈和链式栈栈只能在一端进行插入和删... 查看详情