前言

大家如果对于队列的性质等不太了解的话，我推荐一篇博客，写得很细节，大家可以去看看栈 和 队列 【 Stack And Queue】- java - 细节决定一切

1.用栈来实现队列

我们要注意一个点，栈是先进后出，队列是先进先出，用一个栈是很难实现队列的,我们可以让一个栈用来入队列，另外一个栈来出队列

1.1思路

入队:先把所有元素放到栈A中(栈B用来出队)
出队:先把栈A中的所有元素出栈进入到栈B中，然后栈B的栈顶元素就是要出队的元素
取队首元素：和出队操作类似，先把A元素进入到B，取栈B的栈顶元素
判断是否为空：看A和B是否同时为空

1.2图示

1.3代码

class MyQueue {private Stack<Integer> stackIn;private Stack<Integer> stackOut;public MyQueue() {stackIn=new Stack();stackOut=new Stack();}//入队public void push(int x) {if(stackOut.isEmpty()){stackIn.push(x);}else{while(!stackOut.isEmpty()){stackIn.push(stackOut.pop());}stackIn.push(x);}}public int pop() {while(!stackIn.isEmpty()){stackOut.push( stackIn.pop());}return stackOut.pop();}public int peek() {while(!stackIn.isEmpty()){stackOut.push( stackIn.pop());}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();*/

2.用队列来实现栈

用队列实现栈

• 仅仅使用两个队列实现栈的四种操作(push,pop,tip,empty)
• 我们只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

2.2思路

一个队列为主队列，一个为辅助队列，当入栈操作时，我们先将主队列内容导入辅助队列，然后将入栈元素放入主队列队头位置，再将辅助队列内容，依次添加进主队列即可。

2.2代码

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}public int pop() {return queue1.poll();}public int top() {return queue1.peek();}public boolean empty() {return queue1.isEmpty();}
}

3.最小栈

题目链接最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

3.1思路

• 因为要求在常数时间内检索到最小元素，所以用一个栈是无法达到的，因为需要O(n)
• 我们可以用一个辅助栈B来存放栈的最小元素，那么直接取出辅助栈的栈顶元素就是栈的最小元素
• 入栈的话，A直接入栈，B如果为空，则直接入栈，B如果不是空，则比较B的栈顶和A的大小关系，如果待入栈元素比B栈顶元素小，则入B
• 取栈顶：直接取A栈顶
• 取最小元素：直接取B栈顶元素

3.2图示

下面的流程图来自博主独一无二的哈密瓜

3.3代码

class MinStack {//使用两个栈private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack=new Stack();minStack=new Stack();}public void push(int val) {stack.push(val);if(minStack.isEmpty()){minStack.push(val);}else{if(val<=minStack.peek()){minStack.push(val);}}}public void pop() {if(!stack.isEmpty()){int val=stack.pop();if(val==minStack.peek()){minStack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/

4.删除字符串中所有相邻重复项

删除字符串中所有相邻重复项

4.1思路

• 我们可以使用栈来完成
• 当栈为空，则把字符直接加入栈中
• 如果栈非空
  • 若栈顶元素和待加入元素相等，则栈顶元素出栈
  • 若栈顶元素和待加入元素不相等，则该元素入栈
• 最后把栈中所有元素出栈，然后反转就是结果，为了简单一点，我们可以使用ArrayDeque双端队列

4.2代码

class Solution {public String removeDuplicates(String S) {//ArrayDeque会比LinkedList在除了删除元素这一点外会快ArrayDeque<Character> deque = new ArrayDeque<>();char ch;for (int i = 0; i < S.length(); i++) {ch = S.charAt(i);if (deque.isEmpty() || deque.peek() != ch) {deque.push(ch);} else {deque.pop();}}String str = "";//剩余的元素即为不重复的元素while (!deque.isEmpty()) {str = deque.pop() + str;}return str;}
}