栈和队列（Java实现）

2024-04-18 19:05:55

栈和队列（Java实现）

栈

栈(Stack)：栈是先进后出（FILO, First In Last Out）的数据结构。Java中实现栈有以下两种方式：

stack类
LinkedList实现（继承了Deque接口）

（1） Stack实现

由于Stack底层是使用Vector的，而Vector支持线程同步，所以整体性能相对较低，如果没有多线程的场景，不建议使用Stack。

stack类图为：

举例：

//栈的实现一，内置类
//底层实现： Vector class Stack<E> extends Vector<E>
//由于Vector支持线程同步，所以效率比较低
Stack<Integer> stack = new Stack<>();
stack.push(1);  //插入元素
stack.pop();    //弹出栈顶元素
stack.peek();      //查看栈顶元素
int n = stack.size();   //栈的大小
System.out.println(stack.isEmpty());    //判断栈是否为空

（2）LinkedList实现

LinkedList实现了List，Deque（实现了Queue接口）的接口，底层是双向链表实现的，所以不仅可以表示栈，也可以表示队列。

举例：

//栈的实现二：LinkedList
/*LinkedList底层实现了Deque双端队列的接口，双端队列，完全可以实现栈的功能
            public class LinkedList<E>
            extends AbstractSequentialList<E>
            implements List<E>, Deque<E>,
 */
Deque<Integer> stack2 = new LinkedList<>();
stack2.push(1);     //插入元素
stack2.push(2);     //插入元素
      //        stack2.offer(3);    //offer和push都可以插入元素,但是push是队尾插入，offer是队首
System.out.println(stack2);
int m = stack2.peek();          //取栈顶元素,peek是2
System.out.println(m);          //结果为2
m = stack2.getFirst();          //取栈顶第一个元素
System.out.println(m);          //结果为2
stack2.pop();         		    //删除栈顶元素

队列

（1）使用LinkedList实现队列

底层是链表

public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        // 添加元素到队列尾部
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // 获取队列头部元素并删除
        int head = queue.poll();
        System.out.println("Head of the queue: " + head);

        // 获取队列头部元素但不删除
        int peek = queue.peek();
        System.out.println("Peek of the queue: " + peek);

        // 遍历队列中的元素
        System.out.println("Elements in the queue: ");
        for (Integer element : queue) {
            System.out.println(element);
        }
    }
}

（2）使用ArrayDeque实现队列

底层是数组实现

    public static void main(String[] args) {
        //使用ArrayQueue实现队列
        Queue<Integer> queue = new ArrayDeque<>();

        // 添加元素到队列尾部
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);

        // 获取队列头部元素并删除
        int head = queue.poll();
        System.out.println("Head of the queue: " + head);

        // 获取队列头部元素但不删除
        int peek = queue.peek();
        System.out.println("Peek of the queue: " + peek);

        // 遍历队列中的元素
        System.out.println("Elements in the queue: ");
        for (Integer element : queue) {
            System.out.println(element);
        }
    }

（3）双端队列

Deque（双端队列）是一种具有队列和栈的特性的数据结构，它允许在队列的头部和尾部进行元素的插入和删除操作。在Java中，Deque接口提供了对双端队列的定义，它是Queue接口的一个子接口。

使用Deque可以进行以下操作：

在队列头部插入元素：可以使用addFirst()或者offerFirst()方法在队列的头部插入一个元素。
在队列尾部插入元素：可以使用addLast()或者offerLast()方法在队列的尾部插入一个元素。
从队列头部删除元素：可以使用removeFirst()或者pollFirst()方法从队列的头部删除一个元素。
从队列尾部删除元素：可以使用removeLast()或者pollLast()方法从队列的尾部删除一个元素。
获取队列头部的元素：可以使用getFirst()或者peekFirst()方法获取队列头部的元素，但不会将其从队列中删除。
获取队列尾部的元素：可以使用getLast()或者peekLast()方法获取队列尾部的元素，但不会将其从队列中删除。
判断队列是否为空：可以使用isEmpty()方法判断队列是否为空。
获取队列的大小：可以使用size()方法获取队列中元素的个数。
offer()方法：用于在队列尾部插入元素，如果插入成功则返回true，否则返回false。它类似于add()方法，但不同之处在于当队列已满时，add()方法会抛出异常，而offer()方法会返回false。
push()方法：用于在队列头部插入元素，即将元素压入栈顶。它等效于addFirst()方法。与offer()方法类似，如果插入成功则返回true，否则抛出异常。

Deque接口有多个实现类可供使用，Java提供了两个常用的实现类：

LinkedList：基于链表实现的双端队列，支持快速插入和删除操作，但在随机访问和迭代性能上相对较慢。
ArrayDeque：基于数组实现的双端队列，支持快速随机访问和插入删除操作，内存占用较小。但在大量元素的插入删除操作中，可能需要重新调整内部数组的容量，导致时间复杂度稍高。

举例：

public class DequeExample {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();

        // 在队列头部插入元素
        deque.addFirst(1);
        deque.offerFirst(2);

        // 在队列尾部插入元素
        deque.addLast(3);
        deque.offerLast(4);

        // 从队列头部删除元素
        int first = deque.removeFirst();
        System.out.println("Removed from first: " + first);

        // 从队列尾部删除元素
        int last = deque.removeLast();
        System.out.println("Removed from last: " + last);

        // 获取队列头部的元素
        int peekFirst = deque.peekFirst();
        System.out.println("Peek from first: " + peekFirst);

        // 获取队列尾部的元素
        int peekLast = deque.peekLast();
        System.out.println("Peek from last: " + peekLast);

        // 遍历队列中的元素
        System.out.println("Elements in the deque:");
        for (Integer element : deque) {
            System.out.println(element);
        }

        // 判断队列是否为空
        boolean isEmpty = deque.isEmpty();
        System.out.println("Is deque empty? " + isEmpty);

        // 获取队列的大小
        int size = deque.size();
        System.out.println("Size of the deque: " + size);
    }
}

LinkedList

LinkedList在栈和队列中均有应用，Linkedlist也有很多方法，下面对LinkedList的方法进行总结。

增加：add/offer/push/addFrist/offerFrist/offerLast等等
删除：remove/pop/poll/pollFirst/pollLast等等
如何进行区分？

这些方法分别来自于集合Collections，队列Queue，栈Stack，双端队列Deque，每对方法都有一定的含义，不建议笼统归为添加/删除。

LinkedList类图为：

类LinkedList实现了以上Deque,Queue,List，Collection的所有的方法。

add和remove是一对，源自Collection；
- 添加到队尾，从队头删除；
offer和poll是一对，源自Queue；
- 队列（先进先出 => 尾进头出），所以添加到队尾，从队头删除；
push和pop是一对，源自Deque，其本质是栈（Stack类由于某些历史原因，官方已不建议使用，使用Deque代替）；
- 栈（先进后出 => 头进头出），所以添加到队头，从队头删除；
offerFirst/offerLast和pollFirst/pollLast是一对，源自Deque，其本质是双端队列。
- 双端队列（两端都可以进也都可以出），根据字面意思，offerFirst添加到队头，offerLast添加到队尾，pollFirst从队头删除，pollLast从队尾删除。

在使用的时候，建议根据用途来使用不同的方法，比如你想把LinkedList当做集合list，那么应该用add/remove，如果想用作队列，则使用offer/poll，如果用作栈，则使用push/pop，如果用作双端队列，则使用offerFirst/offerLast/pollFirst/pollLast

fferLast添加到队尾，pollFirst从队头删除，pollLast`从队尾删除。**

码农公寓