栈和队列(Java实现)

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

  • stack类
  • LinkedList实现(继承了Deque接口)

(1) Stack实现

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

stack类图为:

栈和队列(Java实现)-LMLPHP

举例:

//栈的实现一,内置类
//底层实现: 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可以进行以下操作:

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

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

  1. LinkedList:基于链表实现的双端队列,支持快速插入和删除操作,但在随机访问和迭代性能上相对较慢。
  2. 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类图为:

栈和队列(Java实现)-LMLPHP

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

  • addremove是一对,源自Collection

    • 添加到队尾,从队头删除;
  • offerpoll是一对,源自Queue

    • 队列(先进先出 => 尾进头出),所以添加到队尾,从队头删除;
  • pushpop是一对,源自Deque,其本质是栈(Stack类由于某些历史原因,官方已不建议使用,使用Deque代替);

    • 栈(先进后出 => 头进头出),所以添加到队头,从队头删除;
  • offerFirst/offerLastpollFirst/pollLast是一对,源自Deque,其本质是双端队列。

    • 双端队列(两端都可以进也都可以出),根据字面意思,offerFirst添加到队头,offerLast添加到队尾,pollFirst从队头删除,pollLast从队尾删除。

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

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

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

03-24 12:20