1. 棧

? ? ? ? 其實棧與隊列仍然屬于線性表（有n個元素構成的集合，邏輯結構呈現線形）

線形表：順序表，鏈表，棧，隊列，串（字符串）

棧（Stack）是一種線性數據結構，進行數據插入和刪除的一段成為棧頂，另外一段稱為棧底，數據元素遵守“后進先出”?（LIFO, Last In First Out）

棧的插入數據 --壓棧/進棧，入數據在棧頂

棧的刪除數據 -- 出棧，出數據也在棧頂。

這里棧如何實現呢？考慮(LIFO: 后進先出)

如果是雙向鏈表的話，無所謂棧頂與棧底的位置。

2. 棧的實現

? ? ? ? 棧的實現利用數組實現提高內存訪問效率

1、棧的初始化? ? ??

typedef int STDataType;
#define Ini_capacity 5typedef struct Stack
{int* _val;int _size;int _capacity;
}Stack;void StackInit(Stack* pst){assert(pst);// pst->_val = NULL;// pst->_capacity = 0;// pst->_size = 0;pst->_val = (STDataType*) malloc(Ini_capacity*sizeof(STDataType));if(pst->_val == NULL){perror("malloc");exit(-1);}pst->_size = 0;pst->_capacity =Ini_capacity;}

2、壓棧（入棧操作）

// 入棧
void StackPush(Stack* pst,STDataType Val){assert(pst);if(pst->_size == pst->_capacity){//增容pst->_capacity = 2*pst->_capacity;STDataType* tmp = realloc(pst->_val,pst->_capacity*sizeof(STDataType));pst->_val = tmp;tmp = NULL;}pst->_val[pst->_size] = Val;pst->_size++; 
}

3、出棧操作

void StackPop(Stack* pst){assert(pst && pst->_size > 0);--pst->_size;
}

4 、返回棧內數據個數，是否為空，以及棧頂元素

//獲取數據個數
int StackSize(Stack* pst){assert(pst);return(pst->_size);
}
//返回1 是空，返回0是非空
int StackEmpty(Stack* pst){assert(pst);// return pst->_size == 0 ? 1 : 0;return !pst->_size;
}
//獲取棧頂數據 
STDataType StackTop(Stack* pst){assert(pst && pst->_size>0);return pst->_val[pst->_size-1];
}

5、棧的摧毀，釋放空間

//棧的摧毀
void StackDestroy(Stack* pst){assert(pst);free(pst->_val);pst->_val = NULL;pst->_size =pst->_capacity = 0;
}

3、棧的常見應用：

• 1、函數調用（函數棧幀）

• 2、括號匹配（如表達式合法性）

• 3、 瀏覽器歷史記錄（后退/前進）

• 4、深度優先搜索（DFS）迷宮問題

4、隊列

????????隊列（Queue）是一種線性數據結構：一個典型的隊列有兩個端：Front（隊首）：元素被取出的地方 Rear（隊尾）：元素被加入的地方。它的特點是：先進先出（FIFO, First In First Out)。

同樣，隊列的實現也可以通過數組和鏈表進行實現。？考慮(FIFO: 后進先出)。

數列出隊列有些麻煩：需要挪動數據，因為隊頭的數據出隊列后，隊尾數據需要補充。

單鏈表入隊列只需要尾插，出隊列只需要將頭節點給到下一個節點，然后free即可。

5、隊列的實現

? ? ? ?隊列的實現利用單向鏈表

1、隊列的初始化 （保存隊列的頭指針，尾指針）

//利用單向鏈表的形式實現棧
typedef int QeDataType;typedef struct QueueNode
{QeDataType _data;struct QueueNode* next;
}QueueNode;
//存儲隊列的頭，尾指針用于插入和刪除隊列元素
typedef struct Queue
{QueueNode* _head;QueueNode* _tail;
}Queue;//隊列的初始化
void QueueInit(Queue* pq){assert(pq);pq->_head = pq->_tail = NULL;
}

2、隊列新增元素

//隊列插入元素
void QueuePush(Queue* pq, QeDataType x){assert(pq);QueueNode*NewNode = (QueueNode*)malloc(sizeof(QueueNode));if(NewNode == NULL){perror("malloc");exit(-1);}NewNode->next=NULL;NewNode->_data = x;if(pq->_head == NULL){pq->_head = pq->_tail = (QueueNode*)malloc(sizeof(QueueNode));}else{pq->_tail->next = NewNode;pq->_tail = NewNode;}
}

3、隊列刪除元素

//隊列刪除元素
void QueuePop(Queue* pq){assert(pq);if(pq->_head == NULL){printf("隊列為空\n");exit(-1);}QueueNode* head_next = pq->_head->next;free(pq->_head);pq->_head = head_next;if(pq->_head == NULL){pq->_tail = NULL;}
}

4、取出隊列頭數據和尾數據

//取出隊頭數據
QeDataType QueueFront(Queue* pq){assert(pq);if(pq->_head ==NULL){return NULL;}return pq->_head->_data;
}
//取出隊尾數據
QeDataType QueueBack(Queue* pq){assert(pq);if(pq->_tail ==NULL){return NULL;}return pq->_tail->_data;
}

5、檢查隊列是否為空，返回隊列大小

//檢查隊列是否為空，返回隊列大小
int QueueEmpty(Queue* pq){assert(pq);return !pq->_head;
}
int QueueSize(Queue* pq){assert(pq);if(pq == NULL){return 0;}QueueNode* Cur = pq->_head;int count =0;while(Cur || Cur != pq->_tail) {count++;Cur = Cur->next;}return count;
}

6、隊列的常見應用

棧與隊列，是程序運行背后的“隱形骨架”，掌握它們，你就掌握了高效處理順序、回退、排隊等核心能力，是走向算法高手的第一步。