代码随想录刷题day29|（栈与队列篇:队列）225.用队列实现栈

目录

一、队列基本知识

二、队列在Java中的实现

1.Queue

2.Deque

①实现普通队列

②实现栈

③实现双端队列

3.基于底层数据结构 

4.组合模式

三、相关算法题目

思路

代码

四、栈和队列总结

---

一、队列基本知识

队列只能在队尾添加元素，在队头删除元素，因此具有先进先出的特点（FIFO），比如排队，队列只能在首尾两端进行操作，做不到随机访问；

队尾入，队头处

常用操作方法：

入队（enQueue）：将元素添加到队列的末尾，如果队列已满，可能会抛出异常或返回错误（取决于实现）；

出队（deQueue）：在队头移除并返回队列的第一个元素，如果队列为空，可能会抛出异常或者返回错误；

获得队首元素（peek）：返回队列的第一个元素，但不移除它，如果队列为空，可能会抛出异常或返回错误；

判空（isEmpty）：检查队列是否为空，为空，返回true，不为空，返回false；

获取队列长度（size）：返回队列中元素的数量；

二、队列在Java中的实现

1.Queue

Queue是java中实现队列的接口（此处队列指普通队列，FIFO型），实现类有LinkedList（基于双向链表实现）、PriorityQueue（基于堆实现，元素按优先级出队），常用LinkedList；

Queue常用的方法有6个，分为3类：插入、移除、获取元素，每个方法存在两种形式：一种抛出异常（操作失败时），另一种返回一个特殊值（null或false）；

	操作失败情况	抛出异常	返回特殊值(null / false)
将元素e插入到队尾	超出队列容量	boolean  add(E e)	bollean  offer(E e)：false
获取并移除此队列的头	队列为空	E  remove()	E  poll()：null
获取但不移除此队列的头	队列为空	E  element()	E  peek()：null

参考：【Java】Java队列Queue使用详解_java queue-CSDN博客   博主：devnn

2.Deque

Deque 是一个双端队列接口，支持在两端插入和移除元素；继承自Queue接口；

Deque的实现类有ArrayDeque（基于动态数组实现）、LinkedList（基于双向链表实现）、LinkedBlocking Deque；

ArrayDeque在用作队列时快于LinkedList；

Deque有三种用途：普通队列、双端队列、栈，常用方法有12种，不同的数据结构实现选用不同方法；建议最好不要在Deque实现中插入null元素；

①实现普通队列

将元素添加到双端队列的末尾，从双端队列的开头移除元素，得到 FIFO（先进先出）行为

Deque<E> deque = new ArrayDeque<>();

Deque<E> deque = new LinkedList<>();

Queue<E> queue = new ArrayDeque<>();

Queue<E> queue = new LinkedList<>();

常用方法：从 Queue 接口继承的方法完全等效于 Deque 方法

		Queue方法	等效Deque方法
将指定元素插入Deque末尾 (入队)	抛出异常	boolean  add(E e)	void  addLast(E e)
	返回特殊值	bollean  offer(E e)	boolean offerLast(E e)
获取并移除Deque第一个元素（出队）	抛出异常	E  remove()	E  removeFirst()
	返回特殊值	E  poll()	E  pollFirst()
获取但不移除Deque第一个元素	抛出异常	E  element()	E  getFirst()
	返回特殊值	E  peek()	E  peekFirst()

示例代码：

Deque<String> deque = new LinkedList<>();//创建一个LinkedList实现类的对象
//Deque<String> deque = new ArrayDeque<>();//创建一个ArrayDeque实现类的对象
deque.addLast("A");
deque.addLast("B");
System.out.println(deque.removeFirst()); // 输出: A

②实现栈

Deque<E> stack = new ArrayDeque<>();

Deque<E> stack = new LinkedList<>();

详见栈 

代码随想录刷题day28|（栈与队列篇:栈）232.用栈实现队列-CSDN博客

③实现双端队列

Deque<E> deque = new ArrayDeque<>();

