什么是栈?请说明详细一些
发布网友
发布时间：2022-04-25 17:41
共1个回答
热心网友
时间：2023-10-22 18:05
一、基本概念
栈（stack）在计算机科学中是限定仅在表尾进行插入或删除操作的线形表。
栈是一种数据结构，是只能在某一端插入和删除的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。 栈也称为后进先出表（LIFO表）。
栈可以用来在函数调用的时候存储断点，做递归时要用到栈！
栈的模型二、基本算法
1、进栈（PUSH）算法
①若TOP≥ｎ时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；
②置TOP=TOP+1（栈指针加１，指向进栈地址）；
③S(TOP)=X，结束（X为新进栈的元素）；
2、退栈（POP）算法
①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)；
②X=S(TOP)，（退栈后的元素赋给X）；
③TOP=TOP-1，结束（栈指针减１，指向栈顶）。
三、栈的实现
在pascal下的实现
1、数组型
Const
m=栈表目数的上限;
Type
stack=array[1..m] of stype; {栈类型}
Var
s:stack;{栈}
top:integer; {栈顶指针}
2、记录型
const
m=栈表目数的上限；
type
stack=record
elem: array[1..m] of elemtp;
top:0..m; {栈顶指针}
end;
Var
s:stack;{栈}
在C/C++中栈的一些基本操作:
C代码:
/*
@**2009/09/24
栈的基本操作
*/
#include <iostream>
#define MaxSize 100
using namespace std;
typedef struct
{
int data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack *st) //初始化栈
{
st->top=-1;
}
int StackEmpty(SqStack *st) //判断栈为空
{
return (st->top==-1);
}
void Push(SqStack *st,int x) //元素进栈
{
if(st->top==MaxSize-1)
printf("栈上溢出!\n");
else
{
st->top++;
st->data[st->top]=x;
}
}
void Pop(SqStack *st) //退栈
{
if(st->top==-1)
printf("栈下溢出\n");
else
st->top--;
}
int Gettop(SqStack *st) //获得栈顶元素
{
if(st->top==-1)
{
printf("栈空\n");
return 0;
}
else
return st->data[st->top];
}
void Display(SqStack *st) //打印栈里元素
{
int i;
printf("栈中元素：");
for(i=st->top;i>=0;--i)
printf("%d ",st->data[i]);
printf("\n");
}
int main()
{
SqStack L;
SqStack *st=&L;
InitStack(st);
printf("栈空：%d\n",StackEmpty(st));
for(int i=1;i<10;++i)
Push(st,i);
Display(st);
printf("退一次栈\n");
Pop(st);
printf("栈顶元素:%d\n",Gettop(st));
Pop(st);
Display(st);
return 0;
}
