【数据结构】关于栈你必须知道的内部原理！！！

用户11288949

发布于 2024-09-24 13:42:35

550

发布于 2024-09-24 13:42:35

文章被收录于专栏：用户11288949的专栏

📚️1.栈的概念

🎥1.1什么是栈？？

栈一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

🎥1.2什么入栈？？

栈的插入操作叫入栈（入数据在栈顶）

🎥1.3什么出栈？？

栈的删除操作叫出栈（出数据在栈顶）

图片如下：

总之一句话，放数据和出数据都在一个口，就像喝水一样，加水和喝水都在水面。 当然你插吸管当小编没说~~~😄😄😄

ok啊，了解了栈的基本原理，咱们就代码模拟一下吧~~~

冲冲冲~~~💪💪💪

📚️ 2.栈的模拟实现

🎥引导

不难看出，上图所示栈是否像一个数组，0下标为栈的栈底索引，而且数据个数减去1，就是栈顶元素的下标索引，那么我们就有以下操作。

🎥2.1栈的初始化

代码如下：

public class MyStack {
    private int []elem;
    private int usedSize=0;
    public MyStack(int Range){
        this.elem=new int[Range];
    }

在代码中我们实现数组，和设定一个代表数据个数的变量，这里在构造函数中实现数组初始化的优点是，可以在实例化对象时，自动初始话我们想要的数组以及大小。

🎥2.2判断栈是否为空

代码如下：

   public boolean isFull(){     //判断栈是否为满
        if (usedSize== elem.length){
            return true;
        }
        return false;
    }
    //判断是否为空
    public boolean isEmpty(){
        if (usedSize==0){
            return true;
        }
        return false;
    }

在几乎所有的数组实现和链表实现中，都要进行越界处理，在此代码中当数据个数等于数组的长度时就表示栈满了，当数据个数为0时，就表示栈为空。（这里的usedSize很关键）。

🎥2.3入栈操作

代码如下：

 public int push(int e){
        if(isFull()){      //在加入数据时，判断栈是否为空
            ensureCapacity();
        }
        elem[usedSize]=e;  //加入数据
        usedSize++;        //有效数据个数加一
        return e;
    }

这里小编多加了一个方法，表示扩容，然后加入数据，当然有效数据也得加一。

💡💡💡注意：扩容的前提是，栈满了；几乎所有的数据结构都要判断，像链表要判断节点是否存在空指针异常，数组判断索引是否越界.......

🎥2.4出栈操作

代码如下：

public int pop(){
        if(isEmpty()){
            System.out.println("栈为空，不能出栈");
            return -1;
        }
        int ret=elem[usedSize-1];
        usedSize--;
        return ret;
    }

和上述代码一样，首先判断栈是否为空，空了就不能出栈，否则就出栈顶元素，有效数据减去一。

🎥2.5输出栈顶元素

代码如下：

 public int peek(){
        if(isEmpty()){
            System.out.println("栈为空，没有栈顶元素");
            return -1;
        }
        return elem[usedSize-1];
    }

同样判断栈是否为空，然后返回栈顶元素，但是有效数据不变。

🎥2.6长度，扩容，打印

~~~这几种方法小编就一笔带过咯

代码如下：

    //求长度
    public int size(){
        return usedSize;
    }

    //扩容
    private void ensureCapacity(){
        this.elem=Arrays.copyOf(this.elem,2*elem.length);
    }
    //打印
    public void display(){
        int index=0;
        while (index<usedSize){
            System.out.print(elem[index]+" ");
            index++;
        }
    }

长度就是有效数据；扩容中要运用 Arrays.copyOf 来实现扩容，创建一个与原数组类型相同的新数组；在打印中，首先要遍历栈，然后通过索引进行打印。

📚️3.栈的使用

和前几期，链表，顺序表等都有类似的方法，但是栈的方法不多~~~

下面比起前面内容稍微较易，那就通过小编代码看看吧！！😁😁😁

Stack<Integer> stack=new Stack<>(); //构造一个空栈
        stack.push(1);  //入栈
        stack.push(2);
        stack.push(3);
        System.out.println(stack);
        stack.pop();     //出栈顶元素
        stack.peek();    //输出栈顶元素，但不出栈
        System.out.println(stack);
        System.out.println(stack.size());  //输出有效数据个数
        System.out.println(stack.empty()); //判断栈是否为空

这里小编注加了解释，小编就不再过多赘述了。

输出情况：