一.棧的定義
1.棧的定義
棧(stack)是限定僅在表尾進(jìn)行插入和刪除操作的線性表。
我們把允許插入和刪除的一段稱為棧頂(top),另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進(jìn)先出的線性表。
進(jìn)一步理解棧，棧首先他是一個(gè)線性表，所以棧元素具有前驅(qū)后繼關(guān)系。
棧的插入操作，叫做出棧，也叫壓棧、入棧。棧的刪除操作，叫做出棧，也叫彈棧。
2.進(jìn)棧出棧變化形式
在進(jìn)一步了解數(shù)據(jù)進(jìn)棧和出棧后，有個(gè)問題----最先進(jìn)棧的元素，是不是就只能是最后出棧呢。
其實(shí)不然，舉例子來說現(xiàn)在有3個(gè)整形數(shù)字元素1、2、3依次進(jìn)棧，會(huì)有那些序列呢？
第一種:1、2、3進(jìn)，再3、2、1出。這是最簡單最好理解的一種，出棧次序?yàn)?、2、1。
第二種:1進(jìn)，1出，2進(jìn)，2出，3進(jìn)，3出。也就是進(jìn)一個(gè)就出一個(gè)，出棧次序?yàn)?、2、3。
第三種:1進(jìn)，2進(jìn)，2出，1出，3進(jìn)，3出。出棧次序?yàn)?、1、3。
第四種:1進(jìn)，1出，2進(jìn)，3進(jìn)，3出，2出。出棧次序?yàn)?、3、2。
第五種:1進(jìn)，2進(jìn)，2出，3 進(jìn)，3出，1出。出棧次序?yàn)?、3、1。
有沒有可能是3、1、2這樣的次序出棧呢?答案是肯定不會(huì)。因?yàn)?先出棧，就意味著，3曾經(jīng)進(jìn)棧，既然3都進(jìn)棧了，那也就意味著，1和2已經(jīng)進(jìn)棧了，此時(shí)，2一定是在1的上面，就是更接近棧頂，那么出棧只可能是3、2、1，不然不滿足1、2、3依次進(jìn)棧的要求，所以此時(shí)不會(huì)發(fā)生1比2先出棧的情況。
從這個(gè)簡單的例子就能看出，只是3個(gè)元素，就有5種可能的出棧次序如果元素?cái)?shù)這個(gè)知識(shí)點(diǎn)一定要弄明白。
二.棧的抽象數(shù)據(jù)類型
對(duì)于棧來說，理論上線性表的操作特性他都具備，下面我們來看一下幾個(gè)需要實(shí)現(xiàn)的功能；
typedef int STDataType;
typedef int STDataType;
void InitST(ST* s);//初始化棧
void DestroyST(ST* s);//銷毀棧
void Push(ST* s, int x);//壓棧
void Pop(ST* s);//出棧
bool STEmpty(ST* s);//判斷棧是否為空棧
STDataType STSize(ST* s);//當(dāng)前棧的元素個(gè)數(shù)
STDataType STTop(ST* s);//返回棧頂元素
三.棧的順序儲(chǔ)存結(jié)構(gòu)及實(shí)現(xiàn)
1.棧的順序存儲(chǔ)結(jié)構(gòu)
棧既然是線性表的特例，那么棧的順序存儲(chǔ)其實(shí)也是線性表順序存儲(chǔ)的簡化，我們簡稱為順序棧。
typedef int STDataType;
typedef struct stack
{
STDataType* a;
STDataType top;//表示當(dāng)前指向的元素下標(biāo)
STDataType capacity;//棧的當(dāng)前容量
}ST;
(1).初始化棧
在初始化棧是指針a需要malloc個(gè)初始空間，容量則根據(jù)malloc的個(gè)數(shù)賦值。而top對(duì)的初值則有所不同，top的初值有兩種情況 一是top代表下一個(gè)元素的下標(biāo)，二是代表當(dāng)前元素的下標(biāo)，兩種不同的初值，也會(huì)影響后面操作的差別。
void InitST(ST* s)
{
assert(s);
s->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (s->a == NULL)
{
perror("malloc fail");
return;
}
s->capacity = 4;
s->top = -1;///top記錄指向的當(dāng)前元素
}
(2).銷毀棧
銷毀棧則非常簡單:
void DestroyST(ST* s)
{
assert(s);
s->capacity = 0;
free(s->a);
s->a = NULL;
s->top = -1;
}
(3).進(jìn)棧操作
進(jìn)棧操作也比前面的順序表鏈表的插入操作更為簡單:文章來源：http://www.zghlxwxcb.cn/news/detail-404491.html
void Push(ST* s,int x)
{
assert(s);
if (s->top+1 == s->capacity)
{
s->a = (STDataType*)realloc(s->a,sizeof(STDataType)*s->capacity*2);
if (s->a == NULL)
{
perror("malloc fail");
return;
}
s->capacity *= 2;
}
s->a[s->top+1] = x;
s->top++;
}
(4).出棧操作
出棧操作同樣簡單，知識(shí)需要提前檢查當(dāng)前是否為空棧即可：文章來源地址http://www.zghlxwxcb.cn/news/detail-404491.html
void Pop(ST* s)
{
assert(s);
assert(!STEmpty(s));
s->top--;
}
bool STEmpty(ST* s)
{
assert(s);
if (s->top == -1)
return true;
return false;
}
(5).棧的元素個(gè)數(shù)和棧頂元素
STDataType STSize(ST* s)
{
assert(s);
return s->top + 1;
}
STDataType STTop(ST* s)
{
assert(s);
return s->a[s->top];
}
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)與算法】棧的講解的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
