一. 棧的基本概念??
棧是一種特殊的線性表。其只允許在固定的一端進(jìn)行插入和刪除元素的操作，進(jìn)行數(shù)據(jù)的插入和刪除的一端稱作棧頂，另外一端稱作棧底。棧不支持隨機(jī)訪問，棧的數(shù)據(jù)元素遵循后進(jìn)先出的原則，即LIFO（Late In First Out）。
也許有人曾經(jīng)聽說過壓棧和入棧的術(shù)語，以下是它們的定義：
壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，插入數(shù)據(jù)是在棧頂
出棧：棧的刪除操作叫做出棧/彈棧，刪除數(shù)據(jù)也是在棧頂
我們結(jié)合動圖來理解棧的后進(jìn)先出：
二. 棧實(shí)現(xiàn)方法的分析與選擇??
2.1 引入
我們可以使用順序存儲結(jié)構(gòu)或者鏈?zhǔn)酱鎯Y(jié)構(gòu)來實(shí)現(xiàn)棧。換句話來說，我們可以使用之前學(xué)習(xí)過的順序表或者鏈表來實(shí)現(xiàn)棧，它們各自有自己的優(yōu)缺點(diǎn)，下面我們就來分析分析。
2.2 用順序表來實(shí)現(xiàn)
以下是動態(tài)順序表實(shí)現(xiàn)棧的結(jié)構(gòu)體聲明和圖示：
typedef struct StackList
{
STDataType* a; //指向動態(tài)開辟的空間
int top; //棧頂所在下標(biāo)，相當(dāng)于元素個數(shù)
int capacity;//順序表容量
}ST;
優(yōu)點(diǎn)：由于棧的插入和刪除數(shù)據(jù)符合 后進(jìn)先出的原則，我們 把順序表末端當(dāng)作棧頂，則插入數(shù)據(jù)和刪除數(shù)據(jù)就是 尾插和 尾刪 。而前面我們知道 順序表的尾插和尾刪效率非常高 ，時間復(fù)雜度為O（1）。
缺點(diǎn)： 存在容量限制，當(dāng)容量不足是需要擴(kuò)容，擴(kuò)容需要成本。
2.3 用鏈表來實(shí)現(xiàn)
2.3.1 單鏈表實(shí)現(xiàn)(尾為棧頂)
typedef struct StackNode
{
STDataType x;//數(shù)據(jù)域
StackNode* nest;//指針域，指向下一結(jié)點(diǎn)
}ST;
struct Stack
{
ST* phead;//指向第一個結(jié)點(diǎn)
ST* tail;//指向尾結(jié)點(diǎn)
}
假如我們使用鏈表尾當(dāng)作棧頂，則對應(yīng)的插入刪除就是尾插和尾刪。我們知道單鏈表的尾插和尾刪要先找到鏈表尾，時間復(fù)雜度是O(N)?？赡苡腥藭?，那我定義一個尾指針來記錄鏈表尾部，想法很好，但是這樣雖然解決了尾插效率低的問題，但是尾刪除了要找到最后一個結(jié)點(diǎn)，還要找到其前面的結(jié)點(diǎn)，由于鏈表單向，最終還是要遍歷鏈表，沒有什么意義。
2.3.2 單鏈表實(shí)現(xiàn)(頭為棧頂)
我們知道，和順序表相反，單鏈表頭插和頭刪效率較高，時間復(fù)雜度為O（1）。我們就可以將鏈表頭當(dāng)作棧頂，這樣插入就相當(dāng)于頭插，刪除就相當(dāng)于頭刪，如下：
2.3.3 雙向鏈表實(shí)現(xiàn)
如果一定要使用鏈表以及把鏈表尾當(dāng)作棧頂，為了解決刪除需要找到尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)時間效率低的問題，我們可以用雙向鏈表來實(shí)現(xiàn)棧。雙向鏈表除了后繼指針還增加了前驅(qū)指針來指向上一個結(jié)點(diǎn)，利用這個結(jié)構(gòu)可以直接得到上一個結(jié)點(diǎn)，無需再遍歷鏈表，時間復(fù)雜度為O（1）。
typedef struct StackNode
{
STDataType x;//數(shù)據(jù)域
StackNode* nest;//后繼指針域，指向下一結(jié)點(diǎn)
StackNode* prev;//前驅(qū)指針域，指向上一結(jié)點(diǎn)
}ST;
struct Stack
{
ST* phead;//指向第一個結(jié)點(diǎn)
ST* tail;//指向尾結(jié)點(diǎn)
}
2.3.4 總結(jié)
如果 沒有要求棧頂?shù)奈恢?/span>，則我們還是使用 單鏈表來實(shí)現(xiàn)，將頭作為棧頂。這是因?yàn)? 雙向鏈表比單鏈表的結(jié)點(diǎn)多占用了一個前驅(qū)指針的空間，雖然現(xiàn)代計(jì)算機(jī)空間已然構(gòu)不成太大問題，但是能省則省，大伙們懂的 ??。
如果題目要求棧頂在鏈表尾的話，那還是老老實(shí)實(shí)用 雙向鏈表實(shí)現(xiàn)吧。
使用鏈表的缺點(diǎn)就是每次插入都要malloc新結(jié)點(diǎn)，會消耗一定的時間成本。
2.4 選擇
我們推薦采用 順序表來實(shí)現(xiàn)對棧的操作，原因如下：
1. 棧的特性完美利用了順序表尾插尾刪效率高的特性，雖然需要擴(kuò)容，但是鏈表創(chuàng)建結(jié)點(diǎn)也同樣需要成本，而 順序表擴(kuò)容頻率不像鏈表一樣如此頻繁。
2. 我們知道CPU與主存速度上存在巨大差距，為了提高效率，CPU和主存之間還存在著 cache高速緩存。 CPU訪問cache的速度是快于主存的。每次CPU取數(shù)據(jù)時會訪問cache看看存不存在所需的數(shù)據(jù)，如果不存在才會訪問主存，然后將數(shù)據(jù)所在的內(nèi)存塊加載到cache中。由于順序表空間是連續(xù)的，根據(jù)cache的 空間局部性原理，采用順序表 cache的命中率會高于鏈表，效率高。
三. 接口的實(shí)現(xiàn)?
3.1 棧的聲明
本文我們采用動態(tài)順序表來實(shí)現(xiàn)棧，結(jié)構(gòu)體的聲明如下：
typedef int STDataType;
typedef struct StackList
{
STDataType* a;//指向動態(tài)開辟的空間
int top; //棧頂所在下標(biāo)，相當(dāng)于元素個數(shù)
int capacity;//棧的容量
}ST;和前面鏈表順序表一樣，我們不直接指定數(shù)據(jù)的類型，而是將類型重定義為STDataType，這樣做有利于提高代碼的可維護(hù)性。
3.2 初始化和銷毀
和其他數(shù)據(jù)結(jié)構(gòu)一樣，當(dāng)我們使用棧結(jié)構(gòu)之前需要對其進(jìn)行初始化，當(dāng)我們不再使用它是要對它進(jìn)行銷毀，具體代碼如下：
//初始化棧
void StackInit(ST* ps) //需要改變實(shí)參，傳指針
{
assert(ps);//確保傳入的指針不為空
ps->a = (STDataType*)malloc(4 * sizeof(STDataType));//起初先分配四個字節(jié)空間
ps->capacity = 4;
ps->top = 0;
}
//銷毀棧
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);//將?？臻g釋放掉
//將棧結(jié)構(gòu)中的信息清空
ps->capacity = 0;
ps->top = 0;
ps->a = NULL;
}3.3 入棧
由于棧只允許在固定的一端插入，我們又將末端當(dāng)作棧頂，因此入棧就是尾插。而順序表的尾插我們已經(jīng)很清楚了，往棧頂所在下標(biāo)放入數(shù)據(jù)，然后棧頂下標(biāo)加1即可。效果和代碼如下：
//入棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity) //元素個數(shù)等于容量，棧滿了，先擴(kuò)容
{
STDataType* temp = (STDataType*)realloc(ps->a, 2 * ps->capacity*sizeof(STDataType));
if (temp == NULL)//失敗則退出程序
{
printf("擴(kuò)容失敗\n");
exit(-1);
}
else
{
ps->a = temp;
ps->capacity *= 2;
temp = NULL;
}
}
(ps->a)[ps->top] = x;//入棧
(ps->top)++;//更新棧頂位置
}3.4 出棧
和入棧一樣，出棧也只在固定的一端進(jìn)行。入棧是尾插，則出棧就是尾刪。而我們用順序表來實(shí)現(xiàn)棧，因此尾刪只需要將棧頂退后一位即可。
這里有人可能會將棧頂?shù)脑刂?然后再將棧頂位置后退一位。實(shí)際上這種方法并不可取，有以下兩種原因：
1. 如果棧頂?shù)脑乇旧砭褪?，那我們的行為就失去了意義。
2. 棧的元素類型不一定是整形，如果是浮點(diǎn)型或者結(jié)構(gòu)體，我們賦值為0顯然是不妥的。
//出棧
void StackPop(ST* ps)
{
assert(ps);//確保傳入指針不為空
assert(ps->top);//確保棧存在元素
(ps->top)--;//更新棧頂
}3.5 求棧頂元素
很簡單，我們可以直接根據(jù)棧頂所在的下標(biāo)得到棧頂元素，如下：
//求棧頂元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top);//確保棧中存在元素
return ps->a[ps->top - 1];//棧頂元素所在下標(biāo)即為top-1
}3.6 判空
在我們設(shè)計(jì)的棧結(jié)構(gòu)中，top實(shí)際上就等價于元素個數(shù)，通過判斷top是否為0就可以知道棧是否為空。我們使用了C語言stdbool.h頭文件中的bool類型，其只能用來存放true(1)和false(0)兩個值，分別代表真和假。代碼如下：
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top;//top為0則返回false，不為零返回true
}3.7 求棧的元素個數(shù)
根據(jù)我們構(gòu)造的棧結(jié)構(gòu)體，棧頂top的值就是棧的元素個數(shù)，直接返回即可：
//求棧的元素個數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}3.8 思考
會不會有人會有以下思考：
1. 求棧頂元素，判空，求元素個數(shù)都是用一行直接返回，這些接口會不會有些許多余，直接訪問結(jié)構(gòu)體相應(yīng)成員不就好了？
2. 為什么沒有實(shí)現(xiàn)查找，打印，修改等接口？
下面我們來分析一下：
我們要知道，數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方式多種多樣，在本文我們將棧元素個數(shù)作為棧頂?shù)南聵?biāo)，那可不可以將最后一個元素的下標(biāo)作為棧頂下標(biāo)呢？實(shí)際上完全可以。那么就會出現(xiàn)一個問題，如果我們使用別人已經(jīng)封裝好的棧，我們要怎么知道棧頂元素下標(biāo)是top還是top-1呢？我們要怎么知道是top=0為空還是top=-1為空呢？我們要怎么知道元素個數(shù)是top還是top+1呢？我們完全不知道，只有設(shè)計(jì)者才知道，因此設(shè)計(jì)者往往會將這些功能再封裝成函數(shù)，供我們直接調(diào)用。
這是因?yàn)?span id="n5n3t3z" class="kdocs-color" style="background-color:#FBF5B3;">棧是一種限制型數(shù)據(jù)結(jié)構(gòu)，其不支持隨機(jī)訪問，只允許在固定的一端(棧頂)進(jìn)行插入和刪除操作，不允許在其他的位置進(jìn)行任何操作。因此，棧不存在查找，打印，修改等對除棧頂之外的位置進(jìn)行操作的接口，否則會破壞棧的特性。為了遵循棧的特性，我們就不實(shí)現(xiàn)這些接口。
四. 完整代碼及效果展示??
按照以往慣例，我們采用多文件編寫的形式，將上述接口的定義實(shí)現(xiàn)放在Stack.c文件中，然后將接口的聲明和結(jié)構(gòu)體的定義放于Stack.h頭文件中，以達(dá)到封裝的效果。這樣我們?nèi)绻枰褂脳?，就只需要在文件中包含對?yīng)的頭文件Stack.h就可以使用我們上面定義的各種接口。以下為本文實(shí)現(xiàn)的棧完整代碼以及效果展示：
//Stack.h文件，用于聲明接口函數(shù)，定義結(jié)構(gòu)體
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct StackList
{
STDataType* a;//指向動態(tài)開辟的空間
int top; //棧頂所在下標(biāo)，相當(dāng)于元素個數(shù)
int capacity;//棧的容量
}ST;
//初始化
void StackInit(ST* ps);
//銷毀
void StackDestroy(ST* ps);
//出棧
void StackPop(ST* ps);
//入棧
void StackPush(ST* ps, STDataType x);
//求棧頂元素
STDataType StackTop(ST* ps);
//求棧元素個數(shù)
int StackSize(ST* ps);
//判空
bool StackEmpty(ST* ps);//Stack.c文件，用于定義接口函數(shù)
#include"Stack.h"
//初始化棧
void StackInit(ST* ps) //需要改變實(shí)參，傳指針
{
assert(ps);//確保傳入的指針不為空
ps->a = (STDataType*)malloc(4 * sizeof(STDataType));//起初先分配四個字節(jié)空間
ps->capacity = 4;
ps->top = 0;
}
//入棧
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity) //元素個數(shù)等于容量，棧滿了，先擴(kuò)容
{
STDataType* temp = (STDataType*)realloc(ps->a, 2 * ps->capacity * sizeof(STDataType));
if (temp == NULL)//失敗則退出程序
{
printf("擴(kuò)容失敗\n");
exit(-1);
}
else
{
ps->a = temp;
ps->capacity *= 2;
temp = NULL;
}
}
(ps->a)[ps->top] = x;//入棧
(ps->top)++;//更新棧頂位置
}
//出棧
void StackPop(ST* ps)
{
assert(ps);//確保傳入指針不為空
assert(ps->top);//確保棧存在元素
(ps->top)--;//更新棧頂
}
//求棧頂元素
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top);//確保棧中存在元素
return ps->a[ps->top - 1];//棧頂元素所在下標(biāo)即為top-1
}
//求棧的元素個數(shù)
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
//判空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top;//top為0則返回false，不為零返回true
}
//銷毀棧
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->a);//將?？臻g釋放掉
//將棧結(jié)構(gòu)中的信息清空
ps->capacity = 0;
ps->top = 0;
ps->a = NULL;
}最后， 我們在tesst.c文件調(diào)用棧各個接口進(jìn)行測試，如下：
//test.c文件，用于測試
#include"Stack.h"
void test01()
{
ST s1;
//初始化
StackInit(&s1);
//求元素個數(shù)
printf("入棧前棧的元素個數(shù)為:%d\n", StackSize(&s1));
//入棧
StackPush(&s1,1);
StackPush(&s1, 2);
StackPush(&s1, 3);
StackPush(&s1, 4);
printf("入棧后棧的元素個數(shù)為:%d\n", StackSize(&s1));
//由于無法遍歷打印，我們就交替使用 求棧頂元素-出棧 來顯示棧中元素
printf("棧中元素:> ");
while (StackEmpty(&s1))//棧不為空則繼續(xù)
{
//求棧頂元素
printf("%d ", StackTop(&s1));
//出棧
StackPop(&s1);
}
//全部出棧
printf("\n全部出棧后棧的元素個數(shù)為:%d\n", StackSize(&s1));
//銷毀
StackDestroy(&s1);
}
int main()
{
test01();
return 0;
}以下是測試的最終效果：
以上，就是本期的全部內(nèi)容啦??文章來源：http://www.zghlxwxcb.cn/news/detail-780035.html
制作不易，能否點(diǎn)個贊再走呢??文章來源地址http://www.zghlxwxcb.cn/news/detail-780035.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】帶你深入理解棧的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
