---

目錄

一、棧的概念

二、棧的兩種實(shí)現(xiàn)方式

1.順序表實(shí)現(xiàn)棧

2.鏈表實(shí)現(xiàn)棧

三、棧的順序存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

1.棧的聲明

2.棧的初始化

3.棧的銷毀

4.棧的壓棧

5.棧的彈棧

6.棧的判空

7.返回棧頂元素

8.返回棧的長(zhǎng)度

四、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

1.棧的聲明

2.棧的初始化

3.棧的銷毀

4.棧的壓棧

5.棧的彈棧

6.棧的判空

7.返回棧頂元素

8.返回棧的長(zhǎng)度

---

一、棧的概念

• 棧的定義：棧是一種特殊的線性表；但在概念上又有一些規(guī)定，棧只允許在一端進(jìn)行數(shù)據(jù)的插入與刪除的操作，被稱為棧頂，而另一端則被稱為棧底
• 出棧（彈棧）：在棧頂進(jìn)行數(shù)據(jù)的刪除
• 入棧（壓棧）：在棧底進(jìn)行數(shù)據(jù)的插入? ? ??
• LIFO原則：棧中的數(shù)據(jù)服從后進(jìn)先出原則（last in first out）

二、棧的兩種實(shí)現(xiàn)方式

1.順序表實(shí)現(xiàn)棧

• 設(shè)計(jì)思路：將數(shù)組下標(biāo)為0的位置作為棧底，而數(shù)組的最大下標(biāo)（即長(zhǎng)度減一）作為棧頂元素可能存在的位置；用top指向棧頂元素下一位置的索引
• 壓棧：棧的壓棧操作，即為順序表的尾插
• 彈棧：棧的彈棧操作，即為順序表的尾刪
• 設(shè)計(jì)優(yōu)勢(shì)：避免了數(shù)組增加刪除數(shù)據(jù)時(shí)候需要移動(dòng)數(shù)據(jù)；壓棧與彈棧的時(shí)間復(fù)雜度為O(1)
• 自身優(yōu)勢(shì)：緩沖區(qū)的利用率高；用一段連續(xù)的物理地址來(lái)存儲(chǔ)數(shù)據(jù)
• 缺點(diǎn)：動(dòng)態(tài)順序表實(shí)現(xiàn)的棧需要擴(kuò)容，而擴(kuò)容會(huì)導(dǎo)致空間浪費(fèi)或性能消耗

2.鏈表實(shí)現(xiàn)棧

• 設(shè)計(jì)思路：將單鏈表的尾部作為棧底，將鏈表的頭部作為棧頂；鏈表的頭指針指針棧頂元素的位置
• 壓棧：棧的壓棧操作，即為鏈表的頭插
• 彈棧：棧的彈棧操作，即為鏈表的頭刪
• 設(shè)計(jì)優(yōu)勢(shì)：避免了鏈表刪除數(shù)據(jù)結(jié)點(diǎn)的時(shí)候，需要找到該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)；壓棧與彈棧的時(shí)間復(fù)雜度為O(1)
• 自身優(yōu)勢(shì)：沒(méi)有擴(kuò)容所帶來(lái)的空間的浪費(fèi)與性能的消耗
• 缺點(diǎn)：緩存利用率不如順序表高

三、棧的順序存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

1.棧的聲明

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>#define STDateType int typedef struct Stack
{STDateType* date;int top;int capacity;
}ST;void STInit(ST* st);
void STDestory(ST* st);
void STPush(ST* st, STDateType x);
void STPop(ST* st);
STDateType STTop(ST* st);
bool STEmpty(ST* st);
int STSize(ST* st);

2.棧的初始化

void STInit(ST* st)
{assert(st);st->date = NULL;st->capacity = st->top = 0;
}

3.棧的銷毀

void STDestory(ST* st)
{assert(st);free(st->date);st->date = NULL;st->top = 0;st->capacity = 0;
}

4.棧的壓棧

void STPush(ST* st, STDateType x)
{assert(st);if (st->top == st->capacity){size_t newcapacity = (st->capacity == 0 ? 4 : 2 * st->capacity);STDateType* tmp = (STDateType*)realloc(st->date, sizeof(STDateType) * newcapacity);if (tmp != NULL){st->date = tmp;st->capacity = newcapacity;}}st->date[st->top++] = x;
}

5.棧的彈棧

void STPop(ST* st)
{assert(st);assert(st->top > 0);st->top--;
}

6.棧的判空

bool STEmpty(ST* st)
{assert(st);return st->top == 0;
}

7.返回棧頂元素

STDateType STTop(ST* st)
{assert(st);assert(st->top > 0);return st->date[st->top - 1];
}

8.返回棧的長(zhǎng)度

int STSize(ST* st)
{assert(st);return st->top;
}

四、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)

1.棧的聲明

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>typedef int StDateType;typedef struct StackNode
{StDateType date;struct StackNode* next;
}StackNode;typedef struct Stack
{StackNode* top;size_t size;
}Stack;void StackInit(Stack* st);//初始化
void StackDestory(Stack* st);//銷毀
void StackPush(Stack* st, StDateType x);//壓棧
void StackPop(Stack* st);//彈棧
StDateType StackTop(Stack* st);//讀取棧頂元素
bool StackEmpty(Stack* st);//判空
size_t StackSize(Stack* st);//返回棧的長(zhǎng)度

2.棧的初始化

void StackInit(Stack* st)
{assert(st);st->top = NULL;st->size = 0;
}

3.棧的銷毀

void StackDestory(Stack* st)
{assert(st);while (st->size > 0)StackPop(st);
}

4.棧的壓棧

void StackPush(Stack* st, StDateType x)
{assert(st);StackNode* Node = (StackNode*)malloc(sizeof(StackNode));if (!Node){perror("malloc mistake");exit(-1);}Node->date = x;Node->next = NULL;Node->next = st->top;st->top = Node;st->size++;
}

5.棧的彈棧

void StackPop(Stack* st)
{assert(st);assert(st->top);StackNode* tmp = st->top;  st->top = st->top->next;  free(tmp);  st->size--;  
}

6.棧的判空

bool StackEmpty(Stack* st)
{assert(st);return st->top == NULL;
}

7.返回棧頂元素

StDateType StackTop(Stack* st)
{assert(st);return st->top->date;
}

8.返回棧的長(zhǎng)度

size_t StackSize(Stack* st)
{assert(st);assert(st->top);return st->size;
}