1?棧

1.1 棧的概念及結(jié)構(gòu)

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

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。

出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

1.2 棧的實現(xiàn)

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

// 下面是定長的靜態(tài)棧的結(jié)構(gòu)，實際中一般不實用，所以我們主要實現(xiàn)下面的支持動態(tài)增長的棧
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 棧頂
}Stack;// 支持動態(tài)增長的棧
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);
// 獲取棧中有效元素個數(shù)
int StackSize(Stack* ps);
// 檢測棧是否為空，如果為空返回非零結(jié)果，如果不為空返回0
int StackEmpty(Stack* ps);
// 銷毀棧
void StackDestroy(Stack* ps);

---

2?隊列

2.1 隊列的概念及結(jié)構(gòu)

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

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

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

2.2 隊列的實現(xiàn)

隊列也可以數(shù)組和鏈表的結(jié)構(gòu)實現(xiàn)，使用鏈表的結(jié)構(gòu)實現(xiàn)更優(yōu)一些，因為如果使用數(shù)組的結(jié)構(gòu)，出隊列在數(shù)組頭上出數(shù)據(jù)，效率會比較低。

// 鏈式結(jié)構(gòu)：表示隊列
typedef int QDataType;
typedef struct QListNode
{struct QListNode* _pNext;QDataType _data;
}QNode;// 隊列的結(jié)構(gòu)
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);
// 獲取隊列中有效元素個數(shù)
int QueueSize(Queue* q);
// 檢測隊列是否為空，如果為空返回非零結(jié)果，如果非空返回0
int QueueEmpty(Queue* q);
// 銷毀隊列
void QueueDestroy(Queue* q);

另外擴展了解一下，實際中我們有時還會使用一種隊列叫循環(huán)隊列。如操作系統(tǒng)課程講解生產(chǎn)者消費模型時就會使用循環(huán)隊列。環(huán)形隊列可以使用數(shù)組實現(xiàn)，也可以使用循環(huán)鏈表實現(xiàn)。

---

本文完