數據結構——棧（詳細分析）

目錄

🍉引言

🍉棧的本質和特點

🍈棧的基本操作

🍈棧的特點

🍍后進先出

🍍操作受限

🍍動態調整

🍈棧的優缺點

🍍優點

🍍缺點

🍉棧的應用

棧的代碼實現

代碼說明

圖解棧的出入過程

壓棧過程

出棧過程

棧的實際應用實例

括號匹配

瀏覽器前進后退功能

代碼說明

🍉棧的實現細節和優化

🍈數組實現棧的優化

🍉引言

棧（Stack）是一種常見的數據結構，在計算機科學中具有重要的應用價值。棧的操作受限于后進先出（LIFO, Last In First Out）的原則，這種特點使得棧在處理特定類型的問題時非常高效。本文將詳細解析棧的本質和特點，并通過生活中的例子和代碼實現來深入理解棧的應用。

🍉棧的本質和特點

  • 棧是一種線性數據結構，只允許在一端進行插入和刪除操作，這一端稱為棧頂（Top）。與棧頂相對的另一端稱為棧底（Bottom），棧底是固定的，不進行操作

🍈棧的基本操作

棧有幾種基本操作：

  1. 壓棧（Push）：將一個元素添加到棧頂。
  2. 出棧（Pop）：移除并返回棧頂元素。
  3. 取棧頂元素（Peek or Top）：返回棧頂元素但不移除它。
  4. 檢查棧是否為空（isEmpty）：返回布爾值，指示棧是否為空。
  5. 檢查棧是否已滿（isFull）：返回布爾值，指示棧是否已滿（主要用于固定大小的棧）。

🍈棧的特點

🍍后進先出

  • 棧的最主要特點是后進先出，即最新加入的元素最先被移除。這種特性使得棧特別適用于某些特定的應用場景。

🍍操作受限

  • 與其他數據結構相比，棧的操作比較受限。只能在棧頂進行壓棧和出棧操作，不能直接訪問棧中的任意元素。

🍍動態調整

  • 棧可以是固定大小的，也可以是動態調整大小的。動態棧會根據需要自動調整其容量。

🍈棧的優缺點

🍍優點

  1. 簡單高效： 棧的操作簡單，只需考慮棧頂元素，因此執行速度較快。

  2. 內存管理： 棧內存的分配和釋放是自動進行的，不需要手動管理內存，避免了內存泄漏和垃圾回收的問題。

  3. 遞歸調用： 棧結構天然適合處理遞歸調用，函數的調用和返回都可以利用棧的特性。

🍍缺點

  1. 大小限制： 棧的大小通常是固定的，當數據量超過棧的容量時會導致棧溢出。

  2. 數據不靈活： 棧是一種后進先出（LIFO）的數據結構，只能在棧頂進行操作，不適合需要隨機訪問數據的場景。

  3. 局部性： 棧中的數據只能按照特定的順序訪問，缺乏靈活性，不能滿足所有的數據操作需求。

🍉棧的應用

棧在現實生活和計算機科學中都有廣泛的應用：

  1. 函數調用：計算機系統使用棧來管理函數調用。每次函數調用時，當前函數的狀態（如局部變量、返回地址等）會被壓入棧中。當函數返回時，狀態從棧中彈出并恢復。
  2. 表達式求值和語法解析：棧用于將中綴表達式轉換為后綴表達式或前綴表達式，并且在表達式求值過程中，棧也扮演重要角色。
  3. 瀏覽器的前進后退功能：瀏覽器使用兩個棧來管理用戶的瀏覽歷史，一個棧存儲前進的頁面，另一個棧存儲后退的頁面。
  4. 撤銷操作：許多軟件（如文本編輯器、圖像編輯器等）使用棧來實現撤銷和恢復功能。

