算法day09-栈与队列（1）

目录

• 力扣232. 用栈实现队列
  
• 力扣225. 用队列实现栈
  
• 力扣20. 有效的括号
  
• 力扣1047. 删除字符串中的所有相邻重复项
  

 一、用栈实现队列

　　主要思路：我们使用两个栈来实现一个队列的功能：其中一个作为输入栈，用于接收通过 push 操作传入的数据；另一个作为输出栈，专门用于处理 pop 和 peek 操作。当需要执行 pop 或 peek 时，如果输出栈为空，我们就将输入栈中的所有元素依次弹出，并按顺序压入输出栈。这样一来，输出栈的栈顶元素就对应了队列的队首，实现了先进先出的队列行为。

1. class MyQueue {
2.     Deque<Integer> inStack;
3.     Deque<Integer> outStack;
5.     public MyQueue() {
6.         //初始化两个栈
7.         inStack = new ArrayDeque<Integer>();
8.         outStack = new ArrayDeque<Integer>();
9.     }
10.    
11.     public void push(int x) {
12.         inStack.push(x);        
13.     }
14.    
15.     public int pop() {
16.         if(outStack.isEmpty()){         //当辅助栈里面镁元素时，要把入栈的元素倒压进出栈
17.             in2out();
18.         }
19.         return outStack.pop();
20.     }
21.    
22.     public int peek() {
23.         if(outStack.isEmpty()){
24.             in2out();
25.         }
26.         return outStack.peek();
27.     }
28.    
29.     public boolean empty() {
30.         return inStack.isEmpty() && outStack.isEmpty();
31.     }
33.     public void in2out(){
34.         while(!inStack.isEmpty()){
35.             outStack.push(inStack.pop());       //把入栈的元素压进出栈
36.         }
37.     }
38. }
39. //时间复杂度：O(1)
40. //空间复杂度：O(N)

复制代码

二、用队列实现栈

　　主要思路：这里可以用两个队列来实现一个栈。首先我们定义两个队列，一个用作辅助。当我们push一个元素时，先将元素放到队列2中，然后将队列 1的所有元素出队加到队列2的末尾，然后再将队列2的所有元素出队放到队列1中。这样可以确保每次入栈操作都确保队列1的前端为栈顶元素，出栈和获得栈顶元素操作都可以简单实现。

1. class MyStack {
2.     Queue<Integer> queue1;
3.     Queue<Integer> queue2;
4.     public MyStack() {
5.         queue1 = new LinkedList<Integer>();
6.         queue2 = new LinkedList<Integer>();
7.     }
8.    
9.     public void push(int x) {
10.         queue2.offer(x);
11.         while(!queue1.isEmpty()){
12.             queue2.offer(queue1.poll());
13.         }
15.         //交换queue1和queue2的元素
16.         Queue<Integer> temp = queue1;
17.         queue1 = queue2;
18.         queue2 = temp;
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. }
33. //时间复杂度：O(n）入栈，O（1）：出栈、查看队首元素、判断为空
34. //空间复杂度：O(N)

复制代码

　　方法二：用一个队列也可以实现栈。只需要修改：在每次入栈的时候，先统计此时队列的长度，然后将元素加入到队列的尾部，然后把本来有的几个元素都从对头弹出并从队尾压入，这样就能保持每次push 的元素都在最开头。

1. class MyStack {
2.     Queue<Integer> queue;
4.     public MyStack() {
5.         queue = new LinkedList<Integer>();
6.     }
7.    
8.     public void push(int x) {
9.         int n = queue.size();
10.         queue.offer(x);
11.         for (int i = 0; i < n; i++) {
12.             queue.offer(queue.poll());
13.         }
14.     }
15.    
16.     public int pop() {
17.         return queue.poll();
18.     }
19.    
20.     public int top() {
21.         return queue.peek();
22.     }
24.     public boolean empty() {
25.         return queue.isEmpty();
26.     }
27. }

复制代码

三、有效的括号

 　　主要思路：首先用一个哈希表记录右-左括号匹配对，然后去遍历输入的字符串，当前字符若是左括号则直接压入栈，若是右括号则进行判断：若栈为空，或者这个右括号与此时栈顶元素不匹配，则说明此字符串不是有效括号字符串。否则弹出字符。
[code]class Solution {    public boolean isValid(String s) {        int n = s.length();        if( n % 2 == 1 ){       //如果长度为奇数，则一定不能匹配            return false;        }        Map map = new HashMap();        map.put(')', '(');        map.put(']', '[');        map.put('}', '{');        Deque stack = new ArrayDeque();        for(int i=0; i