代码随想录-栈与队列

目前本内容用Java实现

232.用栈实现队列

用栈实现队列： 在存的时候正常存，出的时候用栈存两边就和队列出的一样了

/**
Java标准库中 ： 
    栈 ：Stack
        push：往栈顶添加元素（存）
        pop：从栈顶移除元素（获取的是最后一个存的东西）
        peek：获取栈顶元素，并不做任何添加删除操作
    队列 ： Quene
        offer:入队 
        poll：出队
        peek：获取队头元素，并不做任何添加删除操作
    用栈实现队列 实现MyQueue.offer 也就是存（存在最后一位）
                实现MyQuene.pop/peek 也就是获取第一个存的东西 
 */
class MyQueue {
 /** Initialize your data structure here. */
    public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }
    
    /** Push element x to the back of queue. */
    // 存就是存
    public void push(int x) {
        stackIn.push(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    // 出的时候比较复杂。输出栈如果为空，就把进栈数据全部导入进来（注意是全部导入），再从出栈弹出数据。
    // 也就是用栈存两遍，出栈顺序就和队列一样了
    // 如果输出栈不为空，则直接从出栈弹出数据就可以了。
    public int pop() {    
        dumpstackIn();
        return stackOut.pop();
    }
    
    /** Get the front element. */
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }

    // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中（存两遍）
    private void dumpstackIn(){

        if (!stackOut.isEmpty()) return; 
        while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
        }
    }
    private Stack<Integer> stackIn;
    private Stack<Integer> stackOut;
}

/**
 * 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();
 */

225.用队列实现栈

class MyStack {
    /**
    Java标准库中 ： 
    栈 ：Stack
        push：往栈顶添加元素（存）
        pop：从栈顶移除元素（获取的是最后一个存的东西）
        peek：获取栈顶元素，并不做任何添加删除操作
    队列 ： Quene
        offer:入队 
        poll：出队
        peek：获取队头元素，并不做任何添加删除操作
    用队列实现栈 MyStack.push 也就是存（存在第一位）
                MyStack.pop/peek 也就是获取最后一个存的东西 
 */
 /**
     队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的顺序。
    所以用栈实现队列， 和用队列实现栈的思路还是不一样的，这取决于这两个数据结构的性质。
    但是依然还是要用两个队列来模拟栈，只不过没有输入和输出的关系，而是另一个队列完全用来备份的！
    用两个队列que1和que2实现队列的功能，que2其实完全就是一个备份的作用，把que1最后面的元素以外的元素都备份到que2，然后弹出最后面的元素，再把其他元素从que2导回que1。
  */
    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }
   /** Push element x onto stack. */
    public void push(int x) {
        queue2.offer(x); // 先放在辅助队列中
        while (!queue1.isEmpty()){
            queue2.offer(queue1.poll());
        }
        Queue<Integer> queueTemp;
        queueTemp = queue1;
        queue1 = queue2;
        queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可
    }
    
    /** Get the top element. */
    public int top() {
        return queue1.peek();
    }
        /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue1.isEmpty();
    }
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;
}

/**
 * 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();
 */

20.有效的括号、

匹配问题

碰到左括号就入栈同类型的右括号，
碰到右括号就出栈并对比（还有判空）

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //最后判断栈中元素是否匹配
        return deque.isEmpty();
    }
}

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

可以用双指针和栈两种方法完成

• 双指针

  class Solution {
      public String removeDuplicates(String s) {
          // 先把字符串
          char[] ch = s.toCharArray();
          int fast = 0 ;
          int slow = 0 ;
          while(fast < ch.length){
              // 直接用fast指针覆盖slow指针的值
              // slow 从0开始
              ch[slow] = ch[fast];
              // 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
              if(slow > 0 && ch[slow] == ch[slow - 1]){
                  // 比如ch[3]和ch[4]相等，那么ch[3]和ch[4]都删
                  // slow -- 下次就是直接从ch[2]开始
                  slow --;
              }else{
                  slow ++;
              }
              fast ++;
          }
          return new String(ch,0,slow);
      }
  }

• 栈

  class Solution {
      public String removeDuplicates(String S) {
          Deque<Character> deque = new LinkedList<>();
          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;
      }
  }

150.逆波兰表达式求值

栈的最后一支舞

// 用栈来写
// 首先，遍历字符串，挨个将数字入栈
// 当遍历到 + - * /时，就对上次入栈的两个数字出栈，进行（+ - * /）操作，操作完再将结果入栈

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for (String s : tokens) {
            if ("+".equals(s)) {        // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
                stack.push(stack.pop() + stack.pop());      // 注意 - 和/ 需要特殊处理
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}