栈和队列

[huangchucai]

栈和队列

定义

• 栈： LIFO(Last in first out)
• 队列：FIFO(First in first out)

栈的初始化和基本操作

Java类库:

stack<String> stack = new Stack<>();

基本操作(后进先出）

方法	参数	返回值	时间复杂度
push	Element	Element/void	O(1)
pop	Void	Element	O(1)
peek	Void	Element	O(1)
isEmpty	void	Boolean	O(1)

什么时候使用栈

1. 函数调用
2. 递归
3. 深度优先搜索DFS(Depth-first Search）

题目

1. 用栈实现队列

使用栈实现队列的下列操作: push(x) -- 将一个元素放入队列的尾部。 pop() -- 从队列首部移除元素。 peek() -- 返回队列首部的元素。 empty() -- 返回队列是否为空。

注意: 你只能使用标准的栈操作。 假设所有操作都是有效的 (例如，一个空的队列不会调用 pop 或者 peek 操作)

解答思路（2个栈）

1. 用2个栈的特性来实现队列的特性 -> 新的栈（NS)和旧的栈（OS）
2. 基本操作
   • push: newStack.push() 新栈直接push
   • pop: 如果oldStack为空，就把newStack的元素pop到oldStack中，然后再对oldStack执行pop操作， 如果oldStack不为空，就直接pop
   • peek: 如果oldStack为空，就把newStack的元素pop到oldStack中，然后最对oldStack进行peek操作，如果oldStack不为空，就直接peek
   • empty: oldStack和newStack全部为空的时候

// 代码
package hcc.company.study.StackStudy;

import java.util.Stack;

/*
* 用栈实现队列
*
使用栈实现队列的下列操作:
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
*
*
* */
public class MyQueue {
    private Stack<Integer> firstStack;
    private Stack<Integer> secondStack;

    public MyQueue(Stack<Integer> firstStack, Stack<Integer> secondStack) {
        this.firstStack = new Stack<Integer>();
        this.secondStack = new Stack<Integer>();
    }

    public void push(int x) {
        firstStack.push(x);
    }

    public int pop() {
        shiftStack();
        return secondStack.pop();
    }

    public int peek() {
        shiftStack();
        return secondStack.peek();
    }

    private void shiftStack() {
        if (secondStack.isEmpty()) {
            // 如果第一个栈存在的话
            while (!firstStack.isEmpty()) {
                secondStack.push(firstStack.pop());
            }
        }
    }
    boolean isEmpty() {
        return firstStack.isEmpty() && secondStack.isEmpty();
    }
}

2. 最小栈

设计一个支持 push，pop，top 操作，并能在常量时间内检索 最小元素的栈。

push(x) -- 将元素 x 推入栈中

pop() -- 删除栈顶的元素。 top() -- 获取栈顶元素。 getMin() -- 检索栈中的最小元素。

解答思路（2个栈）

1. 用2个栈来存放数据，stack存放正常的数据，minStack用来存放最小值的记录

2. 基本操作：

   • push：stack执行push方法，把数据存放到栈中，判定如果minStack为空或者minStack最顶部不大于x的话（peek），minStack也需要push（x）的值
   • pop: stack执行pop方法，把数据弹出栈中，判定如果弹出的数据等于minStack的顶部元素，minStack也需要弹出数据
   • top: 执行stack中的peek操作
   • getMin: 执行minStack的peek方法

   // 代码
   package hcc.company.study.StackStudy;
   
   import java.util.Stack;
   
   public class minStack {
       private Stack<Integer> stack;
       private Stack<Integer> minStack;
   
       /**
        * initialize your data structure here.
        */
       public minStack() {
           stack = new Stack<>();
           minStack = new Stack<>();
       }
   
       public void push(int x) {
           if (minStack.isEmpty() || minStack.peek() >= x) {
               minStack.push(x);
           }
           stack.push(x);
       }
   
       public void pop() {
           if (stack.peek().equals(minStack.peek())) {
               minStack.pop();
           }
           stack.pop();
       }
   
       public int top() {
           return stack.peek();
       }
   
       public int getMin() {
           return minStack.peek();
       }
   }
   

3. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

注意:空字符串可被认为是有效字符串

示例 1:输入: "()" 输出: true 示例 2: 输入 : "()[]{}" 输出 : tiue

示例 3:输入: "(]" 输出: false

示例 4:输入:"([)]" 输出:false

示例 5:输入:"{[]}" 输出:true

package hcc.company.study.StackStudy;

import java.util.Stack;

public class isValid {
    public boolean isValid(String s) {
        if(s == null || s == "") {
            return true;
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0; i < s.length(); i++) {
            System.out.println(i);
            char c = s.charAt(i);
            switch(c) {
                case '{':
                case '(':
                case '[':
                    stack.push(c);
                    break;
                case '}':
                    if(stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                case ')':
                    if(stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    break;
                case ']':
                    if(stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
            }
        }
        return stack.isEmpty();
    }
}