关键词:
栈是一种基本的数据结构
基本概念
栈(Stack):具有一定操作约束的线性表。
只在一端(栈顶,Top)做插入、删除操作
插入数据:入栈(Push)
删除数据:出栈(Pop)
后入先出:Last In First Out(LIFO)
抽象数据类型描述
类型名称:栈
数据对象集:一个有0个或多个元素的有穷线性表
操作集:长度为MaxSize的堆栈属于Stack,堆栈元素X属于ElementType
- Stack CreateStack(int MaxSize):生成空栈,其最大长度为MaxSize
- bool IsFull(Stack S):判断栈S是否已满
- void Push(Stack S, ElementType X):将元素X压入栈
- bool IsEmpty(Stack S):判断栈S是否为空
- ElementType Pop(Stack S):删除并返回栈顶元素
顺序存储实现
栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。
结构体定义
typedef int Position;
struct SNode
ElementType *Data; //存储元素的数组
Position Top; //栈顶位置
int MaxSize; //最大容量
;
typedef struct SNode *Stack;
初始化栈
Stack CreateStack(int MaxSize) //初始化最大容量为MaxSize的空栈
Stack S=(Stack)malloc(sizeof(struct SNode));
S->Data=(ElementType *)malloc(MaxSize*sizeof(ElementType)); //分配内存
S->Top=-1; //空栈栈顶位置为-1
S->MaxSize=MaxSize;
return S;
是否满栈
判断栈是否满了,可以根据栈顶位置与最大容量的关系。
bool IsFull(Stack S)
return (S->Top==S->MaxSize-1);
入栈
void Push(Stack S, ElementType X)
if(IsFull(S)) //先判断栈是否已满
printf("栈已满");
else
S->Data[++(S->Top)]=X; //先把栈顶位置加1,再入栈
return true;
是否空栈
判断栈是否是空栈,可以根据栈顶位置是否为-1来判断。
bool IsEmpty(Stack S)
return (S->Top==-1);
出栈
ElementType Pop(Stack S)
if(IsEmpty(S)) //先判断栈是否已空
printf("栈已空");
return ERROR; //define ERROR -1
else
return S->Data[(S->Top)--]; //先出栈,再栈顶位置减1
链式存储实现
栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行,因为确定单链表的表尾比较耗费时间,我们一般把栈顶指针Top放在表头,也就是在链栈的头部进行插入和删除操作。因为是链式结构,也就不存在栈满这种情况。
结构体定义
typedef struct SNode *PtrToSNode;
struct SNode
ElementType Data;
PtrToSNode Next;
;
typedef PtrToSNode Stack;
初始化栈
在初始化的时候,一般先定义一个头结点Head,这个头结点不存放数据,只是作为链表的起始。
Stack CreateStack()
Stack S;
S=(Stack)malloc(sizeof(struct SNode)); //内存分配
S->Next=NULL;
return S;
是否空栈
bool IsEmpty(Stack S)
return (S->Next==NULL);
入栈
void Push(Stack S, ElementType X)
PtrToSNode tmp;
tmp=(PtrToSNode)malloc(sizeof(struct SNode));
tmp->Data=X;
tmp->Next=S->Next;
S->Next=tmp;
出栈
ElementType Pop(Stack S)
PtrToSNode FirstCell;
ElementType TopElem;
if(IsEmpty(S))
printf("栈已空
");
return ERROR; //define ERROR -1
else
FirstCell=S->Next;
TopElem=FirstCell->Data;
S->Next=FirstCell->Next;
free(FirstCell);
return TopElem;
!-->[数据结构]手动实现栈(代码片段)
栈有两种实现:静态栈(数组)和动态栈(链表)。这里采用链表。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)又名堆栈,它是一种运算受限的线性表.限定仅在表尾进行插入和删... 查看详情