1?棧

1.1 棧的概念及結構

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

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

1.2 棧的實現

棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。

// 下面是定長的靜態棧的結構，實際中一般不實用，所以我們主要實現下面的支持動態增長的棧
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 棧頂
}Stack;// 支持動態增長的棧
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top; // 棧頂int _capacity; // 容量
}Stack;
// 初始化棧
void StackInit(Stack* ps);
// 入棧
void StackPush(Stack* ps, STDataType data);
// 出棧
void StackPop(Stack* ps);
// 獲取棧頂元素
STDataType StackTop(Stack* ps);
// 獲取棧中有效元素個數
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0
int StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);

---

2?隊列

2.1 隊列的概念及結構

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列遵循先進先出 FIFO (First In First Out) 的原則。

入隊列：進行插入操作的一端稱為隊尾。

出隊列：進行刪除操作的一端稱為隊頭。

2.2 隊列的實現

隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低。

// 鏈式結構：表示隊列
typedef int QDataType;
typedef struct QListNode
{struct QListNode* _pNext;QDataType _data;
}QNode;// 隊列的結構
typedef struct Queue
{QNode* _front;QNode* _rear;
}Queue;// 初始化隊列
void QueueInit(Queue* q);
// 隊尾入隊列
void QueuePush(Queue* q, QDataType data);
// 隊頭出隊列
void QueuePop(Queue* q);
// 獲取隊列頭部元素
QDataType QueueFront(Queue* q);
// 獲取隊列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取隊列中有效元素個數
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);

另外擴展了解一下，實際中我們有時還會使用一種隊列叫循環隊列。如操作系統課程講解生產者消費模型時就會使用循環隊列。環形隊列可以使用數組實現，也可以使用循環鏈表實現。

---

本文完