首页 > 正文

栈（计算机术语）

次浏览 | 2023.06.01 08:58:41 更新

来源：互联网

精选百科

本文由作者推荐

栈

计算机术语

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

中文名

栈

外文名

stack

别名

栈帧

种类

数据结构

堆栈帧

函数的返回地址和参数

基本概念

要搞清楚这个概念，首先要明白”栈“原来的意思，如此才能把握本质。栈,存储货物或供旅客住宿的地方,可引申为仓库、中转站，所以引入到计算机领域里，就是指数据暂时存储的地方，所以才有进栈、出栈的说法。

首先，系统或者数据结构栈中数据内容的读取与插入（压入）push和弹出pop是两回事。压入是增加数据，弹出是删除数据，这些操作只能从栈顶即最低地址作为约束的接口界面入手操作，但读取栈中的数据是随便的，没有接口约束之说。很多人都误解这个理念从而对栈产生困惑。而系统栈在计算机体系结构中又起到一个跨部件交互的媒介区域的作用即 cpu 与内存的交流通道，cpu只从系统给我们自己编写的应用程序所规定的栈入口线性地读取执行指令，用一个形象的词来形容它就是pipeline（管道线、流水线）。cpu内部交互具体参见 EU与BIU的概念介绍。

栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照后进先出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

栈可以用来在函数调用的时候存储断点，做递归时要用到栈。

以上定义是在经典计算机科学中的解释。

在计算机系统中，栈则是一个具有以上属性的动态内存区域。程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中，栈顶由称为esp的寄存器进行定位。压栈的操作使得栈顶的地址减小，弹出的操作使得栈顶的地址增大。

栈在程序的运行中有着举足轻重的作用。最重要的是栈保存了一个函数调用时所需要的维护信息，这常常称之为堆栈帧或者活动记录。堆栈帧一般包含如下几方面的信息：

1．函数的返回地址和参数

2．临时变量：包括函数的非静态局部变量以及编译器自动生成的其他临时变量。

基本算法

1．进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；

②置TOP=TOP+1（栈指针加1，指向进栈地址）；

③S(TOP)=X，结束（X为新进栈的元素）；

2．退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，空则下溢；不空则作②)；

②X=S(TOP)，（退栈后的元素赋给X）：

③TOP=TOP-1，结束（栈指针减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++代码

#include <iostream>
using namespace std;
class SqStack
{
private:
enum { MaxSize = 100 };
int data[MaxSize];
int top;
public:
SqStack();
~SqStack();
bool isEmpty();
void pushint(int x);
int popint();
int getTop();
void display();
};
SqStack::SqStack()
{
top = -1;
}
SqStack::~SqStack() {}
bool SqStack::isEmpty() //判断栈为空
{
return(top == -1);
}
void SqStack::pushint(int x)//元素进栈
{
if (top == MaxSize - 1)
{
cout << "栈上溢出！" << endl;
}
else
{
++top;
data[top] = x;
}
}
int SqStack::popint()//退栈
{
int tmp = 0;
if (top == -1)
{
cout << "栈已空！" <<endl;
}
else
{
tmp = data[top--];
}
return tmp;
}
int SqStack::getTop()//获得栈顶元素
{
int tmp = 0;
if (top == -1)
{
cout << "栈空！" << endl;
}
else
{
tmp = data[top];
}
return tmp;
}
void SqStack::display()//打印栈里元素
{
cout << "栈中元素：" << endl;
for (int index = top; index >= 0; --index)
{
cout << data[index] << endl;
}
}
int main()
{
SqStack st;
cout << "栈空：" << st.isEmpty() << endl;
for (int i = 1; i < 10; i++)
{
st.pushint(i);
}
st.display();
cout << "退一次栈" << endl;
st.popint();
cout << "栈顶元素:" << st.getTop() << endl;
st.popint();
st.display();
return 0;
}

C代码

#include <stdio.h>
#include <malloc.h>
#define DataType int
#define MAXSIZE 1024
typedef struct{
DataType data[MAXSIZE];
int top;
}SeqStack;
SeqStack* Init_SeqStack(){ //栈初始化
SeqStack* s;
s = (SeqStack*)malloc(sizeof(SeqStack));
if(!s){
printf("空间不足 ");
return NULL;
}else{
s->top = -1;
return s;
}
}
int Empty_SeqStack(SeqStack* s){ //判栈空
if(s->top == -1)
return 1;
else
return 0;
}
int Push_SeqStack(SeqStack* s, DataType x){ //入栈
if(s->top == MAXSIZE - 1)
return 0;//栈满不能入栈
else{
s->top++;
s->data[s->top] = x;
return 1;
}
}
int Pop_SeqStack(SeqStack* s, DataType* x){ //出栈
if(Empty_SeqStack(s))
return 0;//栈空不能出栈
else{
*x = s->data[s->top];
s->top--;
return 1;
}//栈顶元素存入*x，返回
}
DataType Top_SeqStack(SeqStack* s){ //取栈顶元素
if(Empty_SeqStack(s))
return 0;//栈空
else
return s->data[s->top];
}
int Print_SeqStack(SeqStack* s){
int i;
printf("当前栈中的元素: ");
for(i = s->top; i >= 0; i--)
printf("%3d", s->data[i]);
printf(" ");
return 0;
}
int main(){
SeqStack* L;
int n, num, m;
int i;
L = Init_SeqStack();
printf("初始化完成 ");
printf("栈空：%d ", Empty_SeqStack(L));
printf("请输入入栈元素个数： ");
scanf("%d", &n);
printf("请输入要入栈的%d个元素： ", n);
for(i = 0; i < n; i++){
scanf("%d", &num);
Push_SeqStack(L, num);
}
Print_SeqStack(L);
printf("栈顶元素：%d ", Top_SeqStack(L));
printf("请输入要出栈的元素个数（不能超过%d个）： ", n);
scanf("%d", &n);
printf("依次出栈的%d个元素： ", n);
for(i = 0; i < n; i++){
Pop_SeqStack(L, &m);
printf("%3d", m);
}
printf(" ");
Print_SeqStack(L);
printf("栈顶元素：%d ", Top_SeqStack(L));
return 0;
}

