棧 · Programiz 中文系列教程

# 棧 > 原文： [https://www.programiz.com/dsa/stack](https://www.programiz.com/dsa/stack) #### 在本教程中，您將學習什么是棧。此外，您還將發現使用 C，C++ ，Java 和 Python 實現棧的實現。棧是編程中有用的數據結構。就像一堆板子彼此疊放。 ![a stack of plates is a good representation of stack data structure as you can only take out a plate from the top and put a plate on top of the other plates](https://img.kancloud.cn/53/79/537941bc4a0ed06c376e59d7d16f2344_456x380.png "Pile of plates act as a stack") 棧表示一堆板子想一想用這樣一堆板子可以做的事情 * 在上面放一個新板 * 卸下頂板如果要使板位于底部，則必須先卸下頂部的所有板。這種安排稱為**后進先出**-放置的最后一個項目是第一個要出去的項目。 * * * ## 編程術語中的棧用編程術語來說，將一個項目放在棧的頂部稱為“推入”，而將一個項目刪除則稱為“彈出”。 ![stack push pop fifo operations](https://img.kancloud.cn/e6/37/e6379fd72fc13c019b920dfbd6e4181f_814x482.png "Stack operations") 棧操作在上圖中，盡管項目 2 保留在最后，但它首先被移除-因此它遵循**后進先出（LIFO）**原則。我們可以用任何編程語言（例如 C，C++ ，Java，Python 或 C# ）實現棧，但是規范幾乎相同。 * * * ## 棧的規范棧是一個對象，或更具體地說，是一個允許執行以下操作的抽象數據結構（ADT）： * `Push`：將元素添加到棧頂部 * `Pop`：從棧頂部刪除元素 * `IsEmpty`：檢查棧是否為空 * `IsFull`：檢查棧是否已滿 * `Peek`：獲取頂部元素的值而不刪除它 * * * ## 棧如何工作操作如下： 1. 稱為`TOP`的指針用于跟蹤棧中的頂部元素。 2. 初始化棧時，我們將其值設置為 -1，以便我們可以通過比較`TOP == -1`來檢查棧是否為空。 3. 推入元素時，我們增加`TOP`的值，然后將新元素放置在`TOP`指向的位置。 4. 彈出元素時，我們返回`TOP`指向的元素并減小其值。 5. 推入之前，我們檢查棧是否已滿 6. 彈出之前，我們檢查棧是否已為空 ![stack operations](https://img.kancloud.cn/7a/83/7a83fa1cd6001136e0f2af2e5c3f64a7_1152x582.png) 棧操作 * * * ## Python，Java 和 C/C++ 示例最常見的棧實現是使用數組，但也可以使用列表來實現。 ```py # Stack implementation in python # Creating a stack def create_stack(): stack = [] return stack # Creating an empty stack def check_empty(stack): return len(stack) == 0 # Adding items into the stack def push(stack, item): stack.append(item) print("pushed item: " + item) # Removing an element from the stack def pop(stack): if (check_empty(stack)): return "stack is empty" return stack.pop() stack = create_stack() push(stack, str(1)) push(stack, str(2)) push(stack, str(3)) push(stack, str(4)) print("popped item: " + pop(stack)) print("stack after popping an element: " + str(stack)) ``` ```java // Stack implementation in Java class Stack { private int arr[]; private int top; private int capacity; // Creating a stack Stack(int size) { arr = new int[size]; capacity = size; top = -1; } // Add elements into stack public void push(int x) { if (isFull()) { System.out.println("OverFlow\nProgram Terminated\n"); System.exit(1); } System.out.println("Inserting " + x); arr[++top] = x; } // Remove element from stack public int pop() { if (isEmpty()) { System.out.println("STACK EMPTY"); System.exit(1); } return arr[top--]; } // Utility function to return the size of the stack public int size() { return top + 1; } // Check if the stack is empty public Boolean isEmpty() { return top == -1; } // Check if the stack is full public Boolean isFull() { return top == capacity - 1; } public void printStack() { for (int i = 0; i <= top; i++) { System.out.println(arr[i]); } } public static void main(String[] args) { Stack stack = new Stack(5); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.pop(); System.out.println("\nAfter popping out"); stack.printStack(); } } ``` ```c // Stack implementation in C #include <stdio.h> #include <stdlib.h> #define MAX 10 int count = 0; // Creating a stack struct stack { int items[MAX]; int top; }; typedef struct stack st; void createEmptyStack(st *s) { s->top = -1; } // Check if the stack is full int isfull(st *s) { if (s->top == MAX - 1) return 1; else return 0; } // Check if the stack is empty int isempty(st *s) { if (s->top == -1) return 1; else return 0; } // Add elements into stack void push(st *s, int newitem) { if (isfull(s)) { printf("STACK FULL"); } else { s->top++; s->items[s->top] = newitem; } count++; } // Remove element from stack void pop(st *s) { if (isempty(s)) { printf("\n STACK EMPTY \n"); } else { printf("Item popped= %d", s->items[s->top]); s->top--; } count--; printf("\n"); } // Print elements of stack void printStack(st *s) { printf("Stack: "); for (int i = 0; i < count; i++) { printf("%d ", s->items[i]); } printf("\n"); } // Driver code int main() { int ch; st *s = (st *)malloc(sizeof(st)); createEmptyStack(s); push(s, 1); push(s, 2); push(s, 3); push(s, 4); printStack(s); pop(s); printf("\nAfter popping out\n"); printStack(s); } ``` ```cpp // Stack implementation in C++ #include <stdlib.h> #include <iostream> using namespace std; #define MAX 10 int size = 0; // Creating a stack struct stack { int items[MAX]; int top; }; typedef struct stack st; void createEmptyStack(st *s) { s->top = -1; } // Check if the stack is full int isfull(st *s) { if (s->top == MAX - 1) return 1; else return 0; } // Check if the stack is empty int isempty(st *s) { if (s->top == -1) return 1; else return 0; } // Add elements into stack void push(st *s, int newitem) { if (isfull(s)) { printf("STACK FULL"); } else { s->top++; s->items[s->top] = newitem; } size++; } // Remove element from stack void pop(st *s) { if (isempty(s)) { printf("\n STACK EMPTY \n"); } else { printf("Item popped= %d", s->items[s->top]); s->top--; } size--; cout << endl; } // Print elements of stack void printStack(st *s) { printf("Stack: "); for (int i = 0; i < size; i++) { cout << s->items[i] << " "; } cout << endl; } // Driver code int main() { int ch; st *s = (st *)malloc(sizeof(st)); createEmptyStack(s); push(s, 1); push(s, 2); push(s, 3); push(s, 4); printStack(s); pop(s); cout << "\nAfter popping out\n"; printStack(s); } ``` * * * ## 棧復雜度對于基于數組的棧實現，推入和彈出操作需要固定時間，即`O(1)`，因為在兩種情況下都只有指針移動。 * * * ## 棧應用盡管棧是一個易于實現的簡單數據結構，但它非常強大。棧最常見的用途是： * **反轉單詞** - 將所有字母疊放并彈出。由于棧的 LIFO 順序，您將獲得相反順序的字母。 * **在編譯器中** - 編譯器使用棧通過將表達式轉換為前綴或后綴形式來計算`2 + 4 / 5 * (7 - 9)`之類的表達式的值。 * **在瀏覽器中** - 瀏覽器中的“后退”按鈕會將您以前訪問過的所有 URL 保存在棧中。每次您訪問新頁面時，它都會被添加到棧頂部。當您按下“后退”按鈕時，當前 URL 從棧中刪除，并訪問前一個 URL。