Java中队列queue和Deque

女爷i 2022-01-23 08:11 155阅读 0赞

前言：学过数据结构的，一定对队列不陌生，java也实现了队列。接下来，介绍一下deque和queue

1、Queue

队列， 一种常用的数据结构，可以将队列看做是一种特殊的线性表，该结构遵循的先进先出原则。Java中，LinkedList实现了Queue接口,因为LinkedList进行插入、删除操作效率较高   
      相关方法：   
      boolean offer(E e):将元素追加到队列末尾,若添加成功则返回true。   
      E poll():从队首删除并返回该元素。   
      E peek():返回队首元素，但是不删除   
      示例：

public class QueueDemo {
        public static void main(String [] args) {
            Queue<String> queue = new LinkedList<String>();
            //追加元素
            queue.offer("one");
            queue.offer("two");
            queue.offer("three");
            queue.offer("four");
            System.out.println(queue);
            //从队首取出元素并删除
            String poll = queue.poll();
            System.out.println(poll);
            System.out.println(queue);
            //从队首取出元素但是不删除
            String peek = queue.peek();
            System.out.println(peek);
            System.out.println(queue);
            //遍历队列，这里要注意，每次取完元素后都会删除，整个
            //队列会变短，所以只需要判断队列的大小即可
            while(queue.size() > 0) {
                System.out.println(queue.poll());
            }
        }
    }

运行结果：   
\[one, two, three, four\]   
one   
\[two, three, four\]   
two   
\[two, three, four\]   
two   
three   
four

2、Deque

双向队列，指该队列两端的元素既能入队(offer)也能出队(poll),如果将Deque限制为只能从一端入队和出队，则可实现栈的数据结构。对于栈而言，有入栈(push)和出栈(pop)，遵循先进后出原则

常用方法如下：   
      void push(E e):将给定元素”压入”栈中。存入的元素会在栈首。即:栈的第一个元素   
      E pop():将栈首元素删除并返回。   
      示例：

public class DequeDemo {
        public static void main(String[] args) {
            Deque<String> deque = new LinkedList<String>();
            deque.push("a");
            deque.push("b");
            deque.push("c");
            System.out.println(deque);
            //获取栈首元素后，元素不会出栈
            String str = deque.peek();
            System.out.println(str);
            System.out.println(deque);
            while(deque.size() > 0) {
                //获取栈首元素后，元素将会出栈
                System.out.println(deque.pop());
            }
            System.out.println(deque);
        }
    }

运行结果：   
\[c, b, a\]   
c   
\[c, b, a\]   
c   
b   
a   
\[\]