一： 棧

1.棧的概念及和結構

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

---

---

2. 棧的實用

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

---

3. 棧接口實現

Stach.h:

// 下面是定長的靜態棧的結構，實際中一般不實用，所以我們主要實現下面的支持動態增長的棧
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 StInit(Stack* ps); 
// 入棧
void StPush(Stack* ps, STDataType data); 
// 出棧
void StPop(Stack* ps); 
// 獲取棧頂元素
STDataType StTop(Stack* ps); 
// 獲取棧中有效元素個數
int StSize(Stack* ps); 
// 檢測棧是否為空，如果為空返回非零結果，如果不為空返回0 
int StEmpty(Stack* ps); 
// 銷毀棧
void StDestroy(Stack* ps)

Stack.c:

#include "Stack.h"void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;//top指向棧頂元素的下一個位置
}void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}void STPush(ST* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp = (STDateType*)realloc(ps->a,sizeof(STDateType) * newCapacity);if (tmp == NULL){perror("malloc fail");exit(-1);}//創建成功ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}STDateType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

---

二： 隊列

1. 隊列的概念和結構

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

?

2. 隊列的實用

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

3. 隊列接口實現

Queue.h:

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;QDataType data;
}QNode;//為了解決傳二級指針的問題，有兩種方法
//第一種是傳哨兵位，另一種就是如下在封裝一個結構體
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Que;// 初始化隊列
void QueueInit(Que* pq);
// 隊尾入隊列
void QueuePush(Que* pq, QDataType x);
// 隊頭出隊列
void QueuePop(Que* pq);
// 獲取隊列頭部元素
QDataType QueueFront(Que* pq);
// 獲取隊列隊尾元素
QDataType QueueBack(Que* pq);
// 獲取隊列中有效元素個數
int QueueSize(Que* pq);
// 檢測隊列是否為空，如果為空返回1，如果非空返回0 
bool QueueEmpty(Que* pq);
// 銷毀隊列
void QueueDestroy(Que* pq);

Queue.c:

#include "Stack.h"void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->capacity = 0;ps->top = 0;//top指向棧頂元素的下一個位置
}void STDestory(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}void STPush(ST* ps, STDateType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;STDateType* tmp = (STDateType*)realloc(ps->a,sizeof(STDateType) * newCapacity);if (tmp == NULL){perror("malloc fail");exit(-1);}//創建成功ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);assert(ps->top > 0);ps->top--;
}STDateType STTop(ST* ps)
{assert(ps);assert(ps->top > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

---

三：擴展

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

---

---

---