反饋

棧

（計算機術語）

堆棧又名棧（stack），它是一種運算受限的線性表。限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。

中文名: 堆棧
外文名: stack

別名: 棧、棧幀
種類: 數據結構
堆棧幀: 函數的返回地址和參數

棧基本概念

要搞清楚這個概念，首先要明白“棧”原來的意思，如此才能把握本質。棧，存儲貨物或供旅客住宿的地方，可引申為倉庫、中轉站，所以引入到計算機領域裏，就是指數據暫時存儲的地方，所以才有進棧、出棧的説法。

堆棧是計算機科學中的一種抽象數據類型，只允許在有序的線性數據集合的一端（稱為堆棧頂端，top）進行插入數據（PUSH）和刪除數據（POP）的運算。^[1]

首先，系統或者數據結構棧中數據內容的讀取與插入（壓入）PUSH和刪除POP是兩回事。壓入是增加數據，彈出是刪除數據，這些操作只能從棧頂即最低地址作為約束的接口界面入手操作，但讀取棧中的數據是隨便的，沒有接口約束之説。很多人都誤解這個理念從而對棧產生困惑。而系統棧在計算機體系結構中又起到一個跨部件交互的媒介區域的作用即CPU 與內存的交流通道，CPU只從系統提供用户自己編寫的應用程序所規定的棧入口線性地讀取執行指令，用一個形象的詞來形容它就是pipeline（管道線、流水線）。CPU內部交互具體參見 EU與BIU的概念介紹。

棧作為一種數據結構，是一種只能在一端進行插入和刪除操作的特殊線性表。它按照後進先出的原則存儲數據，先進入的數據被壓入棧底，最後的數據在棧頂，需要讀數據的時候從棧頂開始彈出數據（最後一個數據被第一個讀出來）。棧具有記憶作用，對棧的插入與刪除操作中，不需要改變棧底指針。

棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為進棧（PUSH），刪除則稱為出棧/退棧（POP）。棧也稱為先進後出表。

棧可以用來在函數調用的時候存儲斷點，做遞歸時要用到棧。

以上定義是在經典計算機科學中的解釋。

在計算機系統中，棧則是一個具有以上屬性的動態內存區域。程序可以將數據壓入棧中，也可以將數據從棧頂彈出。在i386機器中，棧頂由稱為esp的寄存器進行定位。壓棧的操作使得棧頂的地址減小，彈出的操作使得棧頂的地址增大。

棧在程序的運行中有着舉足輕重的作用。最重要的是棧保存了一個函數調用時所需要的維護信息，這常常稱之為堆棧幀或者活動記錄。堆棧幀一般包含如下幾方面的信息：

1．函數的返回地址和參數

2．臨時變量：包括函數的非靜態局部變量以及編譯器自動生成的其他臨時變量。

堆棧進棧出棧示意圖

棧基本特點

堆棧的基本特點：^[1]

先入後出，後入先出。
除頭尾節點之外，每個元素有一個前驅，一個後繼。

棧基本算法

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("空間不足\n");
        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("當前棧中的元素:\n");
    for(i = s->top; i >= 0; i--)
        printf("%3d", s->data[i]);
    printf("\n");
    return 0;
}

int main(){
    SeqStack* L;
    int n, num, m;
    int i;
    
    L = Init_SeqStack();
    
    printf("初始化完成\n");
    printf("棧空：%d\n", Empty_SeqStack(L));
    printf("請輸入入棧元素個數：\n");
    scanf("%d", &n);
    printf("請輸入要入棧的%d個元素：\n", n);
    
    for(i = 0; i < n; i++){
        scanf("%d", &num);
        Push_SeqStack(L, num);
    }
    
    Print_SeqStack(L);
    
    printf("棧頂元素：%d\n", Top_SeqStack(L));
    printf("請輸入要出棧的元素個數（不能超過%d個）：\n", n);
    scanf("%d", &n);
    printf("依次出棧的%d個元素：\n", n);
    
    for(i = 0; i < n; i++){
        Pop_SeqStack(L, &m);
        printf("%3d", m);
    }
    
    printf("\n");
    Print_SeqStack(L);
    printf("棧頂元素：%d\n", Top_SeqStack(L));
    
    return 0;
}

定義stack的簡單代碼：

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

棧其他説明

堆棧是一種存儲部件，即數據的寫入跟讀出不需要提供地址，而是根據寫入的順序決定讀出的順序

形象來説，棧就是一條流水線，而流水線中加工的就是方法的主要程序，在分配棧時，由於程序是自上而下順序執行，就將程序指令一條一條壓入棧中，就像流水線一樣。而堆上站着的就是工作人員，他們加工流水線中的商品，由程序員分配：何時加工，如何加工。而我們通常使用new運算符為對象在堆上分配內存（C#），堆上尋找對象的任務交給句柄，而棧中由棧指針管理。

參考資料

1. 什麼是堆棧-常見問題-PHP中文網．PHP中文網[引用日期2023-08-26]

棧的概述圖（1張）

詞條統計

瀏覽次數：次
編輯次數：31次歷史版本
最近更新： bingher2020 （2023-11-10）

1 基本概念
2 基本特點
3 基本算法
4 實現: 4.1 pascal; 4.2 C++代碼; 4.3 C代碼
5 其他説明

棧