[Data structure]栈-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Data structure]栈。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

⭐作者介绍：大二本科网络工程专业在读，持续学习Java，努力输出优质文章
⭐作者主页：@逐梦苍穹
⭐所属专栏：数据结构。数据结构专栏主要是在讲解原理的基础上拿Java实现，有时候有C/C++代码。
⭐如果觉得文章写的不错，欢迎点个关注一键三连😉有写的不好的地方也欢迎指正，一同进步😁

1、简介

栈（Stack）是一种常见的数据结构，它遵循"先进后出"（Last-In-First-Out，LIFO）的原则。栈的操作主要包括入栈（Push）和出栈（Pop）两种基本操作，其中入栈将元素放入栈的顶部，而出栈则从栈的顶部移除元素。
栈可以想象成一叠盘子，每当放入一个新的盘子时，它就被放在上面，而当需要取出盘子时，也是从上面开始取。因此，最后放入的盘子会最先被取出。

2、栈的特点

LIFO原则：栈遵循"后进先出"的原则，最后放入的元素会首先被访问和移除。
限定访问位置：栈只允许在栈顶进行插入和删除操作，无法直接访问或修改栈底的元素。
时间复杂度：入栈和出栈操作的时间复杂度为O(1)，即常数时间。

栈的实现可以基于数组或链表。使用数组实现的栈称为顺序栈（Sequential Stack），使用链表实现的栈称为链式栈（Linked Stack）。

以下是栈的基本操作：

Push（入栈）：将元素添加到栈的顶部。如果栈已满，可能会发生栈上溢（Stack Overflow）的错误。
Pop（出栈）：从栈的顶部移除一个元素，并返回该元素的值。如果栈为空，可能会发生栈下溢（Stack Underflow）的错误。
Top/Peek（查看栈顶元素）：返回栈顶元素的值，但不移除它。
isEmpty（判断栈是否为空）：检查栈是否为空，如果为空则返回True，否则返回False。
isFull（判断栈是否为满）：检查栈是否为满，如果为满则返回True，否则返回False。

3、应用场景

栈在计算机科学和软件工程中有广泛的应用，例如：

函数调用栈：用于跟踪函数的调用顺序和局部变量的存储。
表达式求值：使用栈来处理中缀表达式转换为后缀表达式，并计算表达式的值。
撤销操作：在文本编辑器、图形操作等应用中，使用栈来存储操作历史，以便撤销先前的操作。
浏览器历史记录：浏览器使用栈来存储访问过的网页，使得用户可以通过后退按钮按照访问的顺序导航。
深度优先搜索（DFS）：在图算法中，栈用于实现深度优先搜索算法的追踪回溯。

栈是一种简单而强大的数据结构，可以通过合理应用栈来解决各种问题，同时也为其他复杂的数据结构和算法提供了基础支持。

4、代码实现

4.1、思路分析

Push（压栈）：将元素添加到栈的顶部。top++;
Pop（弹栈）：从栈的顶部移除一个元素，并返回该元素的值。top–;
top（栈顶指针）：初始值为-1。
isEmpty（判断栈是否为空）：检查栈是否为空，如果为空则返回True，否则返回False。
isFull（判断栈是否为满）：检查栈是否为满，如果为满则返回True，否则返回False。

4.2、Stack

Java

[Data structure]栈文章来源地址https://www.toymoban.com/news/detail-459745.html

package stack;

/**
 * @author 逐梦苍穹
 * @date 2023/5/25 20:34
 */
public class Stack<T> {
    private final int maxSize;
    private final Object[] stack;
    private int top = -1;

    public Stack(int maxSize) {
        this.maxSize = maxSize;
        this.stack = new Object[this.maxSize];
    }

    /**
     * 栈满
     */
    public boolean isFull(){
        return (top == maxSize - 1);
    }

    /**
     * 栈空
     */
    public boolean isEmpty(){
        return (top == -1);
    }

    /**
     * 压栈
     */
    public void push(T value){
        if (isFull()){
            System.out.println("栈满");
        }
        top++;
        stack[top] = value;
    }

    /**
     * 弹栈
     */
    public Object pop(){
        if (isEmpty()){
            System.out.println("栈空");
        }
        Object value = stack[top];
        stack[top] = null;
        top--;
        return value;
    }

    /**
     * 显示栈的内容
     */
    public void showStack(){
        //从栈顶遍历，但是不是弹栈
        if(!isEmpty()) {
            for(int i = top; i >= 0 ; i--) {
                System.out.printf("stack[%d]=%d\n", i, stack[i]);
            }
        }else {
            System.out.println("栈空");
        }
    }
}

C++

#include <vector>
#include <stdexcept>

template <typename T>
class Stack {
private:
    std::vector<T> stack; // 用vector作为底层存储结构

public:
    // 构造函数
    Stack() : stack(std::vector<T>()) {
    }

    // 入栈操作
    void push(T item) {
        stack.push_back(item);
    }

    // 出栈操作
    T pop() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        T item = stack.back();
        stack.pop_back();
        return item;
    }

    // 查看栈顶元素
    T peek() {
        if (isEmpty()) {
            throw std::out_of_range("Stack is empty");
        }
        return stack.back();
    }

    // 判断栈是否为空
    bool isEmpty() {
        return stack.empty();
    }

    // 获取栈的大小
    int size() {
        return stack.size();
    }
};