一、棧
1.棧的概念

? ? 棧：一種特殊的線性表，其只允許在固定的一端進(jìn)行插入和刪除元素操作。 進(jìn)行數(shù)據(jù)插入和刪除操作的一端稱為棧頂，另一端稱為棧底。
? ? 棧中的數(shù)據(jù)元素遵守后進(jìn)先出LIFO（Last In First Out）的原則。 壓棧：棧的插入操作叫做進(jìn)棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
? ? 出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

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

棧的實(shí)現(xiàn)一般可以使用數(shù)組或者鏈表實(shí)現(xiàn)，相對(duì)而言數(shù)組的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些。因?yàn)閿?shù)組在尾上插入數(shù)據(jù)的代價(jià)比較小。

3.代碼示例

（1）Stack.h

?

//頭文件的聲明
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

2.棧的接口定義

//棧的接口定義
typedef int STDataType;
typedef struct Stack
{
? ? STDataType* a;
? ? int top;
? ? int capacity;
}ST;

3.初始化和銷毀函數(shù)的聲明

//初始化
void STInit(ST* ps);
//銷毀
void STDestroy(ST* ps);

4.入棧和出棧函數(shù)的聲明

//插入
void STPush(ST* ps, STDataType x);
//刪除
void STPop(ST* ps);

5.查找棧頂元素和長度計(jì)算函數(shù)以及判空函數(shù)的聲明

//插入
//查找棧頂元素
STDataType STTop(ST* ps);
//長度計(jì)算
int STSize(ST* ps);
//判斷是否為空
bool STEmpty(ST* ps);