定义stack的简单代码：

stack<int> sta;
入栈：sta.push(x);
出栈：sta.pop();
判断栈的大小： sta.size();
判断栈是否为空：sta.empty();

参考资料

1.·

栈相关的文章

威廉·福克纳（美国作家）

出身名门望族，全名威廉·卡斯伯特·福克纳。支配这个家族想象力的是福克纳的曾祖父威廉·克拉科·福克纳老上校。他既是种植园主，又是军人、作家、政治家。他还是经营铁路的企业家，他修的铁路是当地惟一的铁路。牛津小镇留下老上校鲜明的痕迹。老上校死后，坟头矗立着一座8英尺高的意大利大理石雕像。

流年明媚·相思谋（桩桩所著的古代言情小说）

《流年明媚·相思谋》作者桩桩，2010年1月由凤凰出版传媒集团、江苏文艺出版社出版的图书。

网络游戏（联网进行的多人电子游戏）

网络游戏，英文名称为Online Game，又称 “在线游戏”，简称“网游”。指以互联网为传输媒介，以游戏运营商服务器和用户计算机为处理终端，以游戏客户端软件为信息交互窗口的旨在实现娱乐、休闲、交流和取得虚拟成就的具有可持续性的个体性多人在线游戏。

三江侗族自治县（广西壮族自治区柳州市下辖县）

三江侗族自治县隶属于广西壮族自治区柳州市，位于广西壮族自治区北部，地处东经108°53′～109°52′，北纬25°22′～26°2′，是湘、桂、黔三省（区）交界地，属于亚热带南岭湿润气候区，山地谷地气候区。

授权（将完成某项工作所必须的权力授给部属人员）

授权意味着在上下级之间建立起某种形式的职权关系

直尺（用来测量长度和作图的工具）

直尺也有人称为间尺，具有精确的直线棱边，用来测量长度和作图。广泛应用于数学、测量、工程等学科。

冷轧钢（经过冷轧生产的钢）

冷轧是在室温条件下将No.1钢板进一步轧薄至为目标厚度的钢板。和热轧钢板比较，冷轧钢板厚度更加精确，而且表面光滑、漂亮，同时还具有各种优越的机械性能，特别是加工性能方面。因为冷轧原卷比较脆硬，不太适合加工，所以通常情况下冷轧钢板要求经过退火、酸洗及表面平整之后才交给客户。冷轧最大厚度是0.1--8.0MM以下，如大部分工厂冷轧钢板厚度是4.5MM以下；最少厚度、宽度是根据各工厂的设备能力和市场需求而决定。

张伦（山东省菏泽市委书记、市长）

张伦，男，汉族，1969年11月生，山东枣庄人，1992年7月参加工作，1991年5月加入中国共产党，北京大学城市与环境学系经济地理学专业毕业，大学学历，理学学士。

敢死连（维亚切斯拉夫·尼基福罗夫执导的战争电影）

《敢死连》由俄罗斯政府投四亿巨资全力支持！动用了两个师的军队，5000名军人，300百辆坦克，200架飞机参与拍摄，壮烈再现二战最后的大反击中最为悲壮惨烈的“高加索平原”大血战。同时，本片也是俄罗斯历史上最大投资的新型战争影片，借以恢复其战争影片生产强国的地位。影片阵容强大，《守夜人》、《土耳其开局》、《血影迷城》三部影片中的主力演员加盟浴血演绎。该片一举夺得俄罗斯奥斯卡金鹰奖，俄罗斯尼卡国际影展大奖等多项荣誉。

乌梢蛇（中药）

乌梢蛇，中药名。为游蛇科乌梢蛇属动物乌梢蛇Zaocys dhumnades（Cantor）除去内脏的全体。动物乌梢蛇，分布于我国陕西、甘肃、江苏、安徽、浙江、江西、福建、河南、湖北、湖南、广东、广西、四川、贵州。具有祛风湿，通经络，止痉之功效。主治风湿顽痹，肌肤麻木，筋脉拘挛，肢体瘫痪，破伤风，麻风，风疹疥癣。