基本运算的栈的定义及基本运算

供稿:hz-xin.com     日期:2025-01-21
c语言中退栈运算,栈中元素随栈顶指针的变化而动态变化什么意思?指针会怎么变化呢?

栈顶指针指向最上面的元素,它的不断移动导致元素的变化

堆栈是一种执行“后进先出”算法的数据结构。

设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球,小球的直径比竹筒的直径略小。现在把不同编号的小球放到竹筒里面,可以发现一种规律:先放进去的小球只能后拿出来,反之,后放进去的小球能够先拿出来。所以“先进后出”就是这种结构的特点。

堆栈就是这样一种数据结构。它是在内存中开辟一个存储区域,数据一个一个顺序地存入(也就是“压入——push”)这个区域之中。有一个地址指针总指向最后一个压入堆栈的数据所在的数据单元,存放这个地址指针的寄存器就叫做堆栈指示器。开始放入数据的单元叫做“栈底”。数据一个一个地存入,这个过程叫做“压栈”。在压栈的过程中,每有一个数据压入堆栈,就放在和前一个单元相连的后面一个单元中,堆栈指示器中的地址自动加1。读取这些数据时,按照堆栈指示器中的地址读取数据,堆栈指示器中的地址数自动减 1。这个过程叫做“弹出pop”。如此就实现了后进先出的原则。

堆栈是计算机中最常用的一种数据结构,比如函数的调用在计算机中是用堆栈实现的。
堆栈可以用数组存储,也可以用以后会介绍的链表存储。
下面是一个堆栈的结构体定义,包括一个栈顶指针,一个数据项数组。栈顶指针最开始指向-1,然后存入数据时,栈顶指针加1,取出数据后,栈顶指针减1。

#define MAX_SIZE 100
typedef int DATA_TYPE;
struct stack
{
DATA_TYPE data[MAX_SIZE];
int top;
};

在C++中,内存分成5个区,他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。
堆,就是那些由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete。如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收。
自由存储区,就是那些由malloc等分配的内存块,他和堆是十分相似的,不过它是用free来结束自己的生命的。
全局/静态存储区,全局变量和静态变量被分配到同一块内存中,在以前的C语言中,全局变量又分为初始化的和未初始化的,在C++里面没有这个区分了,他们共同占用同一块内存区。
常量存储区,这是一块比较特殊的存储区,他们里面存放的是常量,不允许修改(当然,你要通过非正当手段也可以修改,而且方法很多.

栈和队列是两种特殊的线性表,它们的逻辑结构和线性表相同,只是其运算规则较线性表有更多的限制,故又称它们为运算受限的线性表。栈和队列被广泛应用于各种程序设计中。 栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出(LastInFirstOut)的线性表,简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前栈中最新的元素,即最后插入(进栈)的元素,而最先插入的是被放在栈的底部,要到最后才能删除
【示例】元素是以a1,a2,…,an的顺序进栈,退栈的次序却是an,an-1,…,a1。 (1)InitStack(S)
构造一个空栈S。
(2)StackEmpty(S)
判栈空。若S为空栈,则返回TRUE,否则返回FALSE。
(3)StackFull(S)
判栈满。若S为满栈,则返回TRUE,否则返回FALSE。
注意:
该运算只适用于栈的顺序存储结构。
(4)Push(S,x)
进栈。若栈S不满,则将元素x插入S的栈顶。
(5)Pop(S)
退栈。若栈S非空,则将S的栈顶元素删去,并返回该元素。
(6)StackTop(S)
取栈顶元素。若栈S非空,则返回栈顶元素,但不改变栈的状态。
顺序栈
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
1、顺序栈的类型定义
#defineStackSize100//假定预分配的栈空间最多为100个元素
typedefcharDataType;//假定栈元素的数据类型为字符
typedefstruct{
DataTypedata[StackSize];
inttop;
}SeqStack;
注意:
①顺序栈中元素用向量存放
②栈底位置是固定不变的,可设置在向量两端的任意一个端点
③栈顶位置是随着进栈和退栈操作而变化的,用一个整型量top(通常称top为栈顶指针)来指示当前栈顶位置
2、顺序栈的基本操作
前提条件:
设S是SeqStack类型的指针变量。若栈底位置在向量的低端,即S->data[0]是栈底元素。
(1)进栈操作
进栈时,需要将S->top加1
注意:
①S->top==StackSize-1表示栈满
②上溢现象--当栈满时,再做进栈运算产生空间溢出的现象。
上溢是一种出错状态,应设法避免。
(2)退栈操作
退栈时,需将S->top减1
注意:
①S->toptop=-1;
}
(2)判栈空
intStackEmpty(SeqStack*S)
{
returnS->top==-1;
}
(3)判栈满
intStackFull(SeqStack*SS)
{
returnS->top==StackSize-1;
}
(4)进栈
voidPush(S,x)
{
if(StackFull(S))
Error(Stackoverflow);//上溢,退出运行
S->data[++S->top]=x;//栈顶指针加1后将x入栈
}
(5)退栈
DataTypePop(S)
{
if(StackEmpty(S))
Error(Stackunderflow);//下溢,退出运行
returnS->data[S->top--];//栈顶元素返回后将栈顶指针减1
}
(6)取栈顶元素
DataTypeStackTop(S)
{
if(StackEmpty(S))
Error(Stackisempty);
returnS->data[S->top];
}
4、两个栈共享同一存储空间
当程序中同时使用两个栈时,可以将两个栈的栈底设在向量空间的两端,让两个栈各自向中间延伸。当一个栈里的元素较多,超过向量空间的一半时,只要另一个栈的元素不多,那么前者就可以占用后者的部分存储空间。
只有当整个向量空间被两个栈占满(即两个栈顶相遇)时,才会发生上溢。因此,两个栈共享一个长度为m的向量空间和两个栈分别占用两个长度为└m/2┘和┌m/2┐的向量空间比较,前者发生上溢的概率比后者要小得多。
链栈
栈的链式存储结构称为链栈。
1、链栈的类型定义
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
链栈的类型说明如下:
typedefstructstacknode{
DataTypedata
structstacknode*next
}StackNode;
typedefstruct{
StackNode*top;//栈顶指针
}LinkStack;
注意:
①LinkStack结构类型的定义是为了方便在函数体中修改top指针本身
②若要记录栈中元素个数,可将元素个数属性放在LinkStack类型中定义。
2、链栈的基本运算
(1)置栈空
VoidInitStack(LinkStack*S)
{
S->top=NULL;
}
(2)判栈空
intStackEmpty(LinkStack*S)
{
returnS->top==NULL;
}
(3)进栈
voidPush(LinkStack*S,DataTypex)
{//将元素x插入链栈头部
StackNode*p=(StackNode*)malloc(sizeof(StackNode));
p->data=x;
p->next=S->top;//将新结点*p插入链栈头部
S->top=p;
}
(4)退栈
DataTypePop(LinkStack*S)
{
DataTypex;
StackNode*p=S->top;//保存栈顶指针
if(StackEmpty(S))
Error(Stackunderflow.);//下溢
x=p->data;//保存栈顶结点数据
S->top=p->next;//将栈顶结点从链上摘下
free(p);
returnx;
}
(5)取栈顶元素
DataTypeStackTop(LinkStack*S)
{
if(StackEmpty(S))
Error(Stackisempty.)
returnS->top->data;
}
注意:
链栈中的结点是动态分配的,所以可以不考虑上溢,无须定义StackFull运算。



