算法---棧和隊列

棧和隊列

  • 1 棧
    • 棧的順序存儲
    • 棧的鏈式存儲
  • 2 隊列
    • 隊列的順序存儲
    • 隊列的鏈式存儲
  • 3 棧和隊列的應用
    • 用棧實現隊列
    • 用隊列實現棧
    • 最小棧

1 棧

參考文章：
https://zhuanlan.zhihu.com/p/346164833
https://zhuanlan.zhihu.com/p/120965372#:~:text=%E6%A0%88%E6%98%AF%E4%B8%80%E7%A7%8D%20%E5%90%8E%E8%BF%9B%E5%85%88%E5%87%BA%EF%BC%88LIFO%EF%BC%89,%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%20%E8%BF%9B%E6%A0%88%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%B8%BAa1%2Ca2%2Ca3%2Ca4%2Ca5%EF%BC%8C%E5%87%BA%E6%A0%88%E7%9A%84%E9%A1%BA%E5%BA%8F%E4%B8%BAa5%2Ca4%2Ca3%2Ca2%2Ca1

棧是一種特殊的線性表，僅允許在一端進行插入和刪除。被允許插入和刪除的一端為棧頂（top），另一端稱為棧底（bottom），棧底是固定的，不允許進行插入和刪除
在這里插入圖片描述
棧的主要基本操作有：

  1. InitStack(&S)：初始化棧
  2. StackEmpty(S)：判斷一個棧是否為空
  3. Push(&S,x)：進棧，若棧未滿，則將x加入到棧頂
  4. pop(&S,&x)：出棧，若棧非空，則將棧頂元素出棧，并用x返回

棧的順序存儲

采用順序存儲的棧稱為順序棧，用數組實現。
棧的定義為：

#define STACK_SIZE 100typedef int ElmType;typedef struct{int top;    /* 棧頂指針 */ElmType data[STACK_SIZE];   /* 順序棧 */
}SqStack;
  • 棧頂指針：S.top，初始時設置S.top = -1；棧頂元素：S.data[top]；
  • 進棧操作：先判斷S.top==STACK_SIZE-1，若棧不滿，S.top加1，然后將值送到棧頂。
  • 出棧操作：棧非空時，先去棧頂元素值，然后再將棧頂指針減1
  • 棧空條件：S.top==-1
  • 棧滿條件：S.top==STACK_SIZE-1
  • 棧長：S.top+1

棧的鏈式存儲

采用鏈式存儲的棧稱為鏈棧，鏈棧的優點是便于多個棧共享存儲空間和提高其效率，且不存在棧滿上溢的情況。通常采用單鏈表實現，并規定所有操作都是在單鏈表的表頭進行的。這里規定鏈棧沒有頭結點，top指向棧頂元素，
請添加圖片描述
鏈棧的存儲可定義為：

typedef int ElemType;
typedef struct LinkNode{ElemType data;struct LinkNode *next;
}LinkStack;

2 隊列

隊列是只允許在一端進程插入操作，在另一端進行刪除操作的線性表。被允許插入的一端叫隊尾（rear），被允許刪除的一端叫隊頭（front）。

請添加圖片描述
隊列的主要基本操作有：

  1. InitQueue(&Q)：初始化隊列
  2. QueueEmpty(Q)：判斷隊列是否為空
  3. QueueLenght(Q)：判斷隊列中元素的個數
  4. push(&Q,x)：入隊，如果隊列沒有滿，就在隊尾插入x
  5. pop(&Q,&x)：出隊，如果隊列非空，就在隊首刪除一個元素，并用x返回

隊列的順序存儲

類型定義為：

#define QUEUE_SIZE 100
typedef int ElemType;
typedef struct 
{ElemType data[QUEUE_SIZE];  /* 隊列 */int front;  /* 隊首 */int rear;   /* 隊尾 */
}SqQueue;

由于普通隊列存在溢出問題，所以我們用循環隊列，循環隊列的定義和普通隊列定義一樣。
請添加圖片描述

