Java Collection(2)——Stack(栈)&Queue(队列)&Deque(双端队列)

用户11873138

发布于 2026-01-13 21:22:49

1070

前言

Stack(栈)&Queue(队列)在集合类中的位置关系图

由图可知，Stack和Queue是通过顺序表/线性表实现的，只要上节搞明白了，这一节就很简单

一.栈(Stack)

1.栈的定义

栈是一种先进后出(Last-in,First-Out)的数据结构实际上现在已经不推荐使用Stack，标准库中已经实现了ArrayDeque（下面会说到）作为Stack的替代品标准库中的Stack继承于Vector(ArrayList的线程安全版本)，这在某些情况下会影响效率，本文后面再详细说

2.栈的方法

3.模拟实现栈

这里的模拟实现与ArrayList的模拟实现有相通之处，push相当于尾插，pop相当于尾删，peek是获取栈尾元素

public class MyStack {
    private int[] elem;
    private int usedSize;
    private static final int DEFAULT_CAPACITY = 10;

     public MyStack(){
         this.elem = new int[DEFAULT_CAPACITY];
     }

     public void push(int data){
         if (isFull()){
             elem = Arrays.copyOf(elem,elem.length*2);
         }
         elem[usedSize] = data;
         usedSize++;
     }

     public Boolean isFull(){
         return usedSize == elem.length;
     }

     public int pop(){
         if (isEmpty()){
             throw new Exception("空指针异常");
         }
         int oldData = elem[usedSize-1];
         usedSize--;
         return oldData;
     }

     public int peek(){
         if (isEmpty()){
             throw new Exception("空指针异常");
         }
         return elem[usedSize-1];
     }

     public Boolean isEmpty(){
         return usedSize == 0;
     }
}

二.队列(Queue)

1.队列的定义

队列是一种先进先出(First-in,First-Out)的数据结构

2.队列的方法

queue中对于删除，添加，获取元素都有两套方法 1.尾插法：add()&&offer()

2.删除队首元素：remove()&&poll()

3.获取队首元素但不删除：element()&&peek()

3.模拟实现队列

这里模拟实现队列使用的时双向链表，所以我首先介绍一下双向链表的结构双向链表一共三个域，value（值），prev（上个结点的地址），next（下个结点的地址），实际上和单向链表是一个逻辑，只不过多了一个保存上个节点地址的域

public class Queue {
    // 双向链表节点
    public static class ListNode {
        ListNode next;
        ListNode prev;
        int value;

        ListNode(int value) {
            this.value = value;
        }
    }

    ListNode first; // 队头
    ListNode last; // 队尾
    int size = 0;

    //入队列---向双向链表位置插入新节点,尾插法
    public void offer(int e) {
        ListNode newNode = new ListNode(e);
        if (first == null) {
            first = newNode;
        // last = newNode;
        } else {
            last.next = newNode;
            newNode.prev = last;
        // last = newNode;
        }
        last = newNode;
        size++;
    }
    //删除第一个元素
    public int poll(){
        int val = 0;
        if(first == null){
            System.out.println("链表为空");
            return -1;
        }else if (first == last){
            val = first.value;
            first = null;
            last = null;
            size--;
        }else{
            val = first.value;
            first = first.next;
            first.prev.next = null;
            first.prev = null;
            size--;
        }
        return val;
    }
    //获取队头元素---获取链表中第一个节点的值域
    public int peek(){
        if(first == null) {
            System.out.print("链表为空");
            return -1;
        }
        return first.value;
    }
    //size
    public int size(){
        return size;
    }
    //empty
    public Boolean isEmpty(){
        return first == null;
    }
    //display
    public void display(){
        if(first == null) {
            System.out.println("链表为空");
            return;
        }
        ListNode cur = first;
        while (cur != null){
            System.out.print(cur.value+" ");
            cur = cur.next;
        }
        System.out.println();
    }
}

三.双端队列Deque

Deque是什么？

Deque是一种双端队列，可以在两端进行插入和删除。既可以当栈使用，也可以当队列使用。它的实现类有 LinkedList(双向链表)/ArrayDeque(本质上是数组) 模拟实现双端队列就不展示了，上面的双向链表做出微调就可以模拟出双端队列

ArrayDeque代替Stack

Stack能完成的工作，ArrayDeque也能完成，那么相较于Stack，ArrayDeque的优势在哪呢？ 1.无同步开销 Stack继承于Vector，Vector是ArrayList的线程安全版本，那么它是如何保证线程安全的呢？看过我的线程安全相关的博文应该知道，多个线程对同一个数据进行"写"操作，就有可能引发线程安全问题，解决办法是添加synchronized，但这会影响性能 Vector就是对方法添加了synchronized以此来保证线程安全，但这也导致它在单线程情况下会有不必要i的开销，Stack同理 2.更好的处理异常 ArrayDeque的offer方法在队列满时返回false，而不是抛出异常 ArrayDeque的poll和peek方法在队列为空时返回null，而不是抛出NoSuchElementException

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-10-20，如有侵权请联系 cloudcommunity@tencent.com 删除

queue