栈有哪些运算?
栈的基本运算包括如下:1、入栈运算 入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1),然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈上溢错误。2、退栈运算 退栈是指取出栈顶...

求计算机C语言中“栈”的基本概念,希望各个方面都有,全一点。最好和教 ...
1、进栈(PUSH)算法 ①若TOP≥n时,则给出溢出信息,作出错处理(进栈前首先检查栈是否已满,满则溢出;不满则作②); ②置TOP=TOP+1(栈指针加1,指向进栈地址); ③S(TOP)=X,结束(X为新进栈的元素); 2、退栈(POP)算法 ①若TOP≤0,则给出下溢信息,作出错处理(退栈前先检...

堆栈和队列之栈的定义及基本运算
栈的定义 栈(Stack) 是限制仅在表的一端进行插入和删除运算的线性表 通常称插入 删除的这一端为栈顶(Top) 另一端称为栈底(Bottom) 栈的修改是按后进后出的原则进行的 因此 栈又称为后进先出(Last In First Out)的线性表 简称为 LIFO表 栈的基本运算 lishixinzhi\/Article\/program\/sjjg...

基本运算的栈的定义及基本运算
栈(Stack)是限制仅在表的一端进行插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶(Top),另一端称为栈底(Bottom)。(2)当表中没有元素时称为空栈。(3)栈为后进先出(LastInFirstOut)的线性表,简称为LIFO表。栈的修改是按后进先出的原则进行。每次删除(退栈)的总是当前...

栈的基本运算包括哪些?
栈(Stack)是一种后进先出(Last In First Out,LIFO)的数据结构,它是程序设计中常用的一种数据结构。栈的基本运算包括以下几种:入栈(Push):将一个元素压入栈中,使其成为新的栈顶元素。出栈(Pop):将栈顶元素弹出栈,使次栈顶元素成为新的栈顶元素。获取栈顶元素(Top):获取当前栈顶...

计算机二级中的栈是什么意思
栈的基本运算有三种:入栈、退栈与读栈顶元素。(1)入栈运算:入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1),然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈"上溢"错误。(2)...

关栈栈的概念及运算
为了更深入地理解栈的运算,以下是常见的栈操作与定义:1. inistack(S):此操作用于初始化栈S,使其成为一个空栈。在编程语言中,这通常通过定义一个空列表、数组或其他数据结构来实现。2. getTop(S):此函数返回栈S中的栈顶元素,即最近被插入但尚未被移除的元素。在数据结构中,栈顶元素是访问...

什么是运算符栈?
定义:运算符栈s,操作数栈c 读3+,+压入栈s,3压入栈c;读5*7,*压入栈s,5压入栈c,7压入栈c;读-,*运算顺序高于+-,取栈c中的7和5,取栈s中的*,计算5*7=35,35压入栈c,-压入栈s;读4,压入栈c,读取完;取栈c中的4和35,取栈s中的-,计算35-4=31,取栈c中的3...

栈是什么意思
一、栈的基本定义 栈是一种遵循特定数据操作规则的线性数据结构,其规则是“后进先出”。这意味着最后一个被放入栈的元素总是第一个被取出。想象一下一摞盘子,我们每次都是在顶端放新的盘子,取走也是取最顶端的盘子,这就是栈的一个直观表现。二、栈的主要操作 栈的主要操作包括入栈和出栈。入栈...

栈能够进行哪些操作这些操作如何实
栈的基本运算有三种:入栈、退栈与读栈顶元素。入栈运算入栈运算是指在栈顶位置插入一个新元素。这个运算有两个基本操作:道德将栈顶指针进一(即top加1),然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为...