說明：這里浪費一個存儲空間

  • 初始化：rear=front=0
  • 添加一個元素：如果隊列沒有滿，則插入，即Q[rear] = x,rear= （rear+1）%QUEUE_SIZE
  • 刪除一個元素：如果隊列非空，則刪除，即*x=Q[front]，front = （front+1）% QUEUE_SIZE
  • 判斷隊列是否為空：rear==front
  • 判斷隊列是否滿：(rear+1)%QUEUE_SIZE==front
  • 隊列元素個數：(rear-front+QUEUE_SIZE)%QUEUE_SIZE

隊列的鏈式存儲

隊列的數組實現比較麻煩，需要考慮各種邊界情況，所以通常使用鏈表形式來實現隊列。

使用單向鏈表來實現鏈式隊列，鏈式隊列中存儲front和rear即可。

typedef int ElemType;
typedef struct node
{int date;struct node *next;
}LinkNode;
typedef struct queue{LinkNode *front;LinkNode *rear;
}LinkQueue;

3 棧和隊列的應用

用棧實現隊列

參考文章：https://cloud.tencent.com/developer/article/1643318

LeedCode題目位置：232. 用棧實現隊列

隊列的特性是新加入的元素在隊尾，最先入隊的元素排在隊首，按隊首到隊尾的順序依次出棧。用棧實現隊列，需要把新加入的元素保留在棧底，保證棧頂是隊列最先加入的元素。

所以我們用兩個棧A、B來實現，每次入隊時，先把存放數據的棧A彈出到另一個棧B，然后把數據存到A，最后把B中的元素依次彈出壓入A棧中，這樣保證了新加入的元素在棧底。
請添加圖片描述
隊列出隊是把隊列隊首的刪除，對應棧是把棧A的棧頂元素刪除。

實現代碼如下：

#include <stdlib.h>typedef char bool;#define SIZE 100
#define false 0
#define true 1
/* 棧的定義 */
typedef struct{int length;int data[SIZE];
}Stack;/* 初始化棧 */
Stack *initStack()
{Stack * ret = malloc(sizeof(Stack));ret->length=-1;return ret;
}/* 判斷棧是否為空 */
bool StackEmpty(Stack *s)
{return s->length==-1;
}/* 入棧操作 */
bool stackPush(Stack *s,int x)
{if(s->length==SIZE-1){return false;}s->length++;s->data[s->length]=x;return true;
}
/* 出棧操作 */
bool stackPop(Stack *s,int *x)
{if(s->length==-1){return false;}*x = s->data[s->length];s->length--;return true;
}/* 釋放棧 */
void freeStack(Stack *s)
{free(s);
}typedef struct {Stack *inStack;Stack *outStack;
} MyQueue;/* 創造隊列 */
MyQueue* myQueueCreate() {MyQueue *ret = (MyQueue *)malloc(sizeof(MyQueue));ret->inStack = initStack();ret->outStack = initStack();return ret;
}void myQueuePush(MyQueue* obj, int x) {int y;/* 先把棧A的元素依次彈出放到棧B */while(stackPop(obj->inStack,&y)){stackPush(obj->outStack,y);}/* 把入隊的元素放到棧A的棧底 */stackPush(obj->inStack,x);/* 依次彈出棧B的元素放到棧A */while(stackPop(obj->outStack,&y)){stackPush(obj->inStack,y);}
}int myQueuePop(MyQueue* obj) {int x;/* 刪除棧A的棧頂元素 */stackPop(obj->inStack,&x);return x;
}int myQueuePeek(MyQueue* obj) {return obj->inStack->data[obj->inStack->length];
}bool myQueueEmpty(MyQueue* obj) {return StackEmpty(obj->inStack);
}void myQueueFree(MyQueue* obj) {free(obj->inStack);free(obj->outStack);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);
*/

在這里插入圖片描述

用隊列實現棧

參考文章：https://cloud.tencent.com/developer/article/1643318
LeedCode題目位置：225. 用隊列實現棧
棧的特性是新加入的元素出現在棧頂，刪除的元素也在棧頂，隊列的特性是新加入的特性在隊尾，刪除的元素在隊首。
我們可以讓數據先入隊列，然后把隊列的以前的數據依次出隊再入隊，這樣保證了新壓入的數據在隊首，對應棧的棧頂。
請添加圖片描述
出棧的話，對應隊列的操作就是把隊首的元素刪除即可。
實現代碼如下：

