栈和队列（摘录）
栈：先进后出（后进先出），Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安全的；
队列：先进先出（后进后出），队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。Java在Java中，Queue是个接口，底层是通过链表实现的。
注意： Queue 是个接口，在实例化时必须实例化 LinkedList 的对象，因为 LinkedList 实现了 Queue 接口。
队列的分类：顺序队列、链式队列。
顺序队列：队列的存在形式是队列中的元素是连续的，就像数组。
循环队列：首尾相接的顺序存储队列，顾名思义循环队列就是队列的内存可以循环使用。
链式队列：跟线性表的单链表一样，只是说只能从头出从尾进而已。
双端队列：又名double ended queue，简称deque，双端队列没有队列和栈这样的限制级，它允许两端进行入队和出队操作，也就是说元素可以从队头出队和入队，也可以从队尾出队和入队。
LeetCode：232.用栈实现队列
1.思路
定义两个栈，一个入栈操作，一个出栈操作。注意一个特殊节点：出栈时或者返回栈顶元素时，需要注意判空，同时将入栈的栈中数据全部压入出栈的栈中。不然顺序会发生错乱。
栈操作方法：new（新建）push（入栈）pop（出栈）peek（获取栈顶元素）isEmpty（判断栈是否为空）
2.代码实现
1class MyQueue { 2 3 Stack<Integer> stackIn; 4 Stack<Integer> stackOut; 5 6 public MyQueue() { 7 stackIn = new Stack<>(); 8 stackOut = new Stack<>(); 9 } 10 11 public void push(int x) { 12 stackIn.push(x); 13 } 14 15 public int pop() { 16 dumpstackIn(); 17 return stackOut.pop(); 18 } 19 20 public int peek() { 21 // 方法一： 22 // if (stackOut.isEmpty()) { 23 // while (!stackIn.isEmpty()) { 24 // stackOut.push(stackIn.pop()); 25 // } 26 // } 27 28 // 方法二 29 dumpstackIn(); 30 return stackOut.peek(); 31 } 32 33 public boolean empty() { 34 return stackIn.isEmpty() && stackOut.isEmpty(); 35 } 36 37 public void dumpstackIn() { 38 if (stackOut.isEmpty()) { 39 while (!stackIn.isEmpty()) { 40 stackOut.push(stackIn.pop()); 41 } 42 } 43 } 44}
3.复杂度分析
时间复杂度: push和empty为O(1), pop和peek为O(n)
空间复杂度: 2O(n)
参考链接：
LeetCode:225. 用队列实现栈
1.思路
两个队列，一个做交换，起控制作用，一个做入队、出队操作。
队列的底层数据结构：链表、数组。
队列操作方法：
入队列：boolean offer(E e)
出队列：E poll()
获取队头元素：peek()
获取队列中有效元素个数：int size()
检测是否为空：boolean isEmpty()
2.代码实现
1class MyStack { 2 Queue<Integer> queue1; 3 Queue<Integer> queue2; 4 5 public MyStack() { 6 queue1 = new LinkedList<>(); 7 queue2 = new LinkedList<>(); 8 } 9 10 public void push(int x) { 11 queue2.offer(x); 12 while (!queue1.isEmpty()) { 13 queue2.offer(queue1.poll()); 14 } 15 Queue<Integer> queueTemp = queue1; 16 queue1 = queue2; 17 queue2 = queueTemp; 18 19 } 20 21 public int pop() { 22 return queue1.poll(); 23 } 24 25 public int top() { 26 return queue1.peek(); 27 } 28 29 public boolean empty() { 30 return queue1.isEmpty(); 31 } 32}
3.复杂度分析
时间复杂度: push为O(n)，其他为O(1)
空间复杂度: O(n)
小结
两者相互实现的底层逻辑还是实现"先进先出"和"后进后出"的特性，对队列和栈的底层数据结构掌握还有待深化。
