【データ構造】チェーンとキューの練習問題

1.括弧のペアの問題は、まず文字列の中で左括弧であれば、スタックの一番上の要素と一致するかどうかを判断し、直接falseに戻るのではない.はい、引き続き判断します.注意Topが0でないと左括弧が多いと判断したらfalseに戻ります.

1.
class Solution {
    public boolean isValid(String s) {
        int l = s.length();
        int top = 0;
        char[] stack = new char[l];
        for(int i = 0; i < l; i++){
            if(s.charAt(i) == '(' || s.charAt(i) == '{' || s.charAt(i) == '['){
                stack[top++] = s.charAt(i);
            }else if(top == 0){
                return false;
            }else{
                if(stack[top -1] == '(' && s.charAt(i) == ')'
                   || stack[top-1] == '[' && s.charAt(i) == ']'
                   || stack[top-1] == '{' && s.charAt(i) == '}'){
                    top--;
                }else{
                    return false;
                }
            }
        }
        if(top != 0){
            return false;
        }
        return true;
    }
}
2. 
class Solution {
    public boolean isValid(String s) {
        //str -> char[]
        char[] data = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        for (char c : data
             ) {
            //       
            if (c == '{' || c == '[' || c == '('){
                stack.push(c);
            }else{
                if (stack.isEmpty()){
                    return false;
                }
                else if (c == '}'){
                    char temp = stack.peek();
                    if (temp == '{'){
                        stack.pop();
                        //continue;
                    }else{
                        return false;
                    }
                }
                else if(c == ']'){
                    char temp = stack.peek();
                    if (temp == '['){
                        stack.pop();
                       // continue;
                    }else{
                        return false;
                    }
                }
                else if(c == ')'){
                    char temp = stack.peek();
                    if (temp == '('){
                        stack.pop();
                        //continue;
                    }else{
                        return false;
                    }
                }
            }
        }
        if (stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

2.キューでスタックを実現する

class MyStack {
    private Queue<Integer> queueA = new LinkedList<>();
    private Queue<Integer> queueB = new LinkedList<>();
    /** Initialize your data structure here. */
    public MyStack() {
        
    }
	
	//  
    /** Push element x onto stack. */
    public void push(int x) {
        queueA.add(x);
    }
    
	//      
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        if (queueA.isEmpty()){
            int len = queueB.size();
            for (int i = 0;i < len - 1;i++){
                //B                      A 
                queueA.add(queueB.poll());
            }
            //  B                 
            //             
            int result = queueB.poll();
            return result;
        }else{
            int len = queueA.size();
            for (int i = 0;i < len - 1;i++){
                //B                      A 
                queueB.add(queueA.poll());
            }
            //  B                 
            //             
            int result = queueA.poll();
            return result;
        }
    }

	//      
    /** Get the top element. */
    public int top() {
        if (queueA.isEmpty()){
            int len = queueB.size();
            for (int i = 0;i < len - 1;i++){
                //B                      A 
                queueA.add(queueB.poll());
            }
            //  B                 
            //             
            int result = queueB.poll();
            queueA.add(result);
            return result;
        }else{
            int len = queueA.size();
            for (int i = 0;i < len - 1;i++){
                //B                      A 
                queueB.add(queueA.poll());
            }
            //  B                 
            //             
            int result = queueA.poll();
            queueB.add(result);
            return result;
        }
    }

	//      
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queueA.isEmpty() && queueB.isEmpty();
    }
}

3.スタック実現キュー

class MyQueue {
    
    private Stack<Integer> a;
    private Stack<Integer> b;
    
    public MyQueue() {
        a = new Stack<>();
        b = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
         a.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        //  b     ，  b    ，    a        b ，      b  
        if(b.isEmpty()){
            while(!a.isEmpty()){
                b.push(a.pop());
            }
        }
        return b.pop();        
    }
    
    /** Get the front element. */
    public int peek() {
        if(b.isEmpty()){
            while(!a.isEmpty()){
                b.push(a.pop());
            }
        }
        return b.peek(); 
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
         return a.isEmpty() && b.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();
 */

4.一番小さいスタックは一回に二つの要素を挿入します.一番目はこの挿入する要素で、二つ目は現在の最小要素です.

class MinStack {

   /** initialize your data structure here. */
    private Stack<Integer> stack = new Stack<>();
   public MinStack() {

   }
   //-2 0 -3
   //-2 -2 0 -2 -3 -3
   public void push(int x) {
       if (stack.isEmpty()){
           stack.push(x);
           stack.push(x);
       }else{
           int temp = stack.peek();//-2
           stack.push(x);//0
           if (x < temp){
               stack.push(x);
           }else{
               stack.push(temp);
           }
       }
   }

   public void pop() {
       stack.pop();
       stack.pop();
   }
   
   public int top() {
       int temp = stack.pop();
       int result = stack.peek();
       stack.push(temp);
       return result;
   }

   public int getMin() {
       return stack.peek();
   }
}

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