#include <stdlib.h>#define false 0
#define true 1
#define SIZE 101typedef struct{int front;  // 隊首int rear;   //隊尾int data[SIZE];
}Queue;/* 初始化隊列 */
Queue * initQueue()
{Queue * ret = (Queue *)malloc(sizeof(Queue));ret->front=0;ret->rear=0;return ret;
}
/* 判斷隊列是否為空 */
bool QueueEmpty(Queue *q)
{if(q->front==q->rear){return true;}elsereturn false;
}/* 入隊 */
bool queuePush(Queue *q,int x)
{/* 隊滿 */if(q->front == (q->rear+1)%SIZE){return false;}q->data[q->rear]=x;q->rear =(q->rear+1)%SIZE;return true;
}
/* 出隊 */
bool QueuePop(Queue *q,int *x)
{/* 隊列是否為空 */if(q->front==q->rear)return false;*x = q->data[q->front];q->front = (q->front+1)%SIZE;return true;
}
/* 獲取隊首元素 */
int getQueueTop(Queue *q)
{return q->data[q->front];
}
typedef struct {Queue *q;
} MyStack;MyStack* myStackCreate() {MyStack *ret = (MyStack *)malloc(sizeof(MyStack));ret->q = initQueue();return ret;
}void myStackPush(MyStack* obj, int x) {int y;/* 計算現在有多少個元素 */int length = (obj->q->rear-obj->q->front+SIZE)%SIZE;/* x入隊 */queuePush(obj->q,x);for(int i=0;i<length;i++){/* 出隊 */QueuePop(obj->q,&y);/* 入隊 */queuePush(obj->q,y);}
}
/* 只需將隊首元素刪除 */
int myStackPop(MyStack* obj) {int x;QueuePop(obj->q,&x);return x;
}int myStackTop(MyStack* obj) {return getQueueTop(obj->q);
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(obj->q);
}void myStackFree(MyStack* obj) {free(obj->q);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);
*/

在這里插入圖片描述

最小棧

LeedCode位置：155. 最小棧
題目要求在常數時間內檢索到最小元素的棧，所以我們在棧里面設置一個變量min來記錄最小元素的位置。

當插入元素，如果插入的元素比棧內的元素都要小，這個時候需要更新min；當刪除元素時，如果此時最小的元素在棧頂，也需要更新min值。

代碼實現如下：

#include <stdlib.h>#define SIZE 30000typedef struct {int length;    //記錄元素個數,始終指向棧頂元素int min;    //記錄最小元素的位置int data[SIZE];
} MinStack;int getStackMin(MinStack *s)
{int min =0;for(int i=1;i<=s->length;i++){if(s->data[min]>s->data[i]){min = i;}}return min;
}MinStack* minStackCreate() {MinStack *ret = (MinStack *)malloc(sizeof(MinStack));ret->length = -1;ret->min = 0;return ret;
}void minStackPush(MinStack* obj, int val) {obj->data[++obj->length]=val;/* 插入的元素比棧內的元素都要小，這個時候需要更新min */if(val<obj->data[obj->min])obj->min = obj->length;
}void minStackPop(MinStack* obj) {obj->length--;/* 刪除元素時，如果此時最小的元素在棧頂，也需要更新min值 */if(obj->min==(obj->length+1)){obj->min = getStackMin(obj);}
}int minStackTop(MinStack* obj) {return obj->data[obj->length];
}int minStackGetMin(MinStack* obj) {return obj->data[obj->min];
}void minStackFree(MinStack* obj) {free(obj);
}/*** Your MinStack struct will be instantiated and called as such:* MinStack* obj = minStackCreate();* minStackPush(obj, val);* minStackPop(obj);* int param_3 = minStackTop(obj);* int param_4 = minStackGetMin(obj);* minStackFree(obj);
*/

在這里插入圖片描述

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

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

相關文章

學習網站LIST

學習網站LIST

面向對象的腳本語言Rubyhttp://rubycn.ce-lab.net/20020101.htmlRUBY文檔中心http://www.moer.net/ruby/doc/TCL腳本http://www.tclchina.com/Python快速入門http://wiki.woodpecker.org.cn/moin/WeiZhong/2006-01-17Python 研究(Dive Into Python)http://www.woodpecker.org.c…
閱讀更多...
再次參加（第七屆）商學院徒步戈壁挑戰賽，賦詞幾首

