关键词:
一、什么是栈(Stack)
首先来说,栈是一种线性表的表现形式,其定义是只允许在栈顶进行插入或者删除的线性表,所以栈就有线性表的表现形式,链式栈和顺序栈。
栈顶(Top):允许进行数据的插入和删除的一端。
栈底(Bottom):不允许进行数据的插入和删除的一端。
空栈:不含任何元素的栈。
由图我们可以看出栈在插入数据时,比如说插入的是a1,a2,a3,a4,a5,a6,那么出栈的顺序就依次为a6,a5,a4,a3,a2,a1,所以总结一个规律就是栈的元素是后进先出。
二、栈的基本操作
InitStack(&S):初始化一个空栈。
StackEmpty(S):判断一个栈是否为空,为空返回true,不为空返回false。
Push(&S,x):进栈,如过栈未满,讲x加入为新的栈顶元素。
Pop(&S,&x):出栈,弹出栈顶元素,用x返回其值。
GetTop(S,&x):读取栈顶元素,用x返回其值。
DestroyStack(&S):销毁栈,并释放S栈占用的空间。
三、顺序栈的实现
顺序栈的存储结构:
#define MaxSize 100 typedef struct ElemType data[MaxSize]; //存放栈中的元素 int top; //指向栈顶元素的位置 SeqStack;
我们在初始化栈的时候栈顶的top初始为-1,在进行入栈操作时候先由top加1在进行元素的添加,在进行出栈操作时先取栈顶元素在使top减1。当S.top==-1时栈为空,S.top == MaxSize-1时栈满。
顺序栈栈的基本操作:
seqStack.h
#include<stdio.h> #define MaxSize 100 #define True 1 #define False 0 typedef int ElemType; typedef int Status; typedef int Boolean; typedef struct ElemType data[MaxSize]; //存放栈中的元素 int top; //指向栈顶元素的位置 SeqStack; void InitSeqStack(SeqStack *S);//初始化栈。 Boolean SeqStackEmpty(SeqStack S);//判断一个栈是否为空,为空返回true,不为空返回false。 Status PushSeqStack(SeqStack *S, ElemType x);//进栈,如过栈未满,讲x加入为新的栈顶元素。 Status PopSeqStack(SeqStack *S, ElemType *x);//出栈,弹出栈顶元素,用x返回其值。 Status GetTopSeqStack(SeqStack S, ElemType *x);//读取栈顶元素,用x返回其值。 Status DestroySeqStack(SeqStack *S);//毁栈,并释放S栈占用的空间。
seqStack.c
#include<stdio.h> #include"sqeStack.h" void InitSeqStack(SeqStack *S) //初始化栈。 S->top = -1; //初始化栈顶 Status PushSeqStack(SeqStack *S, ElemType x) //进栈,如过栈未满,将x加入为新的栈顶元素。 if (S->top == MaxSize - 1) //元素超出报错 return False; else S->top ++; S->data[S->top] = x; return True; Status PopSeqStack(SeqStack *S, ElemType *x) //出栈,弹出栈顶元素,用x返回其值。 if (S->top == -1) return False; else *x = S->data[S->top]; S->top--; return True; Boolean SeqStackEmpty(SeqStack S) //判断一个栈是否为空,为空返回true,不为空返回false。 if (S.top == -1) return True; else return False; Status GetTopSeqStack(SeqStack S, ElemType *x) //读取栈顶元素,用x返回其值。 if (S.top == -1) return False; else *x = S.data[S.top]; Status DestroySeqStack(SeqStack *S) //毁栈,并释放S栈占用的空间。 S->top = -1;
链栈的存储结构:
typedef struct LinkNode ElemType data; struct LinkNode *next; LinkNode,*LinkStack;
链栈的Push和Pop操作:
代码实现:
LinkStack.h
#include<stdio.h> #define True 1 #define False 0 typedef int ElemType; typedef int Status; typedef int Boolean; typedef struct LinkNode ElemType data; struct LinkNode *next; LinkNode,*LinkStack; void InitLinkStack(LinkStack S);//初始化栈。 Boolean LinkStackEmpty(LinkStack S);//判断一个栈是否为空,为空返回true,不为空返回false。 Boolean PushLinkStack(LinkStack S, ElemType x);//进栈,将x加入为新的栈顶元素。 Boolean PopLinkStack(LinkStack S, ElemType *x);//出栈,弹出栈顶元素,用x返回其值。 Boolean GetTopLinkStack(LinkStack S, ElemType *x);//读取栈顶元素,用x返回其值。 Boolean DestroyLinkStack(LinkStack S);//毁栈,并释放S栈占用的空间。
LinkStack.c
#include"LinkStack.h" void InitLinkStack(LinkStack S) //初始化栈。 S = (LinkNode*)malloc(sizeof(LinkNode)); S->next = NULL; Boolean PushLinkStack(LinkStack S, ElemType x) //进栈,将x加入为新的栈顶元素。 LinkNode *newSpace = (LinkNode*)malloc(sizeof(LinkNode)); newSpace->data = x; newSpace->next = S->next; S->next = newSpace; return True; Boolean PopLinkStack(LinkStack S, ElemType *x) //出栈,弹出栈顶元素,用x返回其值。 if (S->next == NULL) return False; else LinkNode *p = S->next; *x = p->data; S->next = p->next; free(p); return True; Boolean LinkStackEmpty(LinkStack S) //判断一个栈是否为空,为空返回true,不为空返回false。 if (S->next == NULL) return True; else return False; Boolean GetTopLinkStack(LinkStack S, ElemType *x) //读取栈顶元素,用x返回其值。 if (S->next == NULL) return False; else *x = S->next->data; return True; Boolean DestroyLinkStack(LinkStack S) //毁栈,并释放S栈占用的空间。 S->next = NULL; free(S); return True;
[数据结构]手动实现栈(代码片段)
栈有两种实现:静态栈(数组)和动态栈(链表)。这里采用链表。packagecom.darrenchan;publicclassMyStackpublicListNodestackTop;publicListNodestackBottom;publicMyStack(ListNodestackTop,ListNodestackBottom)this.stackTop=stackTop;this. 查看详情
数据结构--栈(stack)(代码片段)
...的定义定义:栈:一种先进后出,后进先出的数据结构(如箱子存放东西)栈和队列都是受到限制的顺序表栈分为顺序栈和链式栈栈只能在一端进行插入和删除,插入和删除的这一端称为栈顶,另一端... 查看详情
数据结构-栈(代码片段)
栈与队列栈概念栈:是限定仅在表尾进行插入和删除操作的线性表。栈顶(top):允许插入和删除的一端,即表尾称为栈顶栈底(bottom):表头称为栈底栈是LIFO结构,后进先出。与线性表相比,特殊之处在于限制了线性表的插入和删除... 查看详情
java数据结构—栈(代码片段)
Java数据结构—栈定义栈的应用场景数组模拟栈代码实现课后练习栈实现综合计算器定义栈的英文为(stack)栈是一个先入后出(FILO-FirstInLastOut)的有序列表栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特... 查看详情
[数据结构]单调栈(代码片段)
[数据结构]单调栈单调栈为栈中元素按照升序排列(递增栈)或降序排列(递减栈)的栈,通常可以用来寻找下一个最大/最小的题。以[1,3,4,2]数组实现一个递增栈:到[1,3,4]这里其实都没有什么问题,一直是处在递增的状态... 查看详情
[数据结构]单调栈(代码片段)
[数据结构]单调栈单调栈为栈中元素按照升序排列(递增栈)或降序排列(递减栈)的栈,通常可以用来寻找下一个最大/最小的题。以[1,3,4,2]数组实现一个递增栈:到[1,3,4]这里其实都没有什么问题,一直是处在递增的状态... 查看详情
数据结构栈(代码片段)
...用栈在内存的存储中了解到压栈和出栈,这种类似的数据结构中也有栈是限定仅在表尾进行插入或者删除操作的线性表。栈中的数据元素遵守后进先出LIFO(LastInFirstOut)的原则图片即可解释 查看详情
sh壳牌栈数据结构封装(代码片段)
数据结构之栈(代码片段)
文章目录栈的概念栈的功能实现栈结构的实现栈的初始化栈的判空读取栈顶数据插入数据删除数据栈中数据个数栈的销毁总结Stack.h文件Stack.c文件栈的概念栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操... 查看详情
数据结构--栈(代码片段)
一、什么是栈(Stack) 首先来说,栈是一种线性表的表现形式,其定义是只允许在栈顶进行插入或者删除的线性表,所以栈就有线性表的表现形式,链式栈和顺序栈。 栈顶(Top):允许进行数据的插入... 查看详情
杠上数据结构-栈(代码片段)
介绍栈:是一种只允许在一端进行插入,删除的线性表,具有先进后出的特性。通常,栈的操作端称为栈顶,另一端称为栈底。栈的插入称为进栈(push),栈的删除操作称为出栈(pop)。栈的存储结构既然栈的本质... 查看详情
数据结构-栈(代码片段)
栈是一种基本的数据结构基本概念栈(Stack):具有一定操作约束的线性表。只在一端(栈顶,Top)做插入、删除操作插入数据:入栈(Push)删除数据:出栈(Pop)后入先出:LastInFirstOut(LIFO)抽象数据类型描述类型名称:栈数据对象集:一... 查看详情
数据结构-栈(代码片段)
目录前言一、栈的概念与结构二、C语言-栈的基本操作与实现1.栈的创建2.栈的初始化3.入栈4.出栈5.获取栈顶元素6.获取栈中有效元素个数7.检测栈是否为空8.销毁栈三、栈的经典使用1.问题叙述2.解题方法3.代码实现前言本文均基于... 查看详情
数据结构复习第三章栈(代码片段)
(1)掌握栈的相关概念、特点和基本操作(入栈、出栈、判栈空、获取栈元素等)。栈:限制只能在表的一端进行插入和删除的线性表。允许插入和删除的一端,称为栈顶(top)。不允许插入和删除的另一端,称为栈底(bottom)。把一... 查看详情
我理解的数据结构——栈(stack)(代码片段)
我理解的数据结构(二)——栈(Stack)一、栈基础栈是一种线性结构相比较数组,栈对应的操作是数组的子集只能从一端添加元素,也只能从同一端取出元素,这一端称为栈顶栈是一种后进先出的数据结构,LIFO(LastInFirstOut)... 查看详情
3线性结构栈队列(代码片段)
一、栈的介绍栈(stack),是一种线性存储结构,它有以下几个特点: (1)栈中数据是按照"后进先出(LIFO,LastInFirstOut)"方式进出栈的。 (2)向栈中添加/删除数据时,只能从栈顶进行操作。栈通常包括的三种操作:push、peek... 查看详情
数据结构和算法-栈(代码片段)
栈可以分为顺序栈:数组实现链式栈:链表实现空间复杂度栈的空间复杂度:有一个n个元素的栈,在入栈和出栈过程中,只需要存储一个临时变量存储空间,所以空间复杂度是O(1)并不是说栈有n个元素,空间复杂度就是O(n),而是指除了原本... 查看详情
数据结构---[栈(stack)](代码片段)
...定义栈的基本操作实现栈(stack)栈也是一种线性数据结构,只能从栈顶一段添加/取出元素;类似于单口试管;后进先出LastInFirstOut(LIFO)栈(stack)又名堆栈,它是一种运算受限的线性表.限定仅在表尾进行插入和删... 查看详情