Deque<E> deque = new LinkedList<>(); 

Queue<E> queue = new ArrayDeque<>();

Queue<E> queue = new LinkedList<>();

注意：Queue接口只能实现队列，Deque接口既能实现队列，也能实现栈；

参考：【Java】Java双端队列Deque使用详解_dequeuejava-CSDN博客

3.基于底层数据结构 

数组：使用循环数组实现

链表：使用单链表实现

了解即可

4.组合模式

原理类似栈，常用LinkedList（底层是链表）实现队列，ArrayList底层是基于动态数组，在ArrayList中，移除第一个元素会导致后面的所有元素向前移动一位，时间复杂度为O(n)，如果出队操作频繁，时间开销比较大；

示例代码

import java.util.LinkedList;public class ComposedQueue<E> {private LinkedList<E> list;public ComposedQueue() {list = new LinkedList<>();}// 入队public void enqueue(E element) {list.addLast(element);}// 出队public E dequeue() {if (isEmpty()) {throw new IllegalStateException("队列为空");}return list.removeFirst();}// 查看队首元素public E peek() {if (isEmpty()) {throw new IllegalStateException("队列为空");}return list.getFirst();}// 判断队列是否为空public boolean isEmpty() {return list.isEmpty();}// 获取队列大小public int size() {return list.size();}
}

三、相关算法题目

225.用队列实现栈

思路

关键是出栈操作和获取栈顶元素操作，每次出栈时，将deque1中的元素倒序存入deque2中，原本元素队尾入，想要倒序就让元素从队头入，deque2运行addFirst(x)方法（从队头添加元素，元素顺序和deque1的入队出队顺序一致）即可实现，注意！倒序存入deque2的操作不需要在deque2为空时再操作，举个例子：

按照1 2 3的顺序

首先deque1执行push方法入队，deque1：（队头）1 2 3（队尾），相当于栈的入栈操作

deque2此时为空，将deque1中的元素倒序存入，deque2：3 2 1

deque2从队头出队：3 2 1，实现先进后出，相当于栈的出栈操作；

此时，按照4 5 的顺序再次入队deque1：4 5

如果之前deque2中只出队元素3，还剩元素2 1，此时不为空，假设时在deque2为空才运行addFirst方法，那么此时出栈操作，不会运行该方法，直接从deque2中移除元素，那么将会移除元素2，而在栈中，从栈顶往下应该是：5 4 2 1，应该出栈的是元素5

而每次出队时deque2都执行addFirst操作，此时deque2中：（队头）5 4 2 1（队尾）

出队元素为5，正确

代码

225. 用队列实现栈 - 力扣（LeetCode）

class MyStack {//成员变量Deque<Integer> deque1;Deque<Integer> deque2;public MyStack() {deque1 = new LinkedList<>();deque2 = new LinkedList<>();}    public void push(int x) {//deque1入队deque1.addLast(x);}    public int pop() {//deque1出队---倒序入队deque2---deque2出队method();return deque2.removeFirst();}public void method(){//确保deque2中包含的是deque1中所有元素的倒叙 不用借助数组 deque中有对应方法while(!deque1.isEmpty()){deque2.addFirst(deque1.removeFirst());}}public int top() {method();return deque2.getFirst();        }    public boolean empty() {return deque1.isEmpty() && deque2.isEmpty();}
}

四、栈和队列总结

java中栈和队列的实现有四种方式：

栈：Stack类、Deque接口、组合模式、底层数据结构（数组、链表）

队列：Queue接口和Deque接口、组合模式、底层数据结构（数组、链表）

其中Deque接口中两个实现类ArrayDeque和LinkedList都可以实现栈和队列，组合模式中通常封装List接口，创建其实现类ArrayList（底层数组）和LinkedList（底层链表）的实例对象，对于栈，常用ArrayList实现，对于队列，常用LinkedList实现；

对于栈，Stack类已经过时，java官方不推荐；

组合模式和底层数据结构的方式均需要手写方法，较为复杂，更推荐使用Deque接口；