再次參加（第七屆）商學院徒步戈壁挑戰賽，賦詞幾首

2012年5月21-25日&#xff0c;再次踏上甘肅莫賀延磧戈壁&#xff0c;參加第七屆商學院徒步戈壁挑戰賽。時隔五年&#xff0c;時空轉換。 少年游 ——戈壁緣 江南物華&#xff0c;遠水碧山&#xff0c;燈火相掩映。暮宴朝歡&#xff0c;酒綠燈紅&#xff0c;躑躅夜歸人。 孤城落…
閱讀更多...
Java StackTraceElement toString（）方法與示例

Java StackTraceElement toString（）方法與示例

StackTraceElement類的toString()方法 (StackTraceElement Class toString() method) toString() method is available in java.lang package. toString()方法在java.lang包中可用。 toString() method is used to represent stack trace element as a string or in other word…
閱讀更多...
增刪改查

增刪改查

web層代碼如下&#xff1a; package beyondwsq.web;import java.io.IOException; import java.sql.SQLException; import java.util.List;import javax.servlet.ServletException; import javax.servlet.http.HttpServlet; import javax.servlet.http.HttpServletRequest; imp…
閱讀更多...
在WebBrowser中通過模擬鍵盤鼠標操控網頁中的文件上傳控件

在WebBrowser中通過模擬鍵盤鼠標操控網頁中的文件上傳控件

引言 這兩天沉迷了Google SketchUp&#xff0c;剛剛玩夠&#xff0c;一時興起&#xff0c;研究了一下WebBrowser。 我在《WebBrowser控件使用技巧分享》一文中曾談到過“我現在可以通過WebBrowser實現對各種Html元素的操控&#xff0c;唯獨無法控制Html的上傳控件”&#xff0c…
閱讀更多...
編寫最簡單的字符設備驅動

編寫最簡單的字符設備驅動

編寫最簡單的字符設備驅動1 編寫驅動代碼2 編寫makefile3 編譯和加載驅動4 編寫應用程序測試驅動參考文章&#xff1a; linux驅動開發第1講&#xff1a;帶你編寫一個最簡單的字符設備驅動 linux驅動開發第2講&#xff1a;應用層的write如何調用到驅動中的write 1 編寫驅動代碼…
閱讀更多...
Java ObjectStreamField toString（）方法與示例

Java ObjectStreamField toString（）方法與示例

ObjectStreamField類toString()方法 (ObjectStreamField Class toString() method) toString() method is available in java.io package. toString()方法在java.io包中可用。 toString() method is used to return a string that defines this field. toString()方法用于返回定…
閱讀更多...
linux內核文件描述符fd、文件索引節點inode、文件對象file關系

linux內核文件描述符fd、文件索引節點inode、文件對象file關系

文件描述符fd、文件索引節點inode、文件對象file關系1 VFS對象1.1 超級塊對象1.2 索引節點對象1.3 文件對象1.4 進程描述符1.5 files_struct2 如何根據文件描述符fd找到文件&#xff1f;1 VFS對象 在說fd、inode和file關系之前&#xff0c;我們先了解VFS的幾個概念。分別是進程…
閱讀更多...
sql2005 獲取表字段信息和視圖字段信息

sql2005 獲取表字段信息和視圖字段信息

獲取表字段名,和字段說明SELECT[Table Name]OBJECT_NAME(c.object_id), [ColumnName]c.name, [Description]ex.value FROMsys.columns c LEFTOUTERJOINsys.exte…
閱讀更多...
解析css之position

解析css之position

CSS的很多其他屬性大多容易理解&#xff0c;比如字體&#xff0c;文本&#xff0c;背景等。有些CSS書籍也會對這些簡單的屬性進行大張旗鼓的介紹&#xff0c;而偏偏忽略了對一些難纏的屬性講解&#xff0c;有避重就輕的嫌疑。CSS中主要難以理解的屬性包括盒型結構&#xff0c;以…
閱讀更多...
Java ObjectInputStream readLong（）方法（帶示例）

Java ObjectInputStream readLong（）方法（帶示例）

ObjectInputStream類readLong()方法 (ObjectInputStream Class readLong() method) readLong() method is available in java.io package. readLong()方法在java.io包中可用。 readLong() method is used to read 8 bytes (i.e. 64 bit) of long value from this ObjectInputSt…
閱讀更多...
交換瓶子（藍橋杯）

