數據結構——棧和隊列oj練習

225. 用隊列實現棧 - 力扣（LeetCode）

這一題需要我們充分理解隊列和棧的特點。

隊列：隊頭出數據，隊尾入數據。

棧：棧頂出數據和入數據。

我們可以用兩個隊列實現棧，在這過程中，我們總要保持其中一個隊列為空。如果我們出棧，也就是要將棧頂元素彈出，就相當于對非空隊列進行操作，就是要把非空隊列的隊尾元素彈出隊列。但是隊列的隊尾是不能出數據的，想要讓隊尾數據出隊列，就要讓這個數據到達隊頭，同時我們還要保留其他的數據，就需要用到另一個隊列來保存。

所以說，我們要用隊列模擬出棧過程，就要把非空隊列中的數據不斷彈出放到另一個隊列中，直到非空隊列中的數據個數變成1，保留下這個數據的值，再將這個數據從隊列中彈出。

對于取棧頂元素過程，大部分代碼可以復用出棧的代碼。或者我們可以發現棧頂元素就是非空隊列的隊尾元素，我們直接取出非空隊列的隊尾元素即可。

對于入棧過程，對于棧，我們直接將數據放到非空隊列的隊尾即可。

typedef int Qdatatype;typedef struct QueueNode
{Qdatatype data;struct QueueNode* next;
}QueueNode;//隊列的結構定義：
typedef struct Queue
{QueueNode* phead;//隊頭QueueNode* ptail;//隊尾int size;//隊列中有效數據個數
}Queue;//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//銷毀
void QueueDesTroy(Queue* pq)
{QueueNode* pcur = pq->phead;while (pcur){QueueNode* pnext = pcur->next;free(pcur);pcur = pnext;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//入隊列
//入隊列是在隊尾入的，所以入隊列相當于鏈表的尾插
void QueuePush(Queue* pq, Qdatatype x)
{assert(pq);//申請新的節點空間QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));newnode->next = NULL;newnode->data = x;//尾插//如果此時隊列中一個元素都沒有if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else//隊列本來就有元素{pq->ptail->next = newnode;pq->ptail = newnode;}(pq->size)++;
}//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//出隊列
//出隊列是在隊頭出的，相當于鏈表的頭刪
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//如果鏈表中只有一個元素if (pq->phead->next == NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else//直接頭刪{QueueNode* newhead = pq->phead->next;free(pq->phead);pq->phead = newhead;}(pq->size)--;
}//取隊頭數據
Qdatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->phead->data;
}//取隊尾數據
Qdatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->ptail->data;
}//隊列有效元素個數
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//=========前面為隊列的實現===========
//棧的結構
typedef struct 
{Queue q1;Queue q2;
} MyStack;//棧的初始化
MyStack* myStackCreate() {MyStack* stack=(MyStack*)malloc(sizeof(MyStack));QueueInit(&(stack->q1));QueueInit(&(stack->q2));return stack;
}
//入棧
void myStackPush(MyStack* obj, int x) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}QueuePush(nonempty,x);
}
//出棧
int myStackPop(MyStack* obj) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}while(QueueSize(nonempty)!=1)//讓非空隊列中的元素不停地出棧直到棧中只有一個元素{//將元素放到原來是空的隊列中QueuePush(empty,QueueFront(nonempty));//出隊列QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePop(nonempty);return ret;
}
//取棧頂元素:兩種方法
//方法一：
int myStackTop(MyStack* obj) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}while(QueueSize(nonempty)!=1)//讓非空隊列中的元素不停地出棧直到棧中只有一個元素{//將元素放到原來是空的隊列中QueuePush(empty,QueueFront(nonempty));//出隊列QueuePop(nonempty);}int ret=QueueFront(nonempty);QueuePush(empty,ret);QueuePop(nonempty);return ret;
}
//方法二：
int myStackTop(MyStack* obj) 
{Queue* empty=&(obj->q1);Queue* nonempty=&(obj->q2);if(QueueEmpty(&(obj->q2))){empty=&(obj->q2);nonempty=&(obj->q1);}return QueueBack(nonempty);
}//判斷棧是否為空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}
//銷毀
void myStackFree(MyStack* obj) 
{QueueDesTroy(&(obj->q1));QueueDesTroy(&(obj->q2));free(obj);obj=NULL;
}

