1. 栈与队列理论基础
1.1 栈-概念
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据在栈顶。
1.2 栈-使用
Stack继承了Vector，Vector和ArrayList类似，都是动态的顺序表，不同的是Vector是线程安
全的。
1.3 栈-模拟实现
public class MyStack { private int[] elem; private int usedSize; public MyStack() { this.elem = new int[5];//初始长度为5，随你定 } //入栈 public void push(int val) { if (isFull()) { elem = Arrays.copyOf(elem, 2 * elem.length);//如果满了扩容 } elem[usedSize] = val; usedSize++; } //栈是否满 public boolean isFull() { return usedSize == elem.length; } //出栈 public int pop() { //判断栈是否为空 if (empty()) {//抛出栈空异常 throw new StackEmptyException("栈为空"); } //开始删除 //这种删除方法原理就是把usedSize往前挪，原本最后位置的元素就放在那但没法调用了，下次添加元素就直接覆盖 return elem[--usedSize];//如果是return elem[usedSize--]就没有返回最后的元素，是返回最后元素的下一个位置 } //栈是否为空 public boolean empty() { return usedSize == 0; } //获取栈顶元素，但不弹出 public int peek() { //判断栈是否为空 if (empty()) {//抛出栈空异常 throw new StackEmptyException("栈为空"); } //开始获取 return elem[usedSize - 1];//不用删除，只需要获取 } //递归打印 public void recursivePrint(MyStack stack) { if (!stack.empty()) { int value = stack.pop(); // 弹出栈顶元素 recursivePrint(stack); // 递归打印剩余栈中的元素 System.out.print(value + " "); // 打印当前弹出的元素 stack.push(value); // 将元素重新压回栈中，保持栈的原有状态 } } }
1.4 队列-概念
队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)。
入队列：进行插入操作的一端称为队尾（Tail/Rear）
出队列：进行删除操作的一端称为队头（Head/Front）
1.5 队列-使用
在Java中，Queue是个接口，底层是通过链表实现的。
注意：Queue是个接口，在实例化时必须实例化LinkedList的对象，因为LinkedList实现了Queue接口。
1.6 队列-模拟实现
public class MyQueue { static class ListNode{ public int val; public ListNode next;//单链表实现队列 public ListNode(int val) { this.val = val; } } public ListNode head; public ListNode last;//方便实现单链表的尾插法 public int usedSize; //入队操作（单链表的尾插法） public void offer(int val){ ListNode node=new ListNode(val); if(head==null){ head=node; last=node; }else{ last.next=node; last=last.next; } } public int getUsedSize(){ return usedSize; } //弹出元素（单链表的删除头节点） public int poll(){ if(head==null){ return -1; } int val=-1; if(head.next==null){ val=head.val; head=null; last=null; return val; } val= head.val; head=head.next; usedSize--; return val; } //获取队头元素 public int peek(){ if(head==null){ return -1; } return head.val; } }
2. LeetCode 232. 用栈实现队列
2.1 思路
- 队列是先进先出的，栈是先进后出的，用一个栈模拟队列的先进先出的行为是不可能的，肯定是先进后出，因此借用另一个栈
- 此时两个栈一个叫输入栈一个叫输出栈，类似负负得正的思想，做两次先进后出就做到了先进先出的操作了
- 进队：这个操作很简单，全部进入输入栈
- 出队：这个操作比较难，当输出栈为空时，就需要把输入栈的元素全部按照栈出栈的方式然后进入输出栈，此时顺序就是一致的了，一直到输出栈为空才把输入栈的元素全部放入到输出栈中，注意是全部，如果不是全部，那顺序会乱的
- 查看队首元素：类似出队的方式，只是不要弹出，只是查看
- 判断队列是否为空：输入栈和输出栈均为空则模拟队列为空
- 注意，定义stack1和stack2时不要在构造方法里声明创建，这样是局部变量的，下面的方法访问不到，因此要声明为全局变量
2.2 代码
class MyQueue { Stack<Integer> stackIn; Stack<Integer> stackOut; /** Initialize your data structure here. */ public MyQueue() { stackIn = new Stack<>(); // 负责进栈 stackOut = new Stack<>(); // 负责出栈 } /** Push element x to the back of queue. */ public void push(int x) { stackIn.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { dumpstackIn(); return stackOut.pop(); } /** Get the front element. */ public int peek() { dumpstackIn(); return stackOut.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stackIn.isEmpty() && stackOut.isEmpty(); } // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中 private void dumpstackIn(){ if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){ stackOut.push(stackIn.pop()); } } }
3. LeetCode 225. 用队列实现栈
3.1 思路
- 可用一个队列实现模拟实现栈，也可用两个队列实现，下面将一个队列的
- 这里关键在于出栈操作：我们按照正常顺序入队1、2、3，正常顺序入栈1、2、3，按照栈应该弹出的是3先，但队列是先弹出1，因此我们让前两个元素依次进行出队、入队的操作，就是先出队然后立刻入队，这样原来的队首元素就跑到队尾了，直到进行到元素3才停止，这时出队就是3了
- 问题关键：怎么知道先把1、2先弹出，然后再弹出3，那么我们假设队列有size个元素，就把size-1个元素依次先弹出再入队，然后再把原本最后一个元素弹出即可
3.2 代码
class MyStack { Queue<Integer> queue; public MyStack() { queue = new LinkedList<>(); } public void push(int x) { queue.add(x); } public int pop() { rePosition(); return queue.poll(); } public int top() { rePosition(); int result = queue.poll(); queue.add(result); return result; } public boolean empty() { return queue.isEmpty(); } public void rePosition(){ int size = queue.size(); size--; while(size-->0) queue.add(queue.poll()); } }
3.3 用两个队列实现栈的代码
class MyStack { //q1作为主要的队列，其元素排列顺序和出栈顺序相同 Queue<Integer> q1 = new ArrayDeque<>(); //q2仅作为临时放置 Queue<Integer> q2 = new ArrayDeque<>(); public MyStack() { } //在加入元素时先将q1中的元素依次出栈压入q2，然后将新加入的元素压入q1，再将q2中的元素依次出栈压入q1 public void push(int x) { while (q1.size() > 0) { q2.add(q1.poll()); } q1.add(x); while (q2.size() > 0) { q1.add(q2.poll()); } } public int pop() { return q1.poll(); } public int top() { return q1.peek(); } public boolean empty() { return q1.isEmpty(); } }
