Leetcoder Day9｜栈与队列part01

语言：Java/C++

理论基础

C++

栈

队列

Java

栈

队列

编辑

232.用栈实现队列

225. 用队列实现栈

Queue

Deque

今日心得

理论基础

又是考研时数据结构里接触到的老朋友，栈是先进后出，队列是先进先出。

C++

现在刷题除了思路还要重点关注程序语言中的细节，卡哥给了C++中栈需要注意的一些问题：

C++中stack 是容器么？
我们使用的stack是属于哪个版本的STL？
我们使用的STL中stack是如何实现的？
stack 提供迭代器来遍历stack空间么？

栈和队列是STL（C++标准库）里面的两个数据结构，目前常用的C++中的STL有以下三种：

HP STL 其他版本的C++ STL，一般是以HP STL为蓝本实现出来的，HP STL是C++ STL的第一个实现版本，而且开放源代码。
P.J.Plauger STL 由P.J.Plauger参照HP STL实现出来的，被Visual C++编译器所采用，不是开源的。
SGI STL 由Silicon Graphics Computer Systems公司参照HP STL实现，被Linux的C++编译器GCC所采用，SGI STL是开源软件，源码可读性甚高。

栈

提供push 和 pop 等接口

所有元素必须符合先进后出（FILO）规则

栈不提供走访功能，也不提供迭代器(iterator)

因此C++中的栈是以底层容器完成其所有的工作，对外提供统一的接口，底层容器是可插拔的（也就是说可以控制使用哪种容器来实现栈的功能）

所以 STL中栈往往不被归类为容器，而被归类为container adapter（容器适配器）。

从上图可见，栈的底层实现可以是vector，deque，list 都是可以的，主要就是数组和链表的底层实现。常用的SGI STL，如果没有指定底层实现，默认是以deque为缺省情况下栈的底层结构。deque是一个双向队列，实现栈时，只要封住一段，只开通另一端就可以了。

也可以指定vector为栈的底层实现，初始化语句如下：

std::stack<int, std::vector<int> > third;  // 使用vector为底层容器的栈

队列

队列为先进先出（FIFO），同样不允许有遍历行为，不提供迭代器, SGI STL中队列一样是以deque为缺省情况下的底部结构。也不被归类为容器，而被归类为container adapter（容器适配器）。

也可以指定 list 为起底层实现，初始化queue的语句如下：

std::queue<int, std::list<int>> third; // 定义以list为底层容器的队列

Java

栈

栈的底层实现有两种：

基于数组的实现：顺序栈（ArrayList）
基于链表的实现：链式栈（LinkedList）

栈的基本操作包括入栈（push），即将元素添加到栈顶；出栈（pop），即将栈顶元素移除；以及访问栈顶元素（peek）

// 基于数组实现链表
public class Stack<E> {private E[] elementData; // 栈中的元素private int size; // 当前栈中元素个数public Stack() {elementData = (E[]) new Object[10]; // 默认长度为10}public Stack(int initCap) {elementData = (E[]) new Object[initCap]; // 初始长度}// 入栈public void push(E value) {// 扩容if(size == elementData.length) {int oldLength = elementData.length;int newLength = oldLength << 1;elementData = Arrays.copyOf(elementData, newLength);}// 在数组尾部添加元素elementData[size++] = value;}// 出栈,返回原来的栈顶元素public E pop () {if(getSize() == 0) {throw new NoSuchElementException("栈中没有元素！");}// 得到原来的栈顶元素位置E oldVaule = elementData[size - 1];size--;elementData[size] = null;return oldVaule;}// 查看栈顶元素public E peek() {if(getSize() == 0) {throw new NoSuchElementException("栈中没有元素！");}return elementData[size - 1];}// 获取当前栈的长度public int getSize() {return size;}@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {stringBuilder.append(elementData[i]);if(i != size - 1) {stringBuilder.append(",");}}stringBuilder.append("]");return stringBuilder.toString();}
}

队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首。

队列和栈相同也是可以使用数组和链表实现，但是对于队列来说使用链表的结构效率更高。

/*** 基于链表的队列*/
public class LinkedQueue{private Node head;private Node tail;private int size;private class Node {private int data;private Node next;public Node(int data) {this.data = data;}}// 入队public void offer(int value) {Node node = new Node(value);if(head == null) {head = tail = node;} else {tail.next = node;tail = node;}size++;}// 出队(队首元素出队）public int poll() {if(size == 0) {throw new NoSuchElementException("对列为空！");} else {int oldValue = head.data;Node tempHead = head;head = head.next;tempHead.next = null;size--;return oldValue;}}// 查看队首元素public int peek() {if(size == 0) {throw new NoSuchElementException("对列为空！");}return head.data;}public String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("front[");Node node = head;while (node != null) {stringBuilder.append(node.data);if(node.next != null) {stringBuilder.append(",");}node = node.next;}stringBuilder.append("]tail");return stringBuilder.toString();}
}