交換瓶子（藍橋杯）

有N個瓶子&#xff0c;編號 1 ~ N&#xff0c;放在架子上。 比如有5個瓶子&#xff1a; 2 1 3 5 4 要求每次拿起2個瓶子&#xff0c;交換它們的位置。 經過若干次后&#xff0c;使得瓶子的序號為&#xff1a; 1 2 3 4 5 對于這么簡單的情況&#xff0c;顯然&#xff0c;至少…
閱讀更多...
Linux設備驅動開發---字符設備驅動程序

Linux設備驅動開發---字符設備驅動程序

字符設備驅動程序1 主設備和次設備的概念設備號的注冊和釋放靜態方法動態方法區別2 設備文件操作struct file_operations與struct file、struct inode關系3 分配和注冊字符設備class_createcdev_adddevice_create4 字符設備驅動程序字符設備通過字符&#xff08;一個接一個的字…
閱讀更多...
Java LinkedHashMap getOrDefault（）方法與示例

Java LinkedHashMap getOrDefault（）方法與示例

LinkedHashMap類的getOrDefault()方法 (LinkedHashMap Class getOrDefault() method) getOrDefault() method is available in java.util package. getOrDefault()方法在java.util包中可用。 getOrDefault() method is used to get the value associated with the given key el…
閱讀更多...
Java中的異常棧軌跡和異常鏈

Java中的異常棧軌跡和異常鏈

Java中允許對異常進行再次拋出&#xff0c;以提交給上一層進行處理&#xff0c;最為明顯的例子為Java的常規異常。 常規異常&#xff1a;有Java所定義的異常&#xff0c;不需要異常聲明&#xff0c;在未被try-catch的情況下&#xff0c;會被默認上報到main()方法。 Example: pu…
閱讀更多...
貪心算法---背包問題（物品可以分割問題）

貪心算法---背包問題（物品可以分割問題）

問題背景&#xff1a; 有一天&#xff0c;阿里巴巴趕著一頭毛驢上山砍柴。砍好柴準備下山時&#xff0c;遠處突然出現一股煙塵&#xff0c;彌漫著直向上空飛揚&#xff0c;朝他這兒卷過來&#xff0c;而且越來越近。靠近以后&#xff0c;他才看清原來是一支馬隊&#xff0c;他…
閱讀更多...
同步---信號量

同步---信號量

信號量1 信號量2 驅動程序和測試程序3 內核的具體實現總結1 信號量 Linux中的信號量是一種睡眠鎖。如果有一個任務試圖獲得一個已經被占用的信號量時&#xff0c;信號量會將其放到一個等待隊列&#xff0c;然后讓其睡眠&#xff0c;這時處理器去執行其他代碼。當持有信號量的進…
閱讀更多...
Java Float類floatToIntBits（）方法與示例

Java Float類floatToIntBits（）方法與示例

Float類floatToIntBits()方法 (Float class floatToIntBits() method) floatToIntBits() method is available in java.lang package. floatToIntBits()方法在java.lang包中可用。 floatToIntBits() method follows IEEE 754 floating-point standards and according to standa…
閱讀更多...
解釋三度帶和六度帶的概念以及各坐標系如何定義

解釋三度帶和六度帶的概念以及各坐標系如何定義

★ 地形圖坐標系&#xff1a;我國的地形圖采用高斯&#xff0d;克呂格平面直角坐標系。在該坐標系中&#xff0c;橫軸&#xff1a;赤道&#xff0c;用&#xff39;表示&#xff1b;縱軸&#xff1a;中央經線&#xff0c;用&#xff38;表示&#xff1b;坐標原點&#xff1a;中央…
閱讀更多...
0-1背包問題（物品不可分割）

0-1背包問題（物品不可分割）

問題背景&#xff1a; 所謂“鐘點秘書”&#xff0c;是指年輕白領女性利用工余時間為客戶提供秘書服務&#xff0c;并按鐘點收取酬金。“鐘點秘書”為客戶提供有償服務的方式一般是&#xff1a;采用電話、電傳、上網等“遙控”式 服務&#xff0c;或親自到客戶公司處理部分業務…
閱讀更多...
最新文章

Copyright @ 2022~2023