棧隊列經典OJ題（詳細過程）

1.?有效的括號 - 力扣（LeetCode）

? 第一題判斷有效的括號，這道題我們會用到棧的知識，棧是后進先出的，可以根據這個來解這道題，先看一下題目和示例。

1.1整體思路?

我們通過示例可以看出括號匹配就返回true，不匹配就返回false，這里的思路就是使用棧，如果是左括號，我們就入棧，如果是右括號，我們就取棧頂元素和右括號進行比較，如果匹配就比較下一個，不匹配直接返回false，我們可以結合圖例來理解一下！

?以上是一些常見的例子，但是也有一些特殊的情況

1.']'只有一個右括號時，這個時候我們就需要加一些條件，如果棧頂沒有元素，證明沒有左括號入棧，那么也就是說沒有左括號和右括號匹配，那就直接返回false。

2.'['只有一個括號時，那么也就是說只有左括號入棧，然后就直接返回了，這里我們可以用判斷一下棧是否為空，用bool來返回，如果為空，返回true，如果不是空，證明棧里還有左括號，那也說明左括號和右擴號的數量不匹配，這樣就可以有效解決了

1.2代碼分析?

因為還沒有學C++，所以這里的棧都是自己模擬實現的

1.3整體代碼

typedef char STDatatype;typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;//函數聲明
//函數的初始化和銷毀
void STInit(ST* pst);
void STDestroy(ST* pst);//進棧和出棧
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);//棧頂
STDatatype STTop(ST* pst);//棧是否為空
bool STEmpty(ST* pst);//個數
int STSize(ST* pst);
//函數的初始化和銷毀
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;
}
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}
//進棧和出棧
void STPush(ST* pst, STDatatype x)
{assert(pst);if (pst->capacity == pst->top){//增加容量int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDatatype* tmp = (STDatatype*)realloc(pst->a,sizeof(STDatatype)*newcapacity);if (tmp == NULL){perror("realloc");exit(1);}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}
//棧頂
STDatatype STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
//棧是否為空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//等于就是空，不等于0就是非空
}
//個數
int STSize(ST* pst)
{assert(pst);return pst->top;
}
bool isValid(char* s) {ST st;STInit(&st);while(*s != 0){//左括號入棧if(*s == '(' || *s == '[' || *s == '{'){STPush(&st,*s);}else{if(STEmpty(&st)){return false;}char top = STTop(&st);STPop(&st);if(top == '(' && *s != ')'|| top == '{' && *s != '}'|| top == '[' && *s != ']'){return false;}}++s;}bool ret = STEmpty(&st);return ret;
}

?2.?用隊列實現棧

這道題是讓我們用兩個隊列來實現一個棧，我們知道隊列是先進先出的，而棧是后進先出的，那我們要如何實現呢？

2.1整體思路：

這道題的思路就是我們把要插入的數據放到那個非空的隊列中，要保持一個隊列是空，一個隊列是非空，注意不可以兩個隊列都有數據，這樣我們會把自己繞進去！要刪除數據的時候，將非空隊列的最后一個數據留下來，將其他的插入到空的隊列當中，然后再將留下的那個數據刪除即可。畫圖來理解一下

?

2.2 代碼分析

2.3整體代碼?

//創建節點typedef int QDatatype;
typedef struct Queuenode
{QDatatype val;struct Queuenode* next;
}Qnode;//定義一個結構體存放指針
typedef struct Queue
{Qnode* phead;Qnode* ptail;int size;
}Queue;//隊列的初始化和銷毀
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);//隊列的插入和刪除
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);//取隊列頭和尾的值
QDatatype QueueFront(Queue* pq);
QDatatype QueueBank(Queue* pq);//是否為空
bool QueueEmpty(Queue* pq);//size
int QueueSize(Queue* pq);//隊列的初始化和銷毀
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
void QueueDestory(Queue* pq)
{assert(pq);Qnode* cur = pq->phead;while (cur){Qnode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}//隊列的插入和刪除
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));if (newnode == NULL){perror("malloc:");exit(1);}//申請成功newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}void QueuePop(Queue* pq)
{assert(pq);assert(pq->size != 0);//一個節點if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//多個節點Qnode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}//取隊列頭和尾的值
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
QDatatype QueueBank(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}//是否為空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}//size
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}//匿名結構體
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* noempty = &(obj->q2);if(!QueueEmpty(&(obj->q1))){empty = &(obj->q2);noempty = &(obj->q1);}while(QueueSize(noempty) > 1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}int top = QueueFront(noempty);QueuePop(noempty);return top;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&(obj->q1))){return QueueBank(&(obj->q1));}else{return QueueBank(&(obj->q2));}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2));
}void myStackFree(MyStack* obj) {QueueDestory(&(obj->q1));QueueDestory(&(obj->q2));free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

?3.?用棧實現隊列

這道題是用兩個棧實現隊列，棧是后進先出，隊列是先進先出，這個就比較好實現了

3.1整體思路

我們可以建一個pushst和一個popst，一個用來插入數據，一個用來刪除數據，我們可以想一下將數據插入到pushst，棧是后進先出，那么我們將pushst的數據倒到popst，他們的順序就發生了改變，這個時候popst棧頂的數據也就是隊列第一個要出的數據，我們可以畫圖來看一下。這里還有一個小技巧，當popst不為空的時候，取棧頂就是隊列要出的數據，這里不用來回倒，插入數據直接插入pustst即可，當popst為空時把pushst的數據都倒入到popst棧中

3.2代碼分析?

3.3整體代碼?

typedef int STDatatype;typedef struct Stack
{STDatatype* a;int top;int capacity;
}ST;//函數聲明
//函數的初始化和銷毀
void STInit(ST* pst);
void STDestroy(ST* pst);//進棧和出棧
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);//棧頂
STDatatype STTop(ST* pst);//棧是否為空
bool STEmpty(ST* pst);//個數
int STSize(ST* pst);//函數的初始化和銷毀
void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->top = pst->capacity = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//進棧和出棧
void STPush(ST* pst, STDatatype x)
{assert(pst);if (pst->capacity == pst->top){//增加容量int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;STDatatype* tmp = (STDatatype*)realloc(pst->a,sizeof(STDatatype)*newcapacity);if (tmp == NULL){perror("realloc");exit(1);}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}//棧頂
STDatatype STTop(ST* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}//棧是否為空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;//等于就是空，不等于0就是非空
}//個數
int STSize(ST* pst)
{assert(pst);return pst->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 myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->popst)){while(!STEmpty(&obj->pushst)){STPush(&obj->popst,STTop(&obj->pushst));STPop(&obj->pushst);}}return STTop(&obj->popst);
}int myQueuePop(MyQueue* obj) {int f = myQueuePeek(obj);STPop(&obj->popst);return f;
}bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->pushst) && STEmpty(&obj->popst);
}void myQueueFree(MyQueue* obj) {STDestroy(&obj->popst);STDestroy(&obj->pushst);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

4.???????設計循環隊列

這道題是讓我們設計一個循環隊列，隊列是先進先出的，是一個循環，可以把他比較一個圖書館的桌子，有四個座位，也就是說最多可以坐四個人，如果超過四個人后面的人就要等待在坐的四個人有人坐，再坐進去，拿這個例子我們就可以很好的理解這個題目了！

4.1整體思路

這道題有多種解法，可以用鏈表來做，也可以用數組來做，在這里我還是用數組來做，鏈表比較麻煩，不論是在申請空間，還是找尾節點的前驅節點，大家感興趣可以拿鏈表做一下，這里就拿數組做了，拿數組做也有出現一些小問題，如果我們只申請k個空間，那么數組是空還是滿我們就分不清了，這里可以畫圖來看一下!

這里有兩種解法，一個是定義一個計數器，還有一個是多開一個空間，就是開k+1個空間，這樣我們就可以分清是空還是非空了，還有一個點就是如何讓他循環起來，就是使用%，也就是每次到尾%回到下標為0的元素，這里我就采用多開一個空間的方法了，也就是%（k+1）這里畫圖可以幫助大家理解一下?。

這里將把每一個函數都拿出來分析！

4.2代碼分析

4.2.1MyCircularQueue(k)

4.2.2isEmpty()

4.2.3isfull?

?4.2.4enQueue(value)和deQueue()

4.2.5Front和Rear

4.3整體代碼

typedef struct {int* a;int head;int tail;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->a = (int*)malloc(sizeof(int)*(k+1));obj->head = 0;obj->tail = 0;obj->k = k;return obj;  
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {return  (obj->tail+1) % (obj->k+1) == obj->head;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj)){return false;}obj->a[obj->tail] = value;obj->tail++;obj->tail %= (obj->k+1);return true;
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return false;}obj->head++;obj->head %= (obj->k+1);return true;
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}elsereturn obj->a[obj->head];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}elsereturn obj->a[(obj->tail -1 + obj->k +1) % (obj->k+1)];//return obj->tail == 0 ? obj->a[obj->k]:obj->a[obj->tail-1];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);free(obj);
}/*** Your MyCircularQueue struct will be instantiated and called as such:* MyCircularQueue* obj = myCircularQueueCreate(k);* bool param_1 = myCircularQueueEnQueue(obj, value);* bool param_2 = myCircularQueueDeQueue(obj);* int param_3 = myCircularQueueFront(obj);* int param_4 = myCircularQueueRear(obj);* bool param_5 = myCircularQueueIsEmpty(obj);* bool param_6 = myCircularQueueIsFull(obj);* myCircularQueueFree(obj);
*/

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

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

