golang,go,博客,开源,编程

栈

Published on with 0 views and 0 comments

栈（Stack） 是一种特殊的线性数据结构，它遵循“后进先出”（LIFO, Last In First Out）原则，即最后插入的元素最先被删除。栈的操作仅限于一端（栈顶），所有的插入（入栈）和删除（出栈）操作都在栈顶进行。

1. 栈的基本操作

栈支持以下几种常见操作：

  1. 入栈（Push）：
    • 将一个元素添加到栈顶。
    • 例如：Push(x) 将元素 x 插入到栈顶。
  2. 出栈（Pop）：
    • 从栈顶移除一个元素，并返回该元素。
    • 例如：Pop() 移除并返回栈顶元素。
  3. 查看栈顶元素（Peek 或 Top）：
    • 返回栈顶的元素，但不删除它。
    • 例如：Peek() 或 Top() 返回栈顶元素，但不出栈。
  4. 栈是否为空（isEmpty）：
    • 检查栈是否为空。
    • 例如：isEmpty() 如果栈为空返回 true，否则返回 false。
  5. 栈的大小（Size）：
    • 返回栈中元素的个数。
    • 例如：Size() 返回栈的元素个数。

2. 栈的应用

栈是计算机科学中非常重要的数据结构，它广泛应用于以下几种场景：

  • 表达式求值：
    • 中缀表达式转后缀（逆波兰表示法）和计算后缀表达式时使用栈。
  • 函数调用：
    • 栈用于存储函数调用的执行信息，例如局部变量、返回地址等。现代程序的调用栈（Call Stack）就是一个栈结构。
  • 撤销操作：
    • 在文本编辑器或图形软件中，栈用于保存操作历史，支持撤销和重做操作。
  • 平衡符号检测：
    • 在编译器中，栈可以用来检查括号、花括号等符号的匹配，确保代码的正确性。

3. 栈的实现

栈可以通过数组或链表实现。

栈的顺序存储（基于数组）

在数组实现中，栈是一个固定大小的数组，栈顶指针指向当前栈顶的位置。

#include <iostream>
using namespace std;

#define MAX 100 // 栈的最大容量

class Stack {
private:
    int arr[MAX];  // 用数组来存储栈元素
    int top;       // 栈顶指针

public:
    Stack() { top = -1; }

    // 判断栈是否为空
    bool isEmpty() {
        return top == -1;
    }

    // 判断栈是否已满
    bool isFull() {
        return top == MAX - 1;
    }

    // 入栈操作
    void push(int x) {
        if (isFull()) {
            cout << "Stack Overflow!" << endl;
            return;
        }
        arr[++top] = x;
    }

    // 出栈操作
    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        return arr[top--];
    }

    // 获取栈顶元素
    int peek() {
        if (isEmpty()) {
            cout << "Stack is Empty!" << endl;
            return -1;
        }
        return arr[top];
    }

    // 获取栈的大小
    int size() {
        return top + 1;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Top element is: " << s.peek() << endl;  // 输出栈顶元素 30
    cout << "Stack size: " << s.size() << endl;      // 输出栈的大小 3

    cout << "Popped element: " << s.pop() << endl;   // 弹出栈顶元素 30
    cout << "Top element is: " << s.peek() << endl;  // 输出栈顶元素 20

    return 0;
}

栈的链式存储（基于链表）

链表实现的栈不需要预先分配固定大小的内存空间，且支持动态扩展。每个节点包含数据和指向下一个节点的指针。

#include <iostream>
using namespace std;

// 链表节点定义
struct Node {
    int data;
    Node* next;
};

class Stack {
private:
    Node* top;

public:
    Stack() { top = nullptr; }

    // 判断栈是否为空
    bool isEmpty() {
        return top == nullptr;
    }

    // 入栈操作
    void push(int x) {
        Node* newNode = new Node();
        newNode->data = x;
        newNode->next = top;
        top = newNode;
    }

    // 出栈操作
    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        Node* temp = top;
        int poppedValue = temp->data;
        top = top->next;
        delete temp;
        return poppedValue;
    }

    // 获取栈顶元素
    int peek() {
        if (isEmpty()) {
            cout << "Stack is Empty!" << endl;
            return -1;
        }
        return top->data;
    }

    // 获取栈的大小
    int size() {
        int count = 0;
        Node* temp = top;
        while (temp != nullptr) {
            count++;
            temp = temp->next;
        }
        return count;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Top element is: " << s.peek() << endl;  // 输出栈顶元素 30
    cout << "Stack size: " << s.size() << endl;      // 输出栈的大小 3

    cout << "Popped element: " << s.pop() << endl;   // 弹出栈顶元素 30
    cout << "Top element is: " << s.peek() << endl;  // 输出栈顶元素 20

    return 0;
}

4. 栈的时间复杂度

操作时间复杂度
入栈（Push）O(1)
出栈（Pop）O(1)
栈顶元素（Peek）O(1)
栈的大小（Size）O(n)
判空（isEmpty）O(1)

5. 栈的优缺点

优点：

  • 操作简单：栈的操作非常简单，只需要对栈顶进行操作，插入和删除时间复杂度都为 O(1)。
  • 空间效率高：对于链式栈，空间是动态分配的，不需要预留过多的空间。
  • 应用广泛：栈是很多重要算法的基础，例如递归调用、深度优先搜索等。

缺点：

  • 只能访问栈顶元素：栈的访问仅限于栈顶元素，无法直接访问栈中间的元素。
  • 固定大小栈（顺序栈）存在溢出风险：如果栈的大小固定（如顺序栈），在栈空间满时会发生栈溢出（Stack Overflow）。

6. 总结

栈是一种非常基础且重要的数据结构，广泛应用于计算机科学中的多种场景，如表达式求值、回溯算法、函数调用、撤销操作等。它可以通过数组或链表来实现，每种实现方式都有其优缺点。在实际使用中，可以根据具体需求选择合适的栈实现方式。

标题：栈
作者：mooncakeee
地址：http://blog.dd95828.com/articles/2025/01/10/1736471162834.html
联系：scotttu@163.com
↑ ↓