【Java数据结构】详解Stack与Queue（一）

E绵绵

发布于 2024-06-04 08:25:54

1570

1.❤️❤️前言~🥳🎉🎉🎉

Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪

2.栈(Stack) 的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

在集合框架中，Stack（栈）是一个普通的类，具体框架图如下：

3.栈的模拟实现

我们能用顺序存储或链式存储来实现栈。 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素（也就是用数组去实现） 采用链式存储的栈称为链式栈，通常采用双向链表实现（之所以用双向链表我们后面将会说）
栈的方法如下，接下来我们要模拟顺序栈和链式栈的实现

3.1顺序栈的模拟实现

由于顺序栈是由顺序存储实现的，所以其底层是一个动态数组 。以下是其模拟实现的代码。

public class ArrayStack {
    public int[] elem; //底层是动态数组
    public int usedSize;//有效数据
    public ArrayStack(){
        this.elem = new int[5];
        this.usedSize = 0;
    }
    //入栈
    public void push(int val){
        //如果栈满了就进行扩容，符合动态数组
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*this.elem.length);
        }
        this.elem[this.usedSize] = val;
        usedSize++;
    }
    //判断栈是否满
    public boolean isFull(){
        return usedSize==this.elem.length;
    }

    //出栈
    public int pop(){
        if(isEmpty()){
            throw new NullPointerException("该栈为空！");
        }
        int value = this.elem[usedSize-1];
        this.usedSize--;
        return value;
    }
    //判断栈是否为空
    public boolean isEmpty(){
        return this.usedSize==0;
    }

    //读取栈顶元素
    public int peek(){
        if(isEmpty()){
            throw new NullPointerException("该栈为空！");
        }
        return this.elem[usedSize-1];
    }

    //获取该栈元素数量
    public int size(){
        return usedSize;
    }
}

这样我们就实现了一个去存放整形数据的顺序栈。下图是对于该顺序栈的使用代码：

public class Test {
    public static void main(String[] args) {
        ArrayStack myStack=new ArrayStack();
        myStack.push(4);//入栈
        myStack.push(3);
        myStack.push(2);
        myStack.push(1);
        System.out.println(myStack.size());//获取该栈元素数量
        System.out.println(myStack.peek());//获取栈顶元素
        System.out.println(myStack.pop());//出栈
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.isEmpty());//判断栈是否为空，如果为空返回true，否则返回false
    }
}

3.2 链式栈的模拟实现

底层是链表需要满足的条件： 先进后出 入栈和出栈的时间复杂度为O(1) 链表可以头插也可以尾插，那么入栈是使用头插法还是使用尾插法呢？ 假设我们是用单链表为底层：如果入栈使用尾插法，那么时间复杂度是O(n)，因为尾插法每次都要找最后一个结点。假设：如果入栈使用头插法，那么时间复杂度是O(1)；出栈的时候只需要删除头结点，时间复杂度也是O(1) 经过推导得出，用单链表使用头插法实现栈能满足条件，但是如果非要使用尾插法呢？假设给一个last引用指向尾巴结点，此时入栈的时间复杂度为O(1)。但是出栈的时间复杂度还是O(n)。因为，虽然知道了最后一个结点，但是去掉尾巴结点后还要知道它的前一个结点，那么就要遍历单链表去找尾巴结点的前驱结点。此时时间复杂度又是O(n)。 最终的解决办法就是用双向链表使用尾插法来实现一个栈。（双向链表可以知道一个结点的前驱结点与后继结点）。 自然双向链表也就能用头插法去实现一个栈。
所以我们可以用单链表使用头插法去实现栈，也可以用双链表使用头插法或尾插法去实现栈

这里我们用双向链表使用尾插法去实现一个链式栈：

public class LinkedStack<E> {
    LinkedList<E> linkedList=new LinkedList<>();
    public  LinkedStack() {

    }
    public void push(E value){
        linkedList.add(value);
    }
    public  E  pop(){
      return   linkedList.remove(linkedList.size()-1);
    }
    public  E peek(){
     return    linkedList.get(linkedList.size()-1);
    }
    public  Boolean isEmpty(){
        if(linkedList.size()==0)
            return  true;
        else
            return  false;
    }
    public  int  size(){
        return  linkedList.size();
    }
}

这样我们就用双链表使用尾插法实现了一个栈，下图是该栈的使用代码：

public class Main {
    public static void main(String[] args) {
        LinkedStack<Integer> linkedStack = new LinkedStack<>();
        linkedStack.push(4);
        linkedStack.push(3);
        linkedStack.push(2);
        linkedStack.push(1);
        System.out.println(linkedStack.peek());//获取栈顶元素
        System.out.println(linkedStack.pop());//出栈
        System.out.println(linkedStack.pop());
        System.out.println(linkedStack.pop());
        System.out.println(linkedStack.pop());
        System.out.println(linkedStack.isEmpty());//判断栈是否为空，如果为空返回true，否则返回false
        System.out.println(linkedStack.size());//求栈中该元素的数量
    }}

3.3顺序栈和链式栈的区别

对比一下顺序栈与链式栈,它们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制,不会存在内存空间浪费的情况。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。

4.Stack类的使用

在集合框架中我们的Stack类其实就是一个顺序栈，其底层是动态数组。以下是Stack类的使用。

public class Test {
    public static void main(String[] args) {
        Stack<Integer> myStack=new Stack<>();
        myStack.push(1);//入栈
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.peek());//获取栈顶元素
        System.out.println(myStack.pop());//出栈
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.isEmpty());//判断栈是否为空，如果为空返回true，否则返回false
        System.out.println(myStack.size());
    }
}