相關文章

【JAVA】BOSS系統發版藝術：構建高效、優雅的微服務部署策略

【JAVA】BOSS系統發版藝術：構建高效、優雅的微服務部署策略

在現代軟件開發領域，微服務架構與容器化部署已迅速成為行業新趨勢。微服務架構通過將應用拆分成多個小型、自治的服務單元，每個服務承擔某項特定的業務功能。而容器化部署則以其輕量級和高度可移植的特性，為這些微服務的有效打包、分發和運行…
閱讀更多...
機器學習 - 不同分類模型的比較

機器學習 - 不同分類模型的比較

一、模型訓練 本案例中，我們將通過四種不同的模型來預測泰坦尼克號乘客的生存情況。 一下是訓練的具體步驟。 加載數據 從seaborn庫中加載目標數據。該數據集包括多個特征，如 PassengerId, Pclass, Name, Sex, Age, SibSp, Parch, Ticket, Fare, Cabi…
閱讀更多...
科技查新中的工法查新點如何確立與提煉？案例講解！

科技查新中的工法查新點如何確立與提煉？案例講解！

按《工程建設工法管理辦法》( 建 質［2014］103 號) ，工法，是指以工程為對象，以工藝為核心，運用系 統工程原理，把先進技術和科學管理結合起來，經過一定工程實踐形成的綜合配套的施工方…
閱讀更多...
探索美國動態IP池：技術賦能下的網絡安全新篇章

