算法笔记|Day9栈与队列

算法笔记|Day9栈与队列

• ☆☆☆☆☆leetcode 232.用栈实现队列
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 225. 用队列实现栈
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 20. 有效的括号
• • 题目分析
  • 代码
• ☆☆☆☆☆leetcode 1047. 删除字符串中的所有相邻重复项
• • 题目分析
  • 代码

☆☆☆☆☆leetcode 232.用栈实现队列

题目链接：leetcode 232.用栈实现队列

题目分析

1.需要输入栈和输出栈两个栈，push时只需放入输入栈，pop时需要考虑输出栈是否为空，若不为空直接弹出输出栈，若为空需将输入栈数据全部弹出导入到输出栈后再弹出输出栈，peek可以在pop基础上push弹出元素并返回，判断是否为empty只需判断输入栈和输出栈是否均为空；
2.push和empty的时间复杂度为O(1)，pop和peek的时间复杂度为O(n)，空间复杂度为O(n)。

代码

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

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

☆☆☆☆☆leetcode 225. 用队列实现栈

题目链接：leetcode 225. 用队列实现栈

题目分析

1.采用一个队列，push只需在队列添加，pop则需将队列除最后一个元素外的元素依次弹出并添加到队尾再弹出，top可以在pop基础上push并返回pop值，判断是否为empty只需判断队列是否为空；
2.push和empty的时间复杂度为O(1)，pop和top的时间复杂度为O(n)，空间复杂度为O(n)。

代码

class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue=new LinkedList<>();
    }
    
    public void push(int x) {
        queue.add(x);
    }
    
    public int pop() {
        int size=queue.size();
        size--;
        while(size>0){
            queue.add(queue.poll());
            size--;
        }
        return queue.poll();
    }
    
    public int top() {
        int res=pop();
        push(res);
        return res;
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

☆☆☆☆☆leetcode 20. 有效的括号

题目链接：leetcode 20. 有效的括号

题目分析

1.依次遍历各个元素，出现左括号时将对应的右括号入栈，直到出现右括号，需要判断是否与栈顶元素相同或者栈是否为空，依次考虑各种情况即可；
2.时间复杂度为O(n)，空间复杂度为O(n)。

代码

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque=new LinkedList();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='(')
                deque.push(')');
            else if(s.charAt(i)=='[')
                deque.push(']');
            else if(s.charAt(i)=='{')
                deque.push('}');
            else if(deque.isEmpty()||s.charAt(i)!=deque.peek())
                return false;
            else
                deque.pop();
        }
        return deque.isEmpty();
    }
}

☆☆☆☆☆leetcode 1047. 删除字符串中的所有相邻重复项

题目链接：leetcode 1047. 删除字符串中的所有相邻重复项

题目分析

1.依次遍历各个元素，若与前一个元素相等则pop，若不等则继续push，最后将数组转为字符串；
2.本题还可以采用双指针法，fast指针遍历各个元素，slow指针指向删除后该元素对应的下标，若slow指针指向元素和上一个元素相等需要slow减一以覆盖该元素，否则slow加一继续遍历；
3.时间复杂度为O(n)，空间复杂度为O(n)。

代码

1.使用栈
class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> deque=new LinkedList<>();
        for(int i=0;i<s.length();i++){
            if(deque.isEmpty()||deque.peek()!=s.charAt(i))
                deque.push(s.charAt(i));
            else
                deque.pop();
        }
        String str="";
        while(!deque.isEmpty()){
            str=deque.pop()+str;
        }
        return str;       
    }
}

2.双指针法
class Solution {
    public String removeDuplicates(String s) {
        char ch[]=s.toCharArray();
        int slow=0,fast=0;
        for(;fast<s.length();fast++){
            ch[slow]=ch[fast];
            if(slow>0&&ch[slow]==ch[slow-1]){
                slow--;
            }else{
                slow++;
            }
        }
        return new String(ch,0,slow);
    }
}