棧的代碼實現

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Stack {int *items;int top;int capacity;
} Stack;// 初始化棧
Stack* createStack(int capacity) {Stack *stack = (Stack *)malloc(sizeof(Stack));stack->capacity = capacity;stack->top = -1;stack->items = (int *)malloc(capacity * sizeof(int));return stack;
}// 檢查棧是否為空
bool is_empty(Stack *stack) {return stack->top == -1;
}// 壓入元素到棧
void push(Stack *stack, int item) {if (stack->top == stack->capacity - 1) {printf("棧已滿，無法壓入元素\n");return;}stack->items[++stack->top] = item;
}// 彈出棧頂元素
int pop(Stack *stack) {if (is_empty(stack)) {printf("棧為空，無法彈出元素\n");exit(EXIT_FAILURE);}return stack->items[stack->top--];
}// 獲取棧頂元素
int peek(Stack *stack) {if (is_empty(stack)) {printf("棧為空，無法獲取棧頂元素\n");exit(EXIT_FAILURE);}return stack->items[stack->top];
}// 獲取棧的大小
int size(Stack *stack) {return stack->top + 1;
}int main() {Stack *stack = createStack(100); // 創建一個容量為100的棧push(stack, 1);push(stack, 2);push(stack, 3);printf("棧頂元素：%d\n", peek(stack));  // 輸出 3printf("出棧元素：%d\n", pop(stack));   // 輸出 3printf("棧頂元素：%d\n", peek(stack));  // 輸出 2printf("棧大小：%d\n", size(stack));    // 輸出 2// 釋放分配的內存free(stack->items);free(stack);return 0;
}

代碼說明

  1. Stack 結構體包含一個整數數組 items，一個表示棧頂索引的 top，和一個表示棧容量的 capacity。
  2. createStack 函數用于初始化棧并分配內存。
  3. is_empty 函數用于檢查棧是否為空。
  4. push 函數用于將元素壓入棧，并在棧滿時打印錯誤信息。
  5. pop 函數用于彈出棧頂元素，并在棧為空時打印錯誤信息并退出程序。
  6. peek 函數用于獲取棧頂元素，并在棧為空時打印錯誤信息并退出程序。
  7. size 函數用于獲取棧的大小（當前存儲的元素數量）。
  8. main 函數演示了棧的使用，類似于您提供的 Python 代碼示例。

圖解棧的出入過程

  • 為了更直觀地理解棧的操作過程，我們可以使用圖解的方式來展示棧的壓棧和出棧操作。

壓棧過程

  • 初始狀態：棧為空
棧: []
  • ?壓棧 1：
壓棧 1
棧: [1]
  • 壓棧 2：
壓棧 2
棧: [1, 2]
  • 壓棧 3：
壓棧 3
棧: [1, 2, 3]

出棧過程

  • 初始狀態：棧頂元素為 3
棧: [1, 2, 3]
  • 出棧 3：
出棧 3
棧: [1, 2]
  • 出棧 2：
出棧 2
棧: [1]
  • 出棧 1：
出棧 1
棧: []

棧的實際應用實例

括號匹配

  • 括號匹配問題是棧的經典應用之一，常用于編譯器和解釋器的語法解析。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>// 棧結構定義