探索美國動態IP池：技術賦能下的網絡安全新篇章

在數字化飛速發展的今天，網絡安全成為了各行各業關注的焦點。特別是在跨國業務中，如何保障數據的安全傳輸和合規性成為了企業面臨的重要挑戰。美國動態IP池作為一種新興的網絡技術，正逐漸走進人們的視野，為網絡安全提供新的解決方…
閱讀更多...
黑馬甄選離線數倉項目day02(數據采集)

黑馬甄選離線數倉項目day02(數據采集)

datax介紹 官網： https://github.com/alibaba/DataX/blob/master/introduction.md DataX 是阿里云 DataWorks數據集成 的開源版本，在阿里巴巴集團內被廣泛使用的離線數據同步工具/平臺。 DataX 實現了包括 MySQL、Oracle、OceanBase、SqlServer、Postgre…
閱讀更多...
Java中List接口中方法的使用（初學者指南）

Java中List接口中方法的使用（初學者指南）

Java中List接口中方法的使用（初學者指南） 在Java中，List接口是Collection接口的子接口，它表示一個有序的集合，其中的元素都可以重復。List接口提供了許多額外的方法，用于對元素進行插入、刪除、查詢等操作…
閱讀更多...
計算機Java項目｜Springboot學生讀書筆記共享

計算機Java項目｜Springboot學生讀書筆記共享

作者主頁：編程指南針 作者簡介：Java領域優質創作者、CSDN博客專家 、CSDN內容合伙人、掘金特邀作者、阿里云博客專家、51CTO特邀作者、多年架構師設計經驗、騰訊課堂常駐講師 主要內容：Java項目、Python項目、前端項目、人工智能與大數據、簡…
閱讀更多...
C++通過json文件配置參數

C++通過json文件配置參數

一、安裝nlohmann json nlohmann json：安裝_nlohmann安裝-CSDN博客 依次執行下面指令： git clone https://gitee.com/cuihongxi/mov_from_github.gitcd json-developmkdir buildcd buildcmake ..makesudo make install 二、安裝完成后使用 #include…
閱讀更多...
華為設備display查看命令

華為設備display查看命令

display version //查看版本信息 display current-configuration //查看配置詳情 display this //查看當前視圖有效配置 display ip routing-table //查看路由表 display ip routing-table 192.168.3.1 //查看去往3.1的路由 display ip interface brief //查看接口下ip信息 dis…
閱讀更多...
想跨境出海？云手機提供了一種可能性

想跨境出海？云手機提供了一種可能性

全球化時代，越來越多的中國電商開始將目光投向了海外市場。這并不是偶然，而是他們在長期的市場運營中，看到了出海的必要性和潛在的機會。 中國的電商市場無疑是全球最大也最發達的之一。然而，隨著市場的不斷發展和競爭的日益加劇…
閱讀更多...
visual studio2022 JNI極簡開發流程

visual studio2022 JNI極簡開發流程

