一、什么是棧，什么是FILO
? 棧是一種具有特殊訪問方式的存儲空間，它的特殊性在于，最后進(jìn)入這個空間的數(shù)據(jù)，最先出去，可以畫圖來描述一下這種操作方式。
假設(shè)有一個盒子和三本書，依次將三本書他們放入盒子中。
入棧模擬圖
? 現(xiàn)在有一個問題，如果一次只能取一本，我們?nèi)绾螌鴱暮凶又腥〕鰜恚?/p>
? 顯然必須從盒子的最上邊開始取，依次取出，和放入的順序剛好相反。
出棧模擬圖
? 從程序化的角度來講，應(yīng)該有一個標(biāo)記，這個標(biāo)記一直指示著盒子最上邊的書。
? 如果說，上圖中的盒子就是一個棧，我們可以看出棧的兩個基本操作：入棧和出棧。入棧就是將一個新元素放到棧頂，出棧就是從棧頂取出一個元素，棧頂?shù)脑乜偸亲詈笕霔?，需要出棧時，有最先被從棧中取出。棧的這種操作被稱為：LIFO（last in first out），后進(jìn)先出
二、棧的作用是什么，為什么編程語言函數(shù)調(diào)用都選擇用棧？
? 為何現(xiàn)如今所有的編程語言都會采用棧來進(jìn)行函數(shù)調(diào)用？函數(shù)調(diào)用的狀態(tài)之所以用棧來記錄是因為這些數(shù)據(jù)的存活時間滿足“先進(jìn)后出”（FILO）順序，而棧的基本操作正好就是支持這種順序訪問的。下面用一組程序舉例。
void test1(){}
void test2() {
test1();
}
void test3() {
test2();
}
int main() {
test3();
}
這個程序運行的順序為：main() ——》 test3() ——》 test2() ——》 test1() ——》 return from test1() ——》 return from test2() ——》 return from test3() ——》 return from test4().
? 可以看到，調(diào)用者的生命周期總是長于被調(diào)用者的生命周期，并且后者在前者之內(nèi)。被調(diào)用者的數(shù)據(jù)總是后于調(diào)用者的，而其釋放順序總是先于調(diào)用者，所以正好可以滿足LIFO順序，選用棧這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)函數(shù)調(diào)用則是一種自然而然的選擇。
三、使用C模擬實現(xiàn)解析棧
? 前面說過棧的兩個基本操作，入棧和出棧，都只是對棧頂進(jìn)行操作，?？梢杂脭?shù)組實現(xiàn)也可以用鏈表實現(xiàn)，這里講解用數(shù)組實現(xiàn)，因為數(shù)組實現(xiàn)相對來說更優(yōu)一些，數(shù)組實現(xiàn)在尾部插入數(shù)據(jù)代價比較小。
1.結(jié)構(gòu)體的定義
? 由于各種操作都只在棧頂進(jìn)行，選擇定義一個top來記錄棧頂?shù)奈恢?，為了?jié)省空間選擇定義一個capacity來記錄最大長度，如果等于top的話進(jìn)行擴(kuò)容。
typedef int STDataType;
typedef struct StackNode {
STDataType* arr;
int capacity;
int top;
}STNode;
2.棧的創(chuàng)建及銷毀
? 由于函數(shù)內(nèi)有對參數(shù)指針的引用，加上assert預(yù)防程序崩潰，易于調(diào)試，top初始化為-1（也可以初始化為0,個人偏向初始化為-1），兩者的區(qū)別就是一個是棧頂指向棧頂數(shù)據(jù)，一個指向棧頂數(shù)據(jù)的下一個，其實本質(zhì)上差不多。
void STInit(STNode* pst)
{
assert(pst);
pst->arr = NULL;
pst->capacity = 0;
pst->top = -1;
}
void STDestroy(STNode* pst)
{
assert(pst);
free(pst->arr);
pst->arr = NULL;
pst->capacity = 0;
pst->top = 0;
}
3.實現(xiàn)入棧操作
? 如果棧已經(jīng)滿了，則進(jìn)行擴(kuò)容，將數(shù)據(jù)放到棧頂。
void STPush(STNode* pst,STDataType x)
{
assert(pst);
if (pst->capacity==pst->top+1)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* temp = NULL;
temp = (STDataType*)realloc(pst->arr,sizeof(STDataType) * newcapacity);
if (temp == NULL)
{
perror("malloc error");
return;
}
pst->arr = temp;
pst->capacity = newcapacity;
}
pst->arr[++pst->top] = x;
}
4.獲取棧頂元素及出棧操作
? 出棧操作將棧頂元素向下移動即可，甚至無需刪除數(shù)據(jù)，因為再次進(jìn)行入棧會將其覆蓋掉。獲取棧頂元素要獲取top的下一個位置，因為top是先存后加。
bool STEmpty(STNode* pst)
{
return pst->top == -1;
}
void STPop(STNode* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(STNode* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->arr[pst->top];
}
5.獲取棧中有效元素個數(shù)
由于數(shù)組偏移度是從0開始存數(shù)據(jù)，所以指向棧頂?shù)膖op比實際上個數(shù)要少1，真正有效元素個數(shù)要將top+1。
int StackSize(STNode* pst)
{
assert(pst);
return pst->top+1;
}
源代碼分享
//stack.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct StackNode {
STDataType* arr;
int capacity;
int top;
}STNode;
void STInit(STNode* pst);
void STPush(STNode* pst,STDataType);
void STPop(STNode* pst);
void STDestroy(STNode* pst);
bool STEmpty(STNode* pst);
STDataType STTop(STNode* pst);
//stack.c
#include "stack.h"
bool STEmpty(STNode* pst)
{
return pst->top == -1;
}
void STInit(STNode* pst)
{
assert(pst);
pst->arr = NULL;
pst->capacity = 0;
pst->top = -1;
}
void STDestroy(STNode* pst)
{
assert(pst);
free(pst->arr);
pst->arr = NULL;
pst->capacity = 0;
pst->top = 0;
}
void STPush(STNode* pst,STDataType x)
{
assert(pst);
if (pst->capacity==pst->top+1)
{
int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* temp = NULL;
temp = (STDataType*)realloc(pst->arr,sizeof(STDataType) * newcapacity);
if (temp == NULL)
{
perror("malloc error");
return;
}
pst->arr = temp;
pst->capacity = newcapacity;
}
pst->arr[++pst->top] = x;
}
void STPop(STNode* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(STNode* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->arr[pst->top];
}
int StackSize(STNode* pst)
{
assert(pst);
return pst->top+1;
}
//test.c
#include "stack.h"
void test1()
{
STNode ST;
STInit(&ST);
STPush(&ST, 1);
STPush(&ST, 2);
STPush(&ST, 3);
STPush(&ST, 4);
STPush(&ST, 5);
STPush(&ST, 6);
STPush(&ST, 7);
while (!STEmpty(&ST))
{
printf("%d ", STTop(&ST));
STPop(&ST);
}
STDestroy(&ST);
}
int main()
{
test1();
}
?本文收錄于數(shù)據(jù)結(jié)構(gòu)理解與實現(xiàn)文章來源：http://www.zghlxwxcb.cn/news/detail-457591.html
下幾期會繼續(xù)帶來棧的練習(xí)題以及與棧剛好相反的堆（FIFO）。如果文章對你有幫助記得點贊收藏關(guān)注。文章來源地址http://www.zghlxwxcb.cn/news/detail-457591.html
到了這里，關(guān)于什么是棧，為什么函數(shù)式編程語言都離不開棧？的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
