一、棧
1.1棧的概念及結構
棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out)的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。
1.2棧的實現
棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。
1.2.1 棧的結點行為
和順序表一樣：一個存儲數據的數組，一個變量記錄個數，一個變量記錄容量。
typedef int STDataType;
typedef struct Stack
{STDataType* data;int capacity;int top;
}ST;
1.2.2 棧的初始化與銷毀
//初始化
void StackInit(ST* s)
{assert(s);s->data = NULL;s->capacity = s->top = 0;
}
//銷毀
void StackDestory(ST* s)
{assert(s);free(s->data);s->data = NULL;s->capacity = s->top = 0;
}
1.2.3 入棧與出棧
//入棧
void StackPush(ST* s, STDataType x)
{assert(s);//檢查是否需要擴容if (s->top == s->capacity){int new_capacity = s->capacity == 0 ? 4 : s->capacity * 2;STDataType* temp = (STDataType*)realloc(s->data, sizeof(STDataType) *new_capacity);if (temp==NULL){perror("realloc fail");exit(-1);}else{s->data = temp;s->capacity =new_capacity;}}s->data[s->top] = x;s->top++;}//出棧
void StackPop(ST* s)
{assert(s);assert(s->top);s->top -= 1;
}
1.2.4 棧的其他操作
//棧的元素個數
int StackSize(ST* s)
{assert(s);return s->top;
}
//判空
bool StackEmpty(ST* s)
{assert(s);return s->top == 0;
}
//取棧頂元素
STDataType StackTop(ST* s)
{assert(s);return s->data[s->top - 1];
}
二、隊列
2.1隊列的概念及結構
隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)的原則。
入隊列：進行插入操作的一端稱為隊尾 出隊列：進行刪除操作的一端稱為隊頭
2.2隊列的實現
隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低。
2.2.1 隊列的結點行為
首先，我們使用鏈表來實現隊列，那么我們需要先定義鏈表型結點：
typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QN;
其次經過分析，我們知道入隊列時就是對鏈表進行尾插操作，尾插的時間復雜度時O（N），因此我們想到用兩個結點（一個頭結點來控制出隊列，一個尾結點來控制入隊列）。因此我們自然而然地想起定義一個結構體來控制他們的行為：
typedef struct Queue
{QN* head;QN* tail;int size;//后續進行統計個數時時間復雜度為O（N），引入size，來提高程序效率
}Queue;
2.2.2 隊列的初始化與銷毀
//初始化
void QueueInit(Queue* s)
{assert(s);s->head = s->tail = NULL;s->size = 0;
}
//銷毀
void QueueDestory(Queue* s)
{assert(s);QN* cur = s->head;while (cur){QN* next = cur->next;free(cur);cur = next;}s->head = s->tail = NULL;s->size = 0;
}
2.2.3 入隊列與出隊列
//入隊
void QueuePush(Queue* s, QueueDataType x)
{assert(s);QN* newnode = (QN*)malloc(sizeof(QN));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->data = x;//隊列是否為空if (s->tail == NULL){s->head = s->tail = newnode;}else{s->tail->next = newnode;s->tail = newnode;}s->size++;
}//出隊
void QueuePop(Queue* s)
{assert(s);//隊列為空時，無法再出數據assert(s->head);//隊列是一個元素還是多個元素if (s->head->next == NULL){s->head = s->tail = NULL;}else{QN* next = s->head->next;free(s->head);s->head = next;}s->size--;
}
2.2.4 隊列的其他操作
//隊列元素個數
int QueueSize(Queue* s)
{assert(s);return s->size;
}
//判空
bool QueueEmpty(Queue* s)
{assert(s);return s->head == NULL;
}
//取隊頭元素
QueueDataType QueueFront(Queue* s)
{assert(s);return s->head->data;
}
//取隊尾元素
QueueDataType QueueBack(Queue* s)
{assert(s);return s->tail->data;
}
)