这里还要列出一下队列中Queue和Deque的基本操作：

Queue：

Queue的6个方法：

压入元素(添加)：add()、offer()
相同：未超出容量，从队尾压入元素，返回压入的那个元素。
区别：在超出容量时，add()方法会对抛出异常，offer()返回false

弹出元素(删除)：remove()、poll()
相同：容量大于0的时候，删除并返回队头被删除的那个元素。
区别：在容量为0的时候，remove()会抛出异常，poll()返回false

获取队头元素(不删除)：element()、peek()
相同：容量大于0的时候，都返回队头元素。但是不删除。
区别：容量为0的时候，element()会抛出异常，peek()返回null。

普通队列（Queue）是指实现了先进先出的基本队列，例如 ArrayBlockingQueue 和 LinkedBlockingQueue，其中

ArrayBlockingQueue是用数组实现的普通队列，如下图所示

LinkedBlockingQueue 是使用链表实现的普通队列，如下图所示：

⚠️一般情况下 offer() 和 poll() 方法配合使用，put() 和 take() 阻塞方法配合使用，add() 和 remove() 方法配合使用。程序中常用的是 offer() 和 poll() 方法，这两个方法比较友好，不会报错。

Deque（双端队列）：

双端队列（Deque）是指队列的头部和尾部都可以同时入队和出队的数据结构，如下图所示：

232.用栈实现队列

使用栈实现队列的下列操作：

push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。

说明:

你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）。

这道题首先就是捋清栈和队列的区别，栈的所有操作只能从栈顶进行，如进去的顺序是1、2、3、4，出去的顺序是4、3、2、1，而队列是队尾进，队首出，进和出的顺序是一样的，因此不难看出，我们需要两个栈来实现队列，一个将1、2、3、4压入栈中再逐一弹出，弹出顺序为4、3、2、1再进入另一个栈中，再次弹出，顺序就是1、2、3、4了。这个是整体的一个思路，但是如果涉及到出栈，判空等操作，需要更加注意细节。而peek本质上和pop是一样的。

class MyQueue {Stack<Integer> stackIn;Stack<Integer> stackOut;//initializepublic MyQueue() {stackIn=new Stack<>();  //输入栈stackOut=new Stack<>(); //输出栈}// 如果stackOut为空，那么将stackIn中的元素全部放入stackOut中private void dumpStackIn(){if(!stackOut.isEmpty()) return;while(!stackIn.isEmpty()){stackOut.push(stackIn.pop());}}public void push(int x) {stackIn.push(x);  //将元素放入输入栈}public int pop() {dumpStackIn();return stackOut.pop();}public int peek() {dumpStackIn();return stackOut.peek();}public boolean empty() {return stackIn.isEmpty() && stackOut.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

225. 用队列实现栈

使用队列实现栈的下列操作：

push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空

注意:

你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。

在理论基础中，有涉及到了Java中队列的两种类型，Queue和Deque。其实队列的形式有很多，常见的有8种，这是其中最常使用的两种。因为知道了双端队列的技巧，所以用队列实现栈很容易就想到了使用双端队列，从一头进和出队列即可。用普通的队列亦可实现：如将1、2、3、4入队，将除了4以外的其他元素弹出并再次入队，弹出4，即可实现pop操作。

Queue

class MyStack {Queue<Integer> queue;public MyStack() {queue=new LinkedList<>();}private void rePush(){int size=queue.size();while(size-->1){queue.offer(queue.poll());//把前size-1个重新入队,同时size--}}public void push(int x) {queue.offer(x);rePush(); //将队列中的前n-1个元素弹出并放回队列}public int pop() {return queue.poll();}public int top() {return queue.peek();}public boolean empty() {return queue.isEmpty();}
}

时间复杂度: pop为O(n)，其他为O(1)
空间复杂度: O(n)

我在第一次写的时候，在push中使用了一次rePush操作，又在top中使用了一次，导致进行了两次重入队，输出错误，要记住如果在push里已经放入并重新入队，其他操作里就不需要了。

Deque

class MyStack {Deque<Integer> deque;public MyStack() {deque=new ArrayDeque<>();}public void push(int x) {deque.offerLast(x);}public int pop() {return deque.pollLast();}public int top() {return deque.peekLast();}public boolean empty() {return deque.isEmpty();}
}