1. 用栈实现队列(lc232)
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
进阶
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-queue-using-stacks
解题思路：
题目要求使用栈来实现队列，栈是先进后出表，队列是先进先出表，我们考虑两个栈来实现队列，分别称这两个栈为栈1，栈2。
栈1用来入队，就是说入队的所有元素都往栈1里面放，出队在栈2执行，如果栈2是空的，则将栈1里面所有的元素出栈，放入栈2，这样从栈1入，栈2出的元素满足了先进先出的原则，这样也就用两个栈实现了队列;
当两个栈均为空时，表示队列为空。
代码实现：
class MyQueue { private Stack<Integer> s1; private Stack<Integer> s2; public MyQueue() { s1 = new Stack<>(); s2 = new Stack<>(); } public void push(int x) { s1.push(x); } public int pop() { if(empty()) { return -1; } if(s2.isEmpty()) { while(!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if(empty()) { return -1; } if(s2.isEmpty()) { while(!s1.isEmpty()) { s2.push(s1.pop()); } } return s2.peek(); } public boolean empty() { return s1.isEmpty() && s2.isEmpty(); } }
提交结果：
2. 用队列实现栈(lc225)
题目描述:
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示：
1 <= x <= 9
最多调用100 次 push、pop、top 和 empty
每次调用 pop 和 top 都保证栈不为空
进阶: 你能否仅用一个队列来实现栈。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/implement-stack-using-queues
解题思路：
- 思路1
可以使用两个队列来实现本题, 分别称这两个队列为队1, 队2, 进队和出队永远往非空队列操作，如果进队时两个队列均为空，则任选一个队列入队;
入栈时，哪一个队列不为空，就在哪一个队列入队;
出栈时，先找到不为空的队列，然后获取该队列的大小size，将前size-1个元素转移到另一个队列，剩下最后一个元素出队返回，这样就实现了栈后进先出的特点, 同时保证了一个队列为空，另一个队列不为空;
获取栈顶元素，与出栈思路一样, 稍微有一点区别就是最后一个元素也需要放入到另一个栈中.
思路2
使用一个队列，队列是先进先出，栈是先进后出，在入栈前，我们先保存入队前的元素个数size，然后再进行新元素入队，最后将所有的旧元素重新入队（就是对所有的旧元素先出队再入队），这样做可以将旧元素（先进队列的元素）全部排在新元素（后进队的元素），这样在这个队列中，新元素总是能够排在队头，实现了栈的后进先出的特点。
//方法二: 使用一个栈 class MyStack { Queue<Integer> qu; public MyStack() { qu = new LinkedList<>(); } public void push(int x) { int size = this.qu.size(); this.qu.offer(x); while(size != 0) { this.qu.offer(this.qu.poll()); size--; } } public int pop() { if(this.empty()) { return -1; } return this.qu.poll(); } public int top() { if(this.empty()) { return -1; } return this.qu.peek(); } public boolean empty() { return this.qu.isEmpty(); } } //方法一: 使用两个栈 /* class MyStack { private Queue<Integer> qu1; private Queue<Integer> qu2; public MyStack() { qu1 = new LinkedList<>(); qu2 = new LinkedList<>(); } public void push(int x) { if(!qu1.isEmpty()) { qu1.offer(x); }else if(!qu2.isEmpty()) { qu2.offer(x); }else { qu1.offer(x); } } public int pop() { if(empty()) { return -1; } if(!qu1.isEmpty()) { int size = qu1.size(); for(int i = 0; i < size-1; i++) { qu2.offer(qu1.poll()); } return qu1.poll(); }else { int size = qu2.size(); for(int i = 0; i < size-1; i++) { qu1.offer(qu2.poll()); } return qu2.poll(); } } public int top() { if(empty()) { return -1; } int ret = -1; if(!qu1.isEmpty()) { int size = qu1.size(); for(int i = 0; i < size; i++) { ret = qu1.poll(); qu2.offer(ret); } }else { int size = qu2.size(); for(int i = 0; i < size; i++) { ret = qu2.poll(); qu1.offer(ret); } } return ret; } public boolean empty() { return qu1.isEmpty() && qu2.isEmpty(); } public static void main(String[] args) { MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); System.out.println(myStack.top()); } }*/
提交结果：
3. 设计循环队列(lc662)
题目描述:
设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。
你的实现应该支持如下操作：
MyCircularQueue(k): 构造器，设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空，返回 -1 。
Rear: 获取队尾元素。如果队列为空，返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
示例：
MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1); // 返回 true
circularQueue.enQueue(2); // 返回 true
circularQueue.enQueue(3); // 返回 true
circularQueue.enQueue(4); // 返回 false，队列已满
circularQueue.Rear(); // 返回 3
circularQueue.isFull(); // 返回 true
circularQueue.deQueue(); // 返回 true
cirularQueue.enQueue(4); // 返回 true
cirularQueue.Rear(); // 返回 4
提示：
所有的值都在 0 至 1000 的范围内；
操作数将在 1 至 1000 的范围内；
请不要使用内置的队列库。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/design-circular-queue
解题思路：
循环队列需要用顺序表，以循环的形式实现，难点在于判定队列是否满，是否为空;
主要有三种判断方式, 分别是:
- 通过添加 size 属性记录
- 保留一个位置
- 使用标记
具体思想可以看我另一篇博客循环队列的部分: 链接
这里采用第一种方法来实现, 记录队列元素个数count，当count的值与顺序表的长度相等时，代表队列已满 ; count值为0表示队列为空。
第一步，按照题目要求，根据传入的参数k创建顺序表大小。
第二步，记录队列元素个数count，当count的值与顺序表的大小相等时，代表队列已满。size值为0表示队列为空。
第三步，确定下标怎么变化，记顺序表长度为len，设置front指向队首元素, rear指向尾(下一次入队时的位置), 下标是由0n-1,n-10进行变化，所以进行下标前移时rear = (rear+1)%len，front = (front+1)% len。
要注意的是获取队尾元素需要拿到队尾元素的下标, 一般情况下是rear - 1, 但如果队尾元素在数组的最后一个位置, 此时rear-1是-1就会出现问题, 此时应该用len-1来表示队尾元素下标.
代码实现：
class MyCircularQueue { private int[] elem; private int front;//队头 private int rear;//队尾 private int count;//计数器 public MyCircularQueue(int k) { elem = new int[k]; } public boolean enQueue(int value) { if(isFull()) { return false; } elem[rear] = value; rear = (rear+1) % elem.length; count++; return true; } public boolean isFull() { if(count == elem.length) { return true; } return false; } public boolean deQueue() { if(isEmpty()) { return false; } front = (front+1)% elem.length; count--; return true; } public boolean isEmpty() { if(count == 0) { return true; } return false; } public int Front() { if(isEmpty()) { return -1; } return elem[front]; } public int Rear() { if(isEmpty()) { return -1; } int index = rear == 0 ? elem.length-1 : rear - 1; return elem[index]; } }
