什么是栈

a数据结构入门 3月前 0 4

栈是一种数据结构，它遵循后进先出（Last In First Out, LIFO）的原则，也就是说，最后加入栈的元素会最先被移除。你可以将它想象成一个装满盘子的堆叠，你只能从顶部添加或移除盘子。

栈的基本操作:

栈的基本操作包括入栈，出栈，查看栈顶元素，判断栈是否为空等操作，其中入栈，出栈是用得最多的操作，我给大家举个例子，比如我们将1,2,3…等元素插入栈中如图所示:

此时我们想取出栈中的元素时,被取出的元素顺序如图所示:

这就是栈的最基本特点，它是一种先进后出，后进先出的数据结构,那小伙伴们大概了解了栈的基本操作之后，我们该如何实现它呢?欲知后事如何,请听下面讲解。

栈的实现方式:

1.用数组实现栈:
我们用数组实现栈时只需先初始化一个数组的大小，然后再定义一个top指针，指向栈底，一般定义为-1。如图所示:

初次学习栈的时候要注意入栈的时候我们要先判断栈的空间是否满了，如果满了，则插入不了，代码如下所示:

public void push(int x){
    if(top==maxSize-1){//maxSize为数组最大容量
       System.out.println("插入失败");
      }else{
      arr[++top]=x;//arr[]表示数组;
      }
}

有了入栈就有出栈，出栈的时候我们要先判断栈是否为空，栈如果空了，则出栈失败,代码如下:

public void pop(){
    if(isEmpty()){
       System.out.println("弹出失败");
    }else{
      top--;
    }
}

然后我对栈的入栈，出栈，初始化做一个完整的代码呈现如图所示:

public class StackArray {
    private int[] stack;
    private int top;
    private int capacity;

    // 构造函数，初始化栈的大小
    public StackArray(int size) {
        this.capacity = size;
        this.stack = new int[capacity];
        this.top = -1;
    }

    // 入栈操作
    public void push(int value) {
        if (top == capacity - 1) {
            System.out.println("Stack Overflow");
            return;
        }
        stack[++top] = value;
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return -1; // 通常返回一个错误码或抛出异常
        }
        return stack[top--];
    }

    // 查看栈顶元素
    public int peek() {
        if (!isEmpty()) {
            return stack[top];
        }
        System.out.println("Stack is empty");
        return -1; // 通常返回一个错误码或抛出异常
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 检查栈是否已满
    public boolean isFull() {
        return top == capacity - 1;
    }

    // 打印栈中的元素
    public void printStack() {
        if (!isEmpty()) {
            for (int i = top; i >= 0; i--) {
                System.out.print(stack[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("Stack is empty");
        }
    }

    // 主函数，用于演示栈的操作
    public static void main(String[] args) {
        StackArray stack = new StackArray(5);
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.printStack(); // 打印栈内容

        System.out.println("Peek: " + stack.peek()); // 查看栈顶元素

        stack.pop();
        stack.printStack(); // 打印栈内容

        System.out.println("Is Stack Empty? " + stack.isEmpty()); // 检查栈是否为空
    }
}

2.调用Java中的封装类:
除了用数组模拟实现栈，在Java语言中还可以直接调用Stack类中的方法。常用的方法有push()：压入元素,,pop()：弹出栈顶元素，并返回栈顶元素,,peek()：返回栈顶元素,,size()：返回长度,,empty()：栈是否为空,,clear()：清空。我带大家写一个简单的入栈，出栈应用，代码如图所示:

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 向栈中压入元素
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 打印栈顶元素
        System.out.println("Top element is: " + stack.peek());

        // 弹出栈顶元素
        while (!stack.empty()) {
            System.out.println(stack.pop());
        }

        // 测试栈是否为空
        System.out.println("Is the stack empty? " + stack.empty());
    }
}

栈的应用场景:

在实际的工作应用中函数调用和递归的实现通常使用栈来管理函数调用的顺序和局部变量的存储。每次函数调用会将函数的参数和局部变量存储在栈帧中，函数返回时栈帧会被弹出，恢复到调用前的状态。另外在进行撤销操作时也用到了栈，在许多应用程序中，如文本编辑器、图形设计软件等，撤销操作可以使用栈来存储每个操作的状态。撤销时，最新的操作被弹出栈，恢复到之前的状态。

今日小结:

今天我给大家入门讲解了栈这种数据结构，介绍了它的基本操作如入栈，出栈，还有如何实现栈，一种是用数组模拟,另一种是直接调用Java语言中的封装类中的方法。其中入栈，出栈的时间复杂度一般都为o(1),它只需在一端执行入栈，出栈操作，而不需遍历整个数组。最后给大家分享了栈的实际应用场景，如果操作符合先进后出，就可以用栈这种数据结构。

栈的基本操作:

栈的实现方式:

栈的应用场景:

今日小结:

发表回复 取消回复

发表回复取消回复