day11leetcode232,225,20,1047

225. 用队列实现栈

利用两个栈来实现队列的基本操作
一个 负责进栈 一个负责出栈

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;
    public MyQueue() {
        stackIn=new Stack<>();
        stackOut=new Stack<>();
    }
    
    public void push(int x) {
        stackIn.push(x);  // 进栈 直接对 stackIn  进行push 操作
    }
    
    public int pop() {
        if(stackOut.isEmpty()){       //出栈 首先要判断  stackout 是否为空
            while(!stackIn.isEmpty()){  //一个出，一个进直到stackin的所有元素出栈为止
            stackOut.push(stackIn.pop());
            }
        }      
        return stackOut.pop();
    }
    
    public int peek() {    //peek 操作只是 取第一个元素 和 pop操作有区别
        if(stackOut.isEmpty()){//pop 操作弹出的同时也会删除元素
            while(!stackIn.isEmpty()){
            stackOut.push(stackIn.pop());
            }
        }
        return stackOut.peek();
    }
    
    public boolean empty() {
        return stackIn.isEmpty()&&stackOut.isEmpty();   //两个栈都未空，则队列为空
    }
}

leetcode225

用队列来实现栈 可以用 一个队列 也可以用两个队列来实现

class MyStack {     //两个队列实现栈
    Queue<Integer> queue1;
    Queue<Integer> queue2;
    public MyStack() {
        queue1=new LinkedList<>();
        queue2=new LinkedList<>();
    }
    
    public void push(int x) {    //push 把入栈元素放队列2 ，然后队列1 的元素 也放入队列2 ，然后 1 2 队列 元素交换， 队列2 充当temp作用
        queue2.offer(x);              
        while(!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queuetemp;
        queuetemp=queue1;
        queue1=queue2;
        queue2=queuetemp;
    }
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

class MyStack {    //一个队列实现栈
    Queue<Integer> queue1;
    
    public MyStack() {
        queue1=new LinkedList<>();
        
    }
    
    public void push(int x) {
        queue1.offer(x);            //先把元素放入队列末尾
        Integer size1=queue1.size()-1;    
        
        while(size1>0){
            queue1.offer(queue1.poll());     //元素从队列头部开始依次弹出 放入队列末尾
            size1--;
        }
    }    
    
    public int pop() {
        return queue1.poll();
    }
    
    public int top() {
        return queue1.peek();
    }
    
    public boolean empty() {
        return queue1.isEmpty();
    }
}

LeetCode：20. 有效的括号

思路：利用栈先进后出的特性 消消乐
依次遍历 左括号 ：把他的相反：由括号放入栈中；
当遍历到右括号时 停止入栈 ，开始比较：和栈顶依次比较；如果相同，则删除，遍历完后如果两边有一边或者都还剩，则说明不匹配\

class Solution {
    public boolean isValid(String s) {
        Stack<Character>stack=new Stack<Character>();
        for(char c:s.toCharArray()){
            if(c=='(')stack.push(')');   
            else if(c=='[')stack.push(']');
            else if(c=='{')stack.push('}');   //入栈
            else if(stack.isEmpty()||c!=stack.pop())return false;  //如果是右括号就开始push 判断
        }
        return stack.isEmpty();   //return true；是错误的，如果左括号比又括号多的时候，无法判断；
    }
}

leetcode1047

class Solution {
    public String removeDuplicates(String s) {    //利用栈的特新消消乐
        Stack<Character> stack=new Stack<>();
        for(char c:s.toCharArray()){
            if(stack.isEmpty()){
                stack.push(c);      //第一个元素 入栈
            }else if(stack.peek()==c){   //如果栈顶元素和遍历的元素相等  则pop
                stack.pop();
            }else{                     //
                stack.push(c);
            }

        }
        char[] array1=new char[stack.size()];
        int size1=stack.size();
        while(size1>0){
            array1[size1-1]=stack.pop();   //从末尾赋值
            size1--;
        }
        return new String(array1);
    }
}