typedef struct Stack {int top;unsigned capacity;char* array;
} Stack;// 創建棧
Stack* createStack(unsigned capacity) {Stack* stack = (Stack*) malloc(sizeof(Stack));stack->capacity = capacity;stack->top = -1;stack->array = (char*) malloc(stack->capacity * sizeof(char));return stack;
}// 判斷棧是否為空
int isEmpty(Stack* stack) {return stack->top == -1;
}// 入棧
void push(Stack* stack, char item) {stack->array[++stack->top] = item;
}// 出棧
char pop(Stack* stack) {if (isEmpty(stack))return '\0';return stack->array[stack->top--];
}// 獲取棧頂元素
char peek(Stack* stack) {if (isEmpty(stack))return '\0';return stack->array[stack->top];
}// 判斷括號是否平衡
int isBalanced(const char* expression) {Stack* stack = createStack(strlen(expression));char pairs[256] = { 0 };pairs[')'] = '(';pairs[']'] = '[';pairs['}'] = '{';for (int i = 0; i < strlen(expression); i++) {char char = expression[i];if (char == '(' || char == '{' || char == '[') {push(stack, char);} else if (char == ')' || char == '}' || char == ']') {if (isEmpty(stack) || pop(stack) != pairs[char]) {free(stack->array);free(stack);return 0; // false}}}int balanced = isEmpty(stack);free(stack->array);free(stack);return balanced;
}// 測試函數
int main() {const char* expression1 = "{[()()]}";printf("%s\n", isBalanced(expression1) ? "True" : "False");const char* expression2 = "{[(])}";printf("%s\n", isBalanced(expression2) ? "True" : "False");return 0;
}

瀏覽器前進后退功能

瀏覽器的前進和后退功能可以通過兩個棧來實現，一個棧用于存儲前進頁面，另一個棧用于存儲后退頁面：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct Node {char* data;struct Node* next;
} Node;typedef struct Stack {Node* top;
} Stack;// 初始化棧
void init_stack(Stack* stack) {stack->top = NULL;
}// 檢查棧是否為空
int is_empty(Stack* stack) {return stack->top == NULL;
}// 推入元素到棧
void push(Stack* stack, const char* data) {Node* new_node = (Node*)malloc(sizeof(Node));new_node->data = (char*)malloc(strlen(data) + 1);strcpy(new_node->data, data);new_node->next = stack->top;stack->top = new_node;
}// 彈出棧頂元素
char* pop(Stack* stack) {if (is_empty(stack)) {return NULL;}Node* temp = stack->top;char* data = temp->data;stack->top = stack->top->next;free(temp);return data;
}// 瀏覽器歷史記錄結構體
typedef struct BrowserHistory {Stack forward_stack;Stack backward_stack;char* current_page;
} BrowserHistory;// 初始化瀏覽器歷史記錄
void init_browser_history(BrowserHistory* history) {init_stack(&history->forward_stack);init_stack(&history->backward_stack);history->current_page = NULL;
}// 訪問新頁面
void visit(BrowserHistory* history, const char* page) {if (history->current_page != NULL) {push(&history->backward_stack, history->current_page);}history->current_page = (char*)malloc(strlen(page) + 1);strcpy(history->current_page, page);// 清空前進棧while (!is_empty(&history->forward_stack)) {free(pop(&history->forward_stack));}
}// 后退
char* back(BrowserHistory* history) {if (!is_empty(&history->backward_stack)) {push(&history->forward_stack, history->current_page);history->current_page = pop(&history->backward_stack);return history->current_page;} else {return NULL;  // 無法后退}
}// 前進
char* forward(BrowserHistory* history) {if (!is_empty(&history->forward_stack)) {push(&history->backward_stack, history->current_page);history->current_page = pop(&history->forward_stack);return history->current_page;} else {return NULL;  // 無法前進}
}int main() {BrowserHistory history;init_browser_history(&history);visit(&history, "Page1");visit(&history, "Page2");visit(&history, "Page3");printf("%s\n", back(&history));  // 輸出 Page2printf("%s\n", back(&history));  // 輸出 Page1printf("%s\n", forward(&history));  // 輸出 Page2return 0;
}

代碼說明

  1. 棧的實現：我們用 Node 結構體來表示棧中的節點，用 Stack 結構體來管理棧頂節點。提供了初始化、檢查空棧、推入和彈出元素的函數。
  2. 瀏覽器歷史記錄：用 BrowserHistory 結構體來管理當前頁面和兩個棧。提供了初始化、訪問新頁面、后退和前進的函數。
  3. 內存管理：使用 malloc 和 free 來動態分配和釋放內存，以避免內存泄漏。

🍉棧的實現細節和優化

  • 在實際應用中，棧的實現可以有多種方式，包括使用數組（列表）或鏈表。每種方式都有其優缺點：
  1. 數組實現棧：簡單高效，但需要預先確定棧的最大容量，可能會導致空間浪費或溢出。
  2. 鏈表實現棧：靈活，無需預先確定棧的容量，但每個節點需要額外的指針存儲空間，操作相對復雜。

🍈數組實現棧的優化

  • 為了解決數組實現棧的容量限制問題，可以使用動態數組，它會在需要時自動擴展容量：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct {int *items;int capacity;int size;
} DynamicArrayStack;// Initialize the stack
DynamicArrayStack* createStack() {DynamicArrayStack* stack = (DynamicArrayStack*)malloc(sizeof(DynamicArrayStack));stack->capacity = 1;stack->size = 0;stack->items = (int*)malloc(stack->capacity * sizeof(int));return stack;
}// Check if the stack is empty
bool isEmpty(DynamicArrayStack* stack) {return stack->size == 0;
}// Push an item onto the stack
void push(DynamicArrayStack* stack, int item) {if (stack->size == stack->capacity) {stack->capacity *= 2;stack->items = (int*)realloc(stack->items, stack->capacity * sizeof(int));}stack->items[stack->size++] = item;
}// Pop an item from the stack
int pop(DynamicArrayStack* stack) {if (isEmpty(stack)) {fprintf(stderr, "pop from empty stack\n");exit(EXIT_FAILURE);}return stack->items[--stack->size];
}// Peek at the top item of the stack
int peek(DynamicArrayStack* stack) {if (isEmpty(stack)) {fprintf(stderr, "peek from empty stack\n");exit(EXIT_FAILURE);}return stack->items[stack->size - 1];
}// Get the size of the stack
int stackSize(DynamicArrayStack* stack) {return stack->size;
}// Free the stack
void freeStack(DynamicArrayStack* stack) {free(stack->items);free(stack);
}int main() {// Create and use the dynamic array stackDynamicArrayStack* dynamicStack = createStack();push(dynamicStack, 1);push(dynamicStack, 2);push(dynamicStack, 3);printf("棧頂元素：%d\n", peek(dynamicStack)); // 輸出 3printf("出棧元素：%d\n", pop(dynamicStack));  // 輸出 3printf("棧頂元素：%d\n", peek(dynamicStack)); // 輸出 2printf("棧大小：%d\n", stackSize(dynamicStack)); // 輸出 2freeStack(dynamicStack);return 0;
}

希望這些能對剛學習算法的同學們提供些幫助哦！！！

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

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

相關文章

002 遞歸評論 mongodb websocket消息推送

002 遞歸評論 mongodb websocket消息推送

文章目錄 商品評論CommentController.javaComment.javaCommentServiceImpl.javaCommentRepository.javaCommentService.javaWebSocketConfig.javaWebSocketProcess.javaapplication.yamlproductReview.htmlindex.htmlindex.jsindex.css 訂單評論EvaluateMapper.xmlEvaluateMapp…
閱讀更多...
從零手寫實現 nginx-01-為什么不能有 java 版本的 nginx?

從零手寫實現 nginx-01-為什么不能有 java 版本的 nginx?

前言 大家好&#xff0c;我是老馬。很高興遇到你。 作為一個 java 開發者&#xff0c;工作中一直在使用 nginx。卻發現一直停留在使用層面&#xff0c;無法深入理解。 有一天我在想&#xff0c;為什么不能有一個 java 版本的 nginx 呢&#xff1f; 一者是理解 nginx 的設計…
閱讀更多...
HTTP 協議中 GET 和 POST 有什么區別?分別適用于什么場景?

HTTP 協議中 GET 和 POST 有什么區別?分別適用于什么場景?

HTTP 協議中 GET 和 POST 是兩種常用的請求方法&#xff0c;它們的區別如下: 1. 參數傳遞方式不同 GET 請求參數是在 URL 中以鍵值對的形式傳遞的&#xff0c;例如:http://www.example.com/&#xff1f;key1value1&k ey2value2。 而 POST 請求參數是在請求體中以鍵值對的…
閱讀更多...
SQOOP詳細講解

SQOOP詳細講解

SQOOP安裝及使用 SQOOP安裝及使用SQOOP安裝1、上傳并解壓2、修改文件夾名字3、修改配置文件4、修改環境變量5、添加MySQL連接驅動6、測試準備MySQL數據登錄MySQL數據庫創建student數據庫切換數據庫并導入數據另外一種導入數據的方式使用Navicat運行SQL文件導出MySQL數據庫impo…
閱讀更多...
數據訪問與Spring Data JPA

數據訪問與Spring Data JPA

數據訪問與Spring Data JPA 在現代Java應用程序中&#xff0c;持久化數據是核心功能之一。Spring Data JPA&#xff08;Java Persistence API&#xff09;為開發者提供了一種簡單且高效的方式來訪問和操作數據庫。在本博文中&#xff0c;我將向您展示如何使用Spring Data JPA來…
閱讀更多...
數據結構------二叉樹經典習題2

數據結構------二叉樹經典習題2

博主主頁: 碼農派大星. 關注博主帶你了解更多數據結構知識 1.非遞歸的前序遍歷 1.用棧來實現 2,前序遍歷是根左右, 先是根節點入棧,,然后不為空時向左遍歷,當為空時就返回向右遍歷,右為空時直接出棧,依次循環即可. public void preOrderNot(TreeNode root){Stack<TreeNo…
閱讀更多...
科技賦能，打破視障人士的溝通壁壘

科技賦能，打破視障人士的溝通壁壘

在探索如何增強盲人群體的社會參與度與幸福感的旅程中&#xff0c;盲人社交能力提升策略成為了不容忽視的一環。隨著科技的不斷進步&#xff0c;像“蝙蝠避障”這樣的輔助軟件&#xff0c;不僅在日常出行中為盲人提供了實時避障和拍照識別的便利&#xff0c;也在無形中為他們拓…
閱讀更多...
華為數通 HCIP-Datacom（H12-821）題庫

華為數通 HCIP-Datacom（H12-821）題庫

最新 HCIP-Datacom&#xff08;H12-821&#xff09;完整題庫請掃描上方二維碼訪問&#xff0c;持續更新中。 BGP路由的Update消息中可不包含以下哪些屬性&#xff1f; A、Local Preference B、AS Path C、MED D、Origin 答案&#xff1a;AC 解析&#xff1a;as-path和ori…
閱讀更多...
深度學習訓練框架——監督學習為例

深度學習訓練框架——監督學習為例

訓練框架 文章目錄 訓練框架1. 模型網絡結構2. 數據讀取與數據加載2.1Dataloater參數2.2 collate_fn 3. 優化器與學習率調整3.1 優化器3.2 學習率調度 4迭代訓練4.1 train_epoch4.2 train iteration 5.1 保存模型權重 本文內容以pytorch為例 1. 模型網絡結構 自定義網絡模型繼…
閱讀更多...
測試開發面試題

測試開發面試題

簡述自動化測試的三大等待 強制等待。直接使用time.sleep()方法讓程序暫停指定的時間。優點是實現簡單&#xff0c;缺點是不夠靈活&#xff0c;可能會導致不必要的等待時間浪費。隱式等待。設置一個固定的等待時間&#xff0c;在這個時間內不斷嘗試去查找元素&#xff0c;如果…
閱讀更多...
Java17 --- SpringCloud之Sentinel

Java17 --- SpringCloud之Sentinel

目錄 一、Sentinel下載并運行 二、創建8401微服務整合Sentinel 三、流控規則 3.1、直接模式 3.2、關聯模式 3.3、鏈路模式 3.3.1、修改8401代碼 3.3.2、創建流控模式 3.4、Warm UP&#xff08;預熱&#xff09; ?編輯 3.5、排隊等待 四、熔斷規則 4.1、慢調用比…
閱讀更多...
【C++】09.vector

【C++】09.vector

一、vector介紹和使用 1.1 vector的介紹 vector是表示可變大小數組的序列容器。就像數組一樣&#xff0c;vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問&#xff0c;和數組一樣高效。但是又不像數組&#xff0c;它的大小是可以動態改…
閱讀更多...
操作系統實驗四 （綜合實驗）設計簡單的Shell程序

操作系統實驗四 （綜合實驗）設計簡單的Shell程序

前言 因為是一年前的實驗&#xff0c;很多細節還有知識點我都已經遺忘了&#xff0c;但我還是盡可能地把各個細節講清楚&#xff0c;請見諒。 1.實驗目的 綜合利用進程控制的相關知識&#xff0c;結合對shell功能的和進程間通信手段的認知&#xff0c;編寫簡易shell程序&…
閱讀更多...
Excel透視表：快速計算數據分析指標的利器

Excel透視表：快速計算數據分析指標的利器

文章目錄 概述1.數據透視表基本操作1.1準備數據&#xff1a;1.2創建透視表&#xff1a;1.3設置透視表字段&#xff1a;1.4多級分類匯總和交叉匯總的差別1.5計算匯總數據&#xff1a;1.6透視表美化&#xff1a;1.7篩選和排序&#xff1a;1.8更新透視表&#xff1a; 2.數據透視-數…
閱讀更多...
【B站 heima】小兔鮮Vue3 項目學習筆記Day02

【B站 heima】小兔鮮Vue3 項目學習筆記Day02

文章目錄 Pinia1.使用2. pinia-計數器案例3. getters實現4. 異步action5. storeToRefsx 數據解構保持響應式6. pinia 調試 項目起步1.項目初始化和git管理2. 使用ElementPlus3. ElementPlus 主題色定制4. axios 基礎配置5. 路由設計6. 靜態資源初始化和 Error lens安裝7.scss自…
閱讀更多...
Github 2024-05-24 開源項目日報 Top10

Github 2024-05-24 開源項目日報 Top10

根據Github Trendings的統計，今日(2024-05-24統計)共有10個項目上榜。根據開發語言中項目的數量，匯總情況如下： 開發語言項目數量Python項目3非開發語言項目2TypeScript項目2JavaScript項目1Kotlin項目1C#項目1C++項目1Shell項目1Microsoft PowerToys: 最大化Windows系統生產…
閱讀更多...
軟件設計師備考筆記（十）：網絡與信息安全基礎知識

軟件設計師備考筆記（十）：網絡與信息安全基礎知識

文章目錄 一、網絡概述二、網絡互連硬件&#xff08;一&#xff09;網絡的設備&#xff08;二&#xff09;網絡的傳輸介質&#xff08;三&#xff09;組建網絡 三、網絡協議與標準&#xff08;一&#xff09;網絡的標準與協議&#xff08;二&#xff09;TCP/IP協議簇 四、Inter…
閱讀更多...
某神，云手機啟動？

某神，云手機啟動？

某神自從上線之后&#xff0c;熱度不減&#xff0c;以其豐富的內容和獨特的魅力吸引著眾多玩家&#xff1b; 但是隨著劇情無法跳過&#xff0c;長草期過長等原因&#xff0c;近年脫坑的玩家多之又多&#xff0c;之前米家推出了一款云某神的app&#xff0c;目標是為了減少用戶手…
閱讀更多...
RedisTemplateAPI:String

RedisTemplateAPI:String

文章目錄 ?1 String 介紹?2 命令?3 對應 RedisTemplate API???? 3.1 添加緩存???? 3.2 設置過期時間(單獨設置)???? 3.3 獲取緩存值???? 3.4 刪除key???? 3.5 順序遞增???? 3.6 順序遞減 ?4 以下是一些常用的API?5 應用場景 ?1 String 介紹 Str…
閱讀更多...
ue引擎游戲開發筆記（47）——設置狀態機解決跳躍問題

ue引擎游戲開發筆記（47）——設置狀態機解決跳躍問題

1.問題分析&#xff1a; 目前當角色起跳時&#xff0c;只是簡單的上下移動&#xff0c;空中仍然保持行走動作&#xff0c;并沒有設置跳躍動作&#xff0c;因此&#xff0c;給角色設置新的跳躍動作&#xff0c;并優化新的動作動畫。 2.操作實現&#xff1a; 1.實現跳躍不復雜&…
閱讀更多...
最新文章

Copyright @ 2022~2023