232. 用棧實現隊列 - 力扣（LeetCode）

我們是可以用兩個棧實現隊列的結構的。具體實現方法如下：

我們定義兩個棧，一個棧A是專門用來插入數據的，另一個棧B是專門用來出數據的。當我們要插入數據的時候，直接往A中插入即可，當我們要刪除數據的時候，要先檢查B是否為空，如果B為空，就講A中的數據全部放入B中，如果B不為空，就直接對B進行出棧操作。

typedef int stdatatype;//定義棧的結構：
typedef struct Stack
{stdatatype* arr;int top;//指向棧頂的后一個位置，也可以表示有效數據個數int capacity;//棧中的最大容量
}ST;
//初始化
void STInit(ST* ps)
{assert(ps);//防止后續空指針解引用ps->arr = NULL;ps->top = 0;//如果使top=0，那么top指向棧頂元素的后一個位置，//如果想讓top指向棧頂元素,就要讓top初始化為-1ps->capacity = 0;
}//銷毀
void STDesTroy(ST* ps)
{assert(ps);free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入棧——棧頂
void STPush(ST* ps, stdatatype x)
{assert(ps);//先判斷是否需要擴容if (ps->top == ps->capacity){//需要擴容int newcapacity = ps->capacity > 0 ? 2 * ps->capacity : 4;stdatatype*tmp = (stdatatype*)realloc(ps->arr, newcapacity * sizeof(stdatatype));ps->arr = tmp;ps->capacity = newcapacity;}ps->arr[(ps->top)++] = x;
}//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧———棧頂
void STPop(ST* ps)
{assert(ps);//出棧之前先判空assert(ps->top);ps->top--;
}//取棧頂元素
stdatatype STTop(ST* ps)
{assert(ps);//去棧頂元素之前先判空assert(ps->top);return ps->arr[ps->top - 1];
}//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}//================以上全是棧的實現=============
typedef struct 
{ST pushst;ST popst;
} MyQueue;MyQueue* myQueueCreate() 
{MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));STInit(&(obj->pushst));STInit(&(obj->popst));return obj;
}
void myQueuePush(MyQueue* obj, int x) 
{STPush(&(obj->pushst),x);
}int myQueuePop(MyQueue* obj) 
{if(!STEmpty(&(obj->popst))){int ret=STTop(&(obj->popst));STPop(&(obj->popst));return ret;}else{while(!STEmpty(&(obj->pushst))){STPush(&(obj->popst),STTop(&(obj->pushst)));STPop(&(obj->pushst));}int ret=STTop(&(obj->popst));STPop(&(obj->popst));return ret;}
}int myQueuePeek(MyQueue* obj) 
{if(!STEmpty(&(obj->popst))){int ret=STTop(&(obj->popst));return ret;}else{while(!STEmpty(&(obj->pushst))){STPush(&(obj->popst),STTop(&(obj->pushst)));STPop(&(obj->pushst));}int ret=STTop(&(obj->popst));return ret;}}bool myQueueEmpty(MyQueue* obj) 
{return STEmpty(&(obj->pushst)) && STEmpty(&(obj->popst));
}void myQueueFree(MyQueue* obj) 
{STDesTroy(&(obj->pushst));STDesTroy(&(obj->popst));free(obj);
}

622. 設計循環隊列 - 力扣（LeetCode）

//我們用數組的結構設計循環隊列
//這一題要善于運用模除的運算從而達到利用舊空間的效果
typedef struct {int front;int rear;int*arr;int capacity;
} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{return obj->rear==obj->front;
}bool myCircularQueueIsFull(MyCircularQueue* obj) 
{return (obj->rear+1)%(obj->capacity)==obj->front;
}MyCircularQueue* myCircularQueueCreate(int k) 
{MyCircularQueue*cirque=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));cirque -> front=0;//指向 隊頭元素（即下一個要出隊的元素）。cirque -> rear= 0;//rear指向的是隊尾元素的下一個位置cirque -> arr=(int*)malloc(sizeof(int)*(k+1));//多開辟一個空間以區分隊列滿和空的狀態cirque->capacity=k+1;return cirque;
}
//尾插
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{if(!myCircularQueueIsFull(obj)){obj->arr[(obj->rear)++]=value;obj->rear=(obj->rear)%(obj->capacity);return true;}return false;
}
//頭刪
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{if(myCircularQueueIsEmpty(obj)){return false;}obj->front= ( obj->front+1)%(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->rear-1+obj->capacity)%(obj->capacity)];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}

