栈 Stack Last In First Out LIFO

栈（Stack）是一种遵循后进先出（Last In First Out，LIFO）原则的线性数据结构。在栈中，元素的添加和删除都发生在同一个位置，称为栈顶（Top）。相对地，栈的另一端称为栈底（Bottom）。栈的操作通常包括以下几个基本功能：

栈的基本操作：

Push：向栈顶添加一个元素。
Pop：移除栈顶的元素，并返回它。
Peek/Top：查看栈顶的元素，但不移除它。
IsEmpty：检查栈是否为空。
Size：获取栈中元素的数量。

栈的实现方式：

栈可以用数组或链表来实现。以下是两种实现方式的简要说明：

数组实现：

使用数组实现栈时，通常会维护一个变量来记录栈顶的位置。当添加元素时，只需将元素放在数组的末尾，并更新栈顶位置；当删除元素时，从数组末尾移除元素，并更新栈顶位置。

#include <iostream>
#include <vector>

class Stack {
private:
    std::vector<int> elements;
    int top; // 栈顶索引

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

    void push(int element) {
        elements.push_back(element);
        top++;
    }

    int pop() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        int element = elements[top];
        elements.pop_back();
        top--;
        return element;
    }

    int peek() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        return elements[top];
    }

    bool isEmpty() {
        return top == -1;
    }

    size_t size() {
        return top + 1;
    }
};

链表实现：

使用链表实现栈时，每个节点包含数据和指向下一个节点的指针。链表的头节点对应栈顶。添加和删除元素都发生在链表的头部。

#include <iostream>
#include <memory>

class Node {
public:
    int data;
    std::unique_ptr<Node> next;

    Node(int data) : data(data), next(nullptr) {}
};

class Stack {
private:
    std::unique_ptr<Node> head; // 栈顶节点

public:
    Stack() : head(nullptr) {}

    void push(int element) {
        auto newNode = std::make_unique<Node>(element);
        newNode->next = std::move(head);
        head = std::move(newNode);
    }

    int pop() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        int element = head->data;
        auto oldHead = std::move(head);
        head = std::move(head->next);
        return element;
    }

    int peek() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        return head->data;
    }

    bool isEmpty() {
        return head == nullptr;
    }

    size_t size() {
        size_t count = 0;
        auto current = head.get();
        while (current != nullptr) {
            count++;
            current = current->next.get();
        }
        return count;
    }
};

栈的应用场景：

函数调用：大多数编程语言使用栈来管理函数调用，包括参数传递和局部变量存储。
表达式求值：用于计算和简化表达式，如算术表达式求值和语法分析。
回溯算法：如迷宫求解、八皇后问题等，需要回溯时使用栈。
撤销操作：在编辑器和图形界面应用程序中，用于实现撤销（Undo）操作。
括号匹配：检查代码或文本中的括号是否正确匹配。

栈是一种基础的数据结构，由于其简单的操作特性，在许多领域和算法中都有广泛应用。

(责任编辑：admin)

热门: