網(wǎng)站首頁 編程語言 正文
棧和隊列是一種數(shù)據(jù)結(jié)構(gòu)，只規(guī)定了性質(zhì)，并沒有規(guī)定實現(xiàn)方式。
本文以順序結(jié)構(gòu)實現(xiàn)棧，鏈表方式實現(xiàn)隊列。
一、棧的概念
棧：是一種特殊的線性表，其只允許在棧頂進行插入和刪除元素操作。
棧中的數(shù)據(jù)元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧\壓棧\入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。
二、Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDataType;
typedef struct stack
{
STDataType* arr;
int top;//數(shù)組元素個數(shù)（top-1為最后一個元素的下標）就是順序表的size
int capacity;//總?cè)萘?
}ST;
void StackInit(ST* ps);//初始化
void StackDestroy(ST* ps);//銷毀
void StackPush(ST* ps, STDataType x);//壓棧
void StackPop(ST* ps);//出棧
bool StackEmpty(ST* ps);//判斷棧是不是為空
STDataType StackTop(ST* ps);//訪問棧頂元素
int StackSize(ST* ps);//數(shù)組元素個數(shù)以順序結(jié)構(gòu)實現(xiàn)棧，本質(zhì)上仍是一個順序表，只是這個順序表加上了棧先進后出的規(guī)則。
數(shù)組的頭是棧底，數(shù)組尾是棧頂。棧主要的壓棧、出棧、訪問棧頂?shù)冉涌诜浅Ｆ鹾享樞虮淼奈膊?、尾刪、隨機訪問的特點。
三、Stack.c
1、棧的初始化和銷毀
void StackInit(ST* ps)//初始化
{
assert(ps);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
void StackDestroy(ST* ps)//銷毀
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
和順序表的初始化、銷毀方式一樣
2、棧的進棧、出棧
void StackPush(ST* ps, STDataType x)//進棧
{
assert(ps);
//判斷擴容
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail:\n");
exit(-1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
ps->arr[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)//出棧
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}進棧需要判斷棧的空間，空間不夠則需要擴容
出棧時，先判空，再將top--即可
3、棧的判空、訪問棧頂元素、棧內(nèi)元素個數(shù)
bool StackEmpty(ST* ps)//判斷棧是不是為空
{
assert(ps);
return ps->top == 0;
}
STDataType StackTop(ST* ps)//訪問棧頂元素
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top - 1];
}
int StackSize(ST* ps)//數(shù)組元素個數(shù)
{
assert(ps);
return ps->top;
}注意訪問棧頂元素這個接口，要先判斷棧是不是空。
四、隊列的概念
隊列：一端進行插入數(shù)據(jù)操作，另一端進行刪除數(shù)據(jù)操作的特殊線性表，隊列具有先進先出FIFO(First In First Out)的特點。
入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭
隊列參照現(xiàn)實生活中的排隊
五、Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.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;//加個size，方便統(tǒng)計長度
}Queue;
void QueueInit(Queue* pq);//初始化
void QueueDestroy(Queue* pq);//銷毀
void QueuePush(Queue* pq,QDataType x);//入隊（尾插）
bool QueueEmpty(Queue* pq);//判斷隊列是否為空
void QueuePop(Queue* pq);//出隊（頭刪）
int QueueSize(Queue* pq);//統(tǒng)計隊列長度
QDataType QueueFront(Queue* pq);//訪問隊頭數(shù)據(jù)
QDataType QueueBack(Queue* pq);//訪問隊尾數(shù)據(jù)因為順序結(jié)構(gòu)不適合頭刪，這里使用單鏈表來實現(xiàn)隊列。
結(jié)構(gòu)體QNode用于模擬單鏈表，結(jié)構(gòu)體Queue中存放了單鏈表的頭、尾指針、鏈表節(jié)點個數(shù)。使用Queue來操縱單鏈表。
單鏈表的頭head是隊頭（頭刪出數(shù)據(jù)），tail是隊尾（尾插錄數(shù)據(jù)）
六、Queue.c
1、隊列的初始化和銷毀
void QueueInit(Queue* pq)//初始化
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueueDestroy(Queue* pq)//銷毀
{
assert(pq);
QNode* cur = pq->head;
//逐個銷毀釋放空間
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = pq->tail = NULL;
}和單鏈表的銷毀方式一樣，注意銷毀時需要逐個節(jié)點銷毀。
2、隊列的入隊、出隊
void QueuePush(Queue* pq, QDataType x)//入隊,尾插
{
assert(pq);
//創(chuàng)建一個新節(jié)點
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail:\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
//隊列為空時的尾插和不為空的尾插
if (QueueEmpty(pq))
pq->head=pq->tail = newnode;
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}
void QueuePop(Queue* pq)//出隊（頭刪）
{
assert(pq);
assert(!QueueEmpty(pq));
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
pq->size--;
}入隊：尾插一個節(jié)點
出隊：頭刪一個節(jié)點
3、隊列的判空
bool QueueEmpty(Queue* pq)//判斷隊列是否為空
{
assert(pq);
return pq->head == NULL;
}
4、訪問隊頭、隊尾數(shù)據(jù)、統(tǒng)計隊列長度
int QueueSize(Queue* pq)//統(tǒng)計隊列長度
{
assert(pq);
return pq->size;
}
QDataType QueueFront(Queue* pq)//訪問隊頭數(shù)據(jù)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}
QDataType QueueBack(Queue* pq)//訪問隊尾數(shù)據(jù)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}訪問接口，注意先判空。
七、力扣中棧和隊列OJ題
1、有效的括號
使用隊列來解決，創(chuàng)建一個棧，碰到左括號將其進棧，碰到右括號則訪問棧頂元素，不相符則為false，迭代比較相符則為true
bool isValid(char * s){
ST st;
StackInit(&st);
while(*s)
{
if(*s=='('||*s=='{'||*s=='[')
{
StackPush(&st,*s);//壓棧
}
else//比較時的情況
{
if(StackEmpty(&st))
return false;
else if(StackTop(&st)=='('&&*s!=')')//訪問棧頂元素
{
return false;
}
else if(StackTop(&st)=='{'&&*s!='}')
{
return false;
}
else if(StackTop(&st)=='['&&*s!=']')
{
return false;
}
StackPop(&st);
}
++s;
}
if(!StackEmpty(&st))
return false;
StackDestroy(&st);
return true;
}注：上述代碼還需要將棧的實現(xiàn)的代碼拷貝一份上去。
2、用隊列實現(xiàn)棧
入棧：選擇非空隊列進行入棧
出棧：隊列中只留一個元素，將其他元素Pop至另一個隊列，再對那個遺留的元素執(zhí)行出隊列操作即可模擬出棧動作
typedef struct {
Queue q1;
Queue q2;
} MyStack;
MyStack* myStackCreate() {
MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
QueueInit(&obj->q1);
QueueInit(&obj->q2);
return obj;
}
void myStackPush(MyStack* obj, int x) {
if(!QueueEmpty(&obj->q1))
{
QueuePush(&obj->q1,x);//入隊,尾插
}
else
{
QueuePush(&obj->q2,x);//入隊,尾插
}
}
int myStackPop(MyStack* obj) {
Queue* empty=&obj->q1;
Queue* unEmpty=&obj->q2;
if(QueueEmpty(&obj->q2))
{
empty=&obj->q2;
unEmpty=&obj->q1;
}
while(QueueSize(unEmpty)>1)//將非空元素導(dǎo)入到空隊列，留下最后一個
{
QueuePush(empty,QueueFront(unEmpty));//入隊,尾插
QueuePop(unEmpty);//出隊（頭刪）
}
int top=QueueFront(unEmpty);
QueuePop(unEmpty);//出隊（頭刪）
return top;
}
int myStackTop(MyStack* obj) {
if(!QueueEmpty(&obj->q1))
{
return QueueBack(&obj->q1);//訪問隊尾數(shù)據(jù)
}
else
{
return QueueBack(&obj->q2);//訪問隊尾數(shù)據(jù)
}
}
bool myStackEmpty(MyStack* obj) {
return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
QueueDestroy(&obj->q1);//銷毀
QueueDestroy(&obj->q2);//銷毀
free(obj);
}注：上述代碼還需要將隊列的實現(xiàn)的代碼拷貝一份上去。
3、用棧實現(xiàn)隊列
現(xiàn)在有兩個棧，第一個棧用于入棧、出棧至第二個棧的操作，第二個棧僅用于出棧操作。
入棧：在第一個棧中壓入數(shù)據(jù)
出棧：如果第二個棧為空，則第一個棧中 數(shù)據(jù)全部出棧至第二個棧，由第二個棧專門執(zhí)行出棧操作。等第二個棧再次為空，再次執(zhí)行上述動作
MyQueue* myQueueCreate() {
MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
StackInit(&obj->st1);
StackInit(&obj->st2);
return obj;
}
void myQueuePush(MyQueue* obj, int x) {
StackPush(&obj->st1, x);//壓棧
}
int myQueuePop(MyQueue* obj) {
if(StackEmpty(&obj->st2))
{
while(!StackEmpty(&obj->st1))
{
StackPush(&obj->st2, StackTop(&obj->st1));//壓棧
StackPop(&obj->st1);
}
}
int val=StackTop(&obj->st2);
StackPop(&obj->st2);
return val;
}
int myQueuePeek(MyQueue* obj) {
if(StackEmpty(&obj->st2))
{
while(!StackEmpty(&obj->st1))
{
StackPush(&obj->st2, StackTop(&obj->st1));//壓棧
StackPop(&obj->st1);
}
}
return StackTop(&obj->st2);
}
bool myQueueEmpty(MyQueue* obj) {
return StackEmpty(&obj->st1)&&StackEmpty(&obj->st2);
}
void myQueueFree(MyQueue* obj) {
StackDestroy(&obj->st1);
StackDestroy(&obj->st2);
free(obj);
}注：上述代碼還需要將棧的實現(xiàn)的代碼拷貝一份上去。
4、設(shè)計循環(huán)隊列
typedef struct {
int* arr;
int front;//記錄首
int tail;//記錄尾的下一個
int capacity;//用于處理邊界問題的一個變量
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->arr=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->tail=0;
obj->capacity=k+1;//這里一定要寫成k+1，寫成k的話,后續(xù)處理邊界問題要額外考慮分支情況
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->capacity)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->arr[obj->tail]=value;
obj->tail++;
obj->tail%=obj->capacity;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
obj->front%=obj->capacity;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
obj->arr=NULL;
free(obj);
}因為循環(huán)隊列無法區(qū)分隊列為空和為滿的情況，因為為空和未滿，首位下標是一樣的。
所以這道題有兩種解法，計數(shù)確定?？諚M，或者多開辟一個空間。本題采用后者。
可選的數(shù)據(jù)結(jié)構(gòu)也有兩種，順序和鏈表。本題采用順序。
上表為隊列滿的情況，無法再執(zhí)行插入。運用順序表，本題的難點在于如何處理tail和front在數(shù)組尾部的情況。
強烈建議在初始化的接口中將capacity定義為k+1，因為入隊出隊接口中%capacity后，可以同時滿足正常和極端位置下的情況。（詳見代碼，一讀就懂，后續(xù)讀者可以逝一下將capacity定義為k，感受下區(qū)別）
capacity定義為k時的代碼如下：
typedef struct {
int* arr;
int front;//記錄首
int tail;//記錄尾的下一個
int capacity;//總?cè)萘?
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
obj->arr=(int*)malloc(sizeof(int)*(k+1));
obj->front=obj->tail=0;
obj->capacity=k;
return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
return obj->front==obj->tail;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
return (obj->tail+1)%(obj->capacity+1)==obj->front;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
if(myCircularQueueIsFull(obj))
return false;
obj->arr[obj->tail]=value;
obj->tail++;
if(obj->tail>obj->capacity)
obj->tail=obj->tail%obj->capacity-1;
return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return false;
obj->front++;
if(obj->front>obj->capacity)
obj->front=obj->front%obj->capacity-1;
return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
return obj->arr[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
if(myCircularQueueIsEmpty(obj))
return -1;
if(obj->tail!=0)
return obj->arr[(obj->tail-1+obj->capacity)%obj->capacity];
return obj->arr[obj->capacity];
}
void myCircularQueueFree(MyCircularQueue* obj) {
free(obj->arr);
obj->arr=NULL;
free(obj);
}主要區(qū)別就是入隊出隊代碼，常規(guī)情況和邊界情況不能統(tǒng)一。
原文鏈接：https://blog.csdn.net/gfdxx/article/details/126397879
相關(guān)推薦
- 2023-03-23 詳解python?ThreadPoolExecutor異常捕獲_python
- 2023-07-09 【elementplus】body設(shè)置zoom后，el-table開啟show-overflow-t
- 2022-09-09 Python利用Turtle繪畫簡單圖形_python
- 2022-08-19 一篇文章讓你看懂用git上傳文件至gitee，結(jié)尾有.gitignore配置
- 2022-03-03 Module parse failed: Unexpected token (3:27) File
- 2022-05-13 檢測到調(diào)試后執(zhí)行的代碼
- 2022-01-17 rabbitmq出現(xiàn) 已安裝 rabbitmq-server 軟件包 post-installati
- 2022-11-12 media配置及把用戶頭像從數(shù)據(jù)庫展示到前端的操作方法_python
- 最近更新
-
- window11 系統(tǒng)安裝 yarn
- 超詳細win安裝深度學習環(huán)境2025年最新版（
- Linux 中運行的top命令 怎么退出？
- MySQL 中decimal 的用法？ 存儲小
- get 、set 、toString 方法的使
- @Resource和 @Autowired注解
- Java基礎(chǔ)操作-- 運算符，流程控制 Flo
- 1. Int 和Integer 的區(qū)別，Jav
- spring @retryable不生效的一種
- Spring Security之認證信息的處理
- Spring Security之認證過濾器
- Spring Security概述快速入門
- Spring Security之配置體系
- 【SpringBoot】SpringCache
- Spring Security之基于方法配置權(quán)
- redisson分布式鎖中waittime的設(shè)
- maven:解決release錯誤：Artif
- restTemplate使用總結(jié)
- Spring Security之安全異常處理
- MybatisPlus優(yōu)雅實現(xiàn)加密？
- Spring ioc容器與Bean的生命周期。
- 【探索SpringCloud】服務(wù)發(fā)現(xiàn)-Nac
- Spring Security之基于HttpR
- Redis 底層數(shù)據(jù)結(jié)構(gòu)-簡單動態(tài)字符串（SD
- arthas操作spring被代理目標對象命令
- Spring中的單例模式應(yīng)用詳解
- 聊聊消息隊列，發(fā)送消息的4種方式
- bootspring第三方資源配置管理
- GIT同步修改后的遠程分支
提供CDN加速