---

前言

本文主要講述特殊的線性表——棧：

---

棧是什么，棧的特點

數(shù)據(jù)結(jié)構(gòu)中有一種特殊的線性表叫棧。
棧有一種特點：

它允許后進(jìn)入的數(shù)據(jù)先拿出來。

類似一個彈夾，或是一個裝磚頭的容器。

棧的基本操作有如上圖：

類比一個缸，缸的底端是棧底，頂端是棧頂，放入數(shù)據(jù)稱為入棧，取出數(shù)據(jù)稱為出棧。

對于一個棧，其特點為后進(jìn)先出
Last In Fist Out
或者
先進(jìn)后出
Fist Out Last In

所以在實現(xiàn)棧這種特殊的線性表時，當(dāng)我們拿出數(shù)據(jù)的時候，只需要取棧頂元素即可，存入數(shù)據(jù)時，只需往棧頂存放數(shù)據(jù)。

綜合棧的特點，在實現(xiàn)其結(jié)構(gòu)時更適合使用數(shù)組 ，而不是鏈表。
當(dāng)然使用鏈表也是可行的，相比而言：
使用鏈表的缺點有：
1.在壓棧時總需要next的指針來維護(hù)。
2。出棧時需要記錄上一個節(jié)點的位置，效率較低。

數(shù)組的方式可以解決上述兩個問題，且無其他較為嚴(yán)重的缺點。

下面來實現(xiàn)棧的基本功能：

實現(xiàn)棧的基本操作

棧的相關(guān)操作聲明

void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);
void CheckCapacity(ST** ps);//檢查容量
void StackPush(ST* ps,STDataType x);//插入元素
STDataType StackPop(ST* ps);//刪除棧頂元素
int StackSize(ST* ps);//計算棧有多少個數(shù)據(jù)
bool StackEmpty(ST* ps);//判斷棧是否為空
STDataType StackTop(ST* ps);//取棧頂元素注：ps是指向一個結(jié)構(gòu)體的指針，在main函數(shù)創(chuàng)建了一個結(jié)構(gòu)體：ST st;并且傳參傳的是結(jié)構(gòu)體的地址

1.創(chuàng)建棧

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
//用順序表實現(xiàn)棧typedef struct Stack
{STDataType* a;int top;//插入棧頂元素int capacity;//棧的容量
}ST;

解讀： 定義一個結(jié)構(gòu)體：使用結(jié)構(gòu)體的指針來維護(hù)數(shù)組棧
top表示棧頂?shù)脑?br /> capacity表示棧的容量大小

2.對棧進(jìn)行初始化

void StackInit(ST* ps)//初始化
{assert(ps!=NULL);ps->a = NULL;ps->top = ps->capacity = 0;//ps->top可以初始化成-1，此時先++，再賦值//此時指向的就是棧頂元素
}

3.銷毀棧

void StackDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

4.判斷棧是否為空

bool StackEmpty(ST* ps)//判斷棧是否為空
{assert(ps);return ps->top == 0;
}

5.壓棧操作

void CheckCapacity(ST**ps)//檢查容量
{assert(ps != NULL);if ((*ps)->top == (*ps)->capacity){STDataType newcapacity = (*ps)->capacity == 0 ? 4 : (*ps)->capacity * 2;STDataType* tmp = (STDataType*)realloc((*ps)->a,(sizeof(STDataType)*newcapacity));//申請的空間是存放STDataType的//不是用來存放結(jié)構(gòu)體的//如果第一個參數(shù)是一個NULL，realloc的作用就跟malloc一樣，所以可以傳NULLassert(tmp != NULL);(*ps)->a = tmp;// 把新地址給ps->a(*ps)->capacity = newcapacity;}
}void StackPush(ST* ps, STDataType x)//插入元素
{assert(ps);CheckCapacity(&ps);//這里如果傳參傳的是ps，相當(dāng)于傳值調(diào)用，在CheckCapacity函數(shù)內(nèi)部申請的空間就無法返回來了。ps->a[ps->top] = x; // 先賦值，再++，因為ps->top初始化是0，就是指向棧頂元素的下一個。ps->top++;
}

解讀：入棧時首先需要檢查?？臻g的容量大小，如果?？臻g不足則需增容。
在這里分裝了一個檢查容量的函數(shù)。

6.刪除棧頂元素

STDataType StackPop(ST* ps)//刪除棧頂數(shù)據(jù)
{assert(ps);assert(!StackEmpty(ps));ps->top--;
}

7.取出棧頂元素

注：第六個函數(shù)僅僅刪除棧頂元素并未拿到該數(shù)據(jù)
這里分裝函數(shù)是更方便的

STDataType StackTop(ST* ps)//取棧頂元素
{assert(ps);assert(!StackEmpty(ps)); //感嘆號表達(dá)式讓語句的邏輯相反return ps->a[ps->top - 1];//在這里我初始化top為0，表示指向棧頂元素的下一個位置//因為初始化為0時，需要先壓棧，top值再++，此時就指向了下一個位置了
}

8.計算棧內(nèi)存放多少個數(shù)據(jù)

int StackSize(ST* ps)//計算棧有多少個數(shù)據(jù)
{assert(ps);assert(!StackEmpty(ps));return ps->top;
}

解讀：
這里直接返回top，而不是返回top-1
因為我們在初始化的時候是將top置為0，先入棧，top再++
假如入棧三次，那么top此時就是3，但是top指向的位置是入棧的第三個元素的下一個位置。

函數(shù)基本功能如下：

總結(jié)

掌握了鏈表的結(jié)構(gòu)之后，實現(xiàn)棧難度是不大的。