文章目錄 1 創建java類2 生成JNI頭文件3 使用visual studio2022創建DLL項目3.1 選擇模板中（Windows桌面向導）3.2 為項目命名3.3 選擇應用程序類型為動態鏈接庫3.4 項目概覽 4 導入需要的頭文件4.1 導入需要的頭文件4.2 修改頭文件 5 編寫C實現6 生成dll文…
閱讀更多...
服務器3389端口，服務器3389端口風險提示的應對措施

服務器3389端口，服務器3389端口風險提示的應對措施

3389端口是Windows操作系統中遠程桌面協議（RDP）的默認端口。一旦該端口被惡意攻擊者利用，可能會導致未經授權的遠程訪問和數據泄露等嚴重安全問題。 針對此風險，強烈建議您采取以下措施： 1. 修改默認端口：…
閱讀更多...
Java面試之抽象類和接口

Java面試之抽象類和接口

Java的一個重要特性就是抽象，抽象是指將具體的事物抽象成更一般化、更抽象化的概念或模型。在Java中，抽象可以通過抽象類和接口來實現，它們讓你能夠定義一些方法但不提供具體實現，從而讓子類去實現具體細節。 一、抽象類&#xf…
閱讀更多...
springboot3 集成spring-authorization-server （一 基礎篇）

springboot3 集成spring-authorization-server （一 基礎篇）

官方文檔 Spring Authorization Server 環境介紹 java&#xff1a;17 SpringBoot&#xff1a;3.2.0 SpringCloud&#xff1a;2023.0.0 引入maven配置 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter…
閱讀更多...
識別AI論文生成內容，降低論文高AI率

識別AI論文生成內容，降低論文高AI率

AI寫作工具能幫我們在短時間內高效生成一篇畢業論文、開通報告、文獻綜述、任務書、調研報告、期刊論文、課程論文等等&#xff0c;導致許多人開始使用AI寫作工具作為撰寫學術論文的輔助手段。而學術界為了杜絕此行為&#xff0c;開始使用AIGC檢測系統來判斷文章是由AI生成還是…
閱讀更多...
解鎖商業AI，賦能新質生產力發展——思愛普中國峰會探展全紀錄

解鎖商業AI，賦能新質生產力發展——思愛普中國峰會探展全紀錄

ITValue 鈦媒體獨家探秘思愛普中國峰會&#xff0c;帶你深刻感受SAP助力企業利用以商業AI為代表的數字化技術&#xff0c;實現質的飛躍&#xff0c;通過全數據、全球化、全綠色賦能新型中國企業發展新質生產力。 首發&#xff5c;鈦媒體APP ITValue 5月10日&#xff0c;一年一度…
閱讀更多...
基于NTP服務器獲取網絡時間的實現

基于NTP服務器獲取網絡時間的實現

文章目錄 1 NTP1.1 簡介1.2 包結構1.3 UNIX 時間戳和NTP時間戳 2 代碼實現2.1 實現步驟2.2 完整代碼 3 結果 在某些場景下&#xff0c;單片機需要通過網絡獲取準確的時間進行數據同步&#xff0c;例如日志記錄、定時任務等。然而&#xff0c;單片機本身無法直接獲得準確的標準時…
閱讀更多...
Vue的學習 —— ＜vue指令＞

Vue的學習 —— ＜vue指令＞

目錄 前言 正文 內容渲染指令 內容渲染指令的使用方法 v-text v-html 屬性綁定指令 雙向數據綁定指令 事件綁定指令 條件渲染指令 循環列表渲染指令 偵聽器 前言 在完成Vue開發環境的搭建后&#xff0c;若想將Vue應用于實際項目&#xff0c;首要任務是學習Vue的基…
閱讀更多...
ORA-00932: inconsistent datatypes: expected - got CLOB的分析解決方案

ORA-00932: inconsistent datatypes: expected - got CLOB的分析解決方案

最近在項目中遇到查詢數據時報ORA-00932: inconsistent datatypes: expected - got CLOB錯誤&#xff0c;這個錯誤很明顯是由于查詢時類型的不匹配造成的。 問題分析&#xff1a; 一、檢查你的查詢的實體的類型是否于數據庫的保持一致&#xff0c;如果不一致&#xff0c;那么需…
閱讀更多...
333_C++_編寫一個go函數每次從文件中讀取固定大小數據，且go作為回調，傳遞給其他函數中，多次調用，完成逐塊傳輸數據

333_C++_編寫一個go函數每次從文件中讀取固定大小數據，且go作為回調，傳遞給其他函數中，多次調用，完成逐塊傳輸數據

(core工程文件) tick_transfer_all_t類是一個用于異步傳輸數據的輔助類，它在某個異步操作完成后將_tick的值設置為0，并返回傳輸的結果 namespace hl {namespace http{namespace __detail{class tick_transfer_all_t{boost::shared_ptr<unsigned long long> _tick
閱讀更多...
最新文章

Copyright @ 2022~2023