解析：圖中我們解釋了如何插入和刪除元素

設計循環雙端隊列

雙端隊列（Deque，Double-Ended Queue）是一種支持?隊頭（front）和隊尾（rear）兩端高效插入和刪除?的數據結構。

上一題我們實現了循環隊列的實現，有了上一題的基礎，我們就能利用循環隊列來實現雙端隊列：

//雙端隊列中：
//front 直接指向當前隊頭元素（即下一個從隊頭出隊的元素）。
//rear 指向隊尾的下一個空位（即下一個插入隊尾的位置）。
//在隊頭插入數據時，要先改變front指向；同理，在隊尾插入元素以后，要改變rear的指向
//然而，插入元素后不能同時讓front和rear同時遞增或同時遞減
//我們就使在隊頭插入數據后，front--，隊尾插入數據后rear++typedef struct {int front;int rear;int capacity;int*arr;
} MyCircularDeque;MyCircularDeque* myCircularDequeCreate(int k) 
{MyCircularDeque* obj=(MyCircularDeque*)malloc(sizeof(MyCircularDeque));obj->front=obj->rear=0;obj->arr=(int*)malloc(sizeof(int)*(k+1));obj->capacity=k+1;return obj;
}bool myCircularDequeIsEmpty(MyCircularDeque* obj) 
{return obj->rear==obj->front;
}bool myCircularDequeIsFull(MyCircularDeque* obj) 
{return (obj->rear+1)%(obj->capacity)==obj->front;
}
//頭插
bool myCircularDequeInsertFront(MyCircularDeque* obj, int value) 
{if(myCircularDequeIsFull(obj)){return false;}//front指向的是隊頭元素，所以我們再進行頭插時，需要先改變隊頭指向obj->front=(obj->front-1+obj->capacity)%(obj->capacity);obj->arr[obj->front]=value;return true;
}bool myCircularDequeInsertLast(MyCircularDeque* obj, int value) 
{if(myCircularDequeIsFull(obj)){return false;}obj->arr[obj->rear]=value;//改變rear指向obj->rear=(obj->rear+1)%(obj->capacity);return true;
}bool myCircularDequeDeleteFront(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return false;}//插入元素是讓front--，那么刪除元素就要讓front++obj->front=(obj->front+1)%(obj->capacity);return true;
}bool myCircularDequeDeleteLast(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return false;}obj->rear=(obj->rear-1+obj->capacity)%(obj->capacity);return true;
}int myCircularDequeGetFront(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return -1;}return obj->arr[obj->front];
}int myCircularDequeGetRear(MyCircularDeque* obj) 
{if(myCircularDequeIsEmpty(obj)){return -1;}return obj->arr[(obj->rear-1+obj->capacity)%(obj->capacity)];
}void myCircularDequeFree(MyCircularDeque* obj) 
{free(obj->arr);obj->arr=NULL;obj->front=obj->rear=obj->capacity=0;free(obj);obj=NULL;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/93650.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/93650.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/93650.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Java基礎 8.19

Java基礎 8.19

目錄 1.局部內部類的使用 總結 1.局部內部類的使用 說明：局部內部類是定義在外部類的局部位置，比如方法中，并且有類名可以直接訪問外部類的所有成員，包含私有的不能添加訪問修飾符，因為它的地位就是一個局部變量。局…
閱讀更多...
從父類到子類：C++ 繼承的奇妙旅程（2）

從父類到子類：C++ 繼承的奇妙旅程（2）

前言：各位代碼航海家，歡迎回到C繼承宇宙！上回我們解鎖了繼承的「基礎裝備包」，成功馴服了public、protected和花式成員隱藏術。但——??前方高能預警： 繼承世界的暗流涌動遠不止于此！今天我們將勇闖三大神…
閱讀更多...
【圖像算法 - 16】庖丁解牛：基于YOLO12與OpenCV的車輛部件級實例分割實戰（附完整代碼）

【圖像算法 - 16】庖丁解牛：基于YOLO12與OpenCV的車輛部件級實例分割實戰（附完整代碼）

庖丁解牛：基于YOLO12與OpenCV的車輛部件級實例分割實戰（附完整代碼） 摘要： 告別“只見整車不見細節”！本文將帶您深入實戰，利用YOLO12-seg訓練實例分割模型，結合OpenCV的強大圖像處理能力&…
閱讀更多...
ubuntu22.04配置遠程桌面

ubuntu22.04配置遠程桌面

文章目錄前言檢查桌面類型xorg遠程桌面(xrdp)安裝xrdpxrdp添加到ssl-certwayland遠程桌面(gnome-remote-desktop)檢查安裝開啟開啟狀況檢查自動登錄奇技淫巧前言 在windows上使用遠程桌面服務，連接ubuntu主機的遠程桌面 檢查桌面類型 查看桌面類型、協議 echo $…
閱讀更多...
SQL Server 中子查詢、臨時表與 CTE 的選擇與對比

SQL Server 中子查詢、臨時表與 CTE 的選擇與對比

在 SQL Server 的實際開發過程中，我們常常需要將復雜的查詢邏輯分解為多個階段進行處理。實現這一目標的常見手段有 子查詢 (Subquery)、臨時表 (Temporary Table) 和 CTE (Common Table Expression)。這三者在語法、執行效率以及可維護性方面各有優勢與局限。如何選…
閱讀更多...
肖臻《區塊鏈技術與應用》第20-22講 - 以太坊難度調整、權益證明和智能合約

肖臻《區塊鏈技術與應用》第20-22講 - 以太坊難度調整、權益證明和智能合約

以太坊的“冰河時代”：詳解難度調整算法與“難度炸彈” 摘要： 為了實現遠快于比特幣的十幾秒出塊速度，以太坊必須設計一套更為靈敏和復雜的挖礦難度調整算法。本文基于北京大學肖臻老師的公開課內容，深入剖析了以太坊獨特的逐塊難度調整機制。文章首先解釋了其維持15秒平均…
閱讀更多...
C++中內存池（Memory Pool）詳解和完整示例

C++中內存池（Memory Pool）詳解和完整示例

1. 什么是內存池？ 內存池（Memory Pool / Pool Allocator） 是一種內存管理機制，提前向系統申請一大塊內存，再在這塊內存里切分、分配和回收。 它相當于在用戶空間建立了一層 “小型堆管理器”，避免頻繁調用系…
閱讀更多...
測試 Next.js 應用：工具與策略

測試 Next.js 應用：工具與策略

1. 引言 Next.js 作為一個基于 React 的全棧框架，在構建復雜 Web 應用時，測試是確保代碼質量、功能穩定性和用戶體驗的關鍵步驟。測試可以分為單元測試、集成測試和端到端測試三種類型，每種類型針對不同的層面：單元測試驗證單個組…
閱讀更多...
IP 分片和組裝的具體過程

IP 分片和組裝的具體過程

IP 分片和組裝的具體過程 在這里插入圖片描述 ? 16 位標識(id): 唯一的標識主機發送的報文. 如果 IP 報文在數據鏈路層被分片了, 那么每一個片里面的這個 id 都是相同的. ? 3 位標志字段: 第一位保留(保留的意思是現在不用, 但是還沒想好說不定以后要用到). 第二位置為 1 表示…
閱讀更多...
數據倉庫OLTPOLAP維度講解

數據倉庫OLTPOLAP維度講解

?博客主頁： https://blog.csdn.net/m0_63815035?typeblog 💗《博客內容》：大數據、Java、測試開發、Python、Android、Go、Node、Android前端小程序等相關領域知識 📢博客專欄： https://blog.csdn.net/m0_63815035/…
閱讀更多...
OpenHarmony之編譯配置白名單機制深度解析：構建系統的安全防線

OpenHarmony之編譯配置白名單機制深度解析：構建系統的安全防線

一、白名單機制概述 在OpenHarmony的構建系統中，compile_standard_whitelist.json是一個關鍵的安全驗證機制，它作為編譯過程中的"守門人"，確保只有經過驗證的組件和依賴關系才能被納入最終構建產物。這個機制是OpenHarmony構建系統…
閱讀更多...
backward怎么計算的是torch.tensor(2.0, requires_grad=True)變量的梯度

backward怎么計算的是torch.tensor(2.0, requires_grad=True)變量的梯度

import torch import torch.nn as nn import torch.optim as optim# 一個參數 w 2 w torch.tensor(2.0, requires_gradTrue) # 預測值 y_pred w * 3 # 6 # 真實值 y_true torch.tensor(10.0) # 損失 (預測 - 真實)^2 loss (y_pred - y_true) ** 2 # (6-10)^2 16loss.b…
閱讀更多...
戴永紅×數圖：重構零售空間價值，讓陳列創造效益！

戴永紅×數圖：重構零售空間價值，讓陳列創造效益！

風雨同舟，智贏未來。近日，湖南戴永紅商業連鎖有限公司（以下簡稱“戴永紅”）正式攜手數圖信息科技有限公司，全面啟動“可視化品類空間管理”項目。以數圖可視化陳列系統為引擎，雙方將共同推進企業零售管理的…
閱讀更多...
排查Redis數據傾斜引發的性能瓶頸

排查Redis數據傾斜引發的性能瓶頸

以下是針對 Redis 數據傾斜問題的完整排查與優化方案，結合實戰案例說明如何提升吞吐量和響應速度：一、問題現象定位1. ?性能監控異常?# Redis集群節點負載差異 $ redis-cli -c cluster nodes | grep master e1d7b... 10.0.0.1:637916379 master - 0 16…
閱讀更多...
元宇宙的硬件設備：從 VR 頭顯到腦機接口

元宇宙的硬件設備：從 VR 頭顯到腦機接口

1 元宇宙的主流硬件設備1.1 VR 頭顯：沉浸式體驗的核心入口VR 頭顯是當前進入元宇宙最主要的硬件設備，通過封閉的顯示系統為用戶營造沉浸式虛擬環境。主流 VR 頭顯采用雙屏 LCD 或 OLED 顯示技術，單眼分辨率已從早期的 1080P 提升至 4K 級別&a…
閱讀更多...
具身智能2硬件架構（人形機器人）摘自Openloong社區

具身智能2硬件架構（人形機器人）摘自Openloong社區

青龍人形機器人： 硬件 身體全身自由度43，手部自由度6*2，電池續航3h，運動控制算法（zmp/slip/mpc/深度學習）MPC+WBC+強化學習，54Tops（FP16），具有路徑建圖和自主導航能力，感官系統深度視覺傳感器*3全景環視*1，具備語音識別與聲源定位，可擴展嗅覺傳感器 OpenLoong通…
閱讀更多...
JavaScript 性能優化：new Map vs Array.find() 查找速度深度對比

JavaScript 性能優化：new Map vs Array.find() 查找速度深度對比

前言在前端開發中，我們經常需要從數據集合中查找特定元素。對于小規模數據，使用 Array.find()方法簡單直接，但當數據量增大時，性能問題就會顯現。本文將深入對比 Map和 Array.find()在數據查找方面的性能差異，并通過實…
閱讀更多...
棧與隊列leetcode題型總結

棧與隊列leetcode題型總結

1. 常用表格總結數據結構常見應用場景時間復雜度（入/出/查）LeetCode 高頻題棧（Stack）括號匹配、單調棧、DFS入棧 O(1) / 出棧 O(1) / 查頂 O(1)20 有效的括號, 155 最小棧, 739 每日溫度隊列（Queue）層序遍歷…
閱讀更多...
云原生俱樂部-RH124知識點總結（3）

云原生俱樂部-RH124知識點總結（3）

寫到這RH124的內容已經過半了，雖然內容不多，但是還是不太好寫。因為簡單的命令不想寫，至于理解上也沒什么難度，不過還是要保證整體內容的都要講到。這篇文章就把RH124剩下的內容都完結吧，主要還剩下配置和保護SSH、管理…
閱讀更多...
安裝DDNS-go

安裝DDNS-go

wget https://github.com/jeessy2/ddns-go/releases/download/v6.12.2/ddns-go_6.12.2_linux_x86_64.tar.gz tar zxvf ddns-go_6.12.2_linux_x86_64.tar.gz sudo ./ddns-go -s install
閱讀更多...
最新文章

Copyright @ 2022~2023