CSView/src/algorithm-mandatory/stark-queue/01.md at main · zijing2333/CSView

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现MyQueue类：

void push(int x) 将元素 x 推到队列的末尾

int pop() 从队列的开头移除并返回元素

int peek() 返回队列开头的元素

boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈操作 —— 也就是只有push to top, peek/pop from top, size, 和 is empty操作是合法的。你所使用的语言也许不支持栈。你可以使用list或者deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

提示：

1 <= x <= 9

最多调用 100 次 push、pop、peek 和 empty

假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

解题思路

两个栈实现队列，经典问题。元素入队全压入第一个栈，出队全从第二个栈中pop。如果第二个栈为空，就把第一个栈中所有元素全压入第二个栈。具体操作如下：

初始化：定义两个栈 x1 和 x2，用 vector<int> 实现。
push 操作：当需要将元素 x 添加到队列尾部时，直接将元素 x 添加到栈 x1 的顶部。
pop 操作：

a. 如果栈 x2 为空，将栈 x1 的元素依次弹出并压入栈 x2。这样可以将队列的头部元素移到栈 x2 的顶部。

b. 弹出栈 x2 的顶部元素并返回。该元素是队列的头部元素。
peek 操作：

a. 如果栈 x2 为空，将栈 x1 的元素依次弹出并压入栈 x2。这样可以将队列的头部元素移到栈 x2 的顶部。

b. 返回栈 x2 的顶部元素。该元素是队列的头部元素。
empty 操作：如果栈 x1 和栈 x2 都为空，则队列为空。返回 true，否则返回 false。

::: code-tabs @tab cpp

class MyQueue {
public:
    /** Initialize your data structure here. */
        vector<int> x1;
        vector<int> x2;
    MyQueue() {
        
    }
    
    /** Push element x to the back of queue. */
    void push(int x) {
        x1.push_back(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    int pop() {
        if(x2.size()==0){
            while(x1.size()!=0) 
            {
                x2.push_back(x1.back());
                x1.pop_back();
            }
        }
        int result=x2.back();
        x2.pop_back();
        return result;       
    }
    
    /** Get the front element. */
    int peek() {
        if(x2.size()==0){
            while(x1.size()!=0) 
            {
                x2.push_back(x1.back());
                x1.pop_back();
            }
        }
        return x2.back();  
    }
    
    /** Returns whether the queue is empty. */
    bool empty() {
        return (x1.size()==0 && x2.size()==0);
    }
};

/**
 * 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();
 * bool param_4 = obj->empty();
 */

@tab java

class MyQueue {
    private Deque<Integer> stack1;
    private Deque<Integer> stack2;

    /** Initialize your data structure here. */
    public MyQueue() {
        stack1 = new ArrayDeque<>();
        stack2 = new ArrayDeque<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        stack1.addLast(x);
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) stack2.addLast(stack1.removeLast());
        }
        return stack2.removeLast();
    }
    
    /** Get the front element. */
    public int peek() {
        if(stack2.isEmpty()) {
            while(!stack1.isEmpty()) stack2.addLast(stack1.removeLast());
        }
        return stack2.getLast();
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return stack1.isEmpty() && stack2.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();
 */

@tab golang

typeMyQueue struct {
	stackPush, stackPop []int
}

func Constructor() MyQueue {
	return MyQueue{make([]int, 0), make([]int, 0)}
}

func (this *MyQueue) pushToPop() {
	if len(this.stackPop)==0 {
		for !(len(this.stackPush)==0) {
			value := this.stackPush[len(this.stackPush)-1]
			this.stackPush = this.stackPush[:len(this.stackPush)-1]
			this.stackPop = append(this.stackPop, value)
		}
	}
}

func (this *MyQueue) Push(x int) {
	this.stackPush = append(this.stackPush, x)
	this.pushToPop()
}

func (this *MyQueue) Pop() int {
	this.pushToPop()
	value := this.stackPop[len(this.stackPop)-1]
	this.stackPop = this.stackPop[:len(this.stackPop)-1]
	return value
}

func (this *MyQueue) Peek() int {
	this.pushToPop()
	return this.stackPop[len(this.stackPop)-1]
}

func (this *MyQueue) Empty() bool {
	this.pushToPop()
	if len(this.stackPop) == 0 {
		return true
	}
	return false
}

:::

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

解题思路：

经典题目了，在 push 操作时，元素被添加到非空队列的尾部，并将另一个队列的元素依次移到非空队列中，以保持栈顶元素始终在非空队列的头部。在进行 pop、top 和 empty 操作时，只需检查和操作非空队列。具体操作如下：

初始化：定义两个队列 q1 和 q2。
push 操作： a. 将元素 x 压入非空队列的尾部。 b. 将另一个队列的全部元素依次出队并压入非空队列的尾部。这样，非空队列的顶部就是栈顶元素。
pop 操作： a. 弹出非空队列的头部元素。该元素是栈顶元素。
top 操作： a. 返回非空队列的头部元素。该元素是栈顶元素。
empty 操作： a. 如果两个队列都为空，则栈为空。返回 true，否则返回 false。

::: code-tabs @tab cpp

class MyStack {
public:
    deque<int> q1, q2;
    MyStack() {
    }
    
    void push(int x) {
        if (q1.empty()) {
            q1.push_back(x);
            while (!q2.empty()) {
                q1.push_back(q2.front());
                q2.pop_front();
            }
        } else {
            q2.push_back(x);
            while (!q1.empty()) {
                q2.push_back(q1.front());
                q1.pop_front();
            }
        }
    }
    
    int pop() {
        int top_element;
        if (!q1.empty()) {
            top_element = q1.front();
            q1.pop_front();
        } else {
            top_element = q2.front();
            q2.pop_front();
        }
        return top_element;
    }
    
    int top() {
        return q1.empty() ? q2.front() : q1.front();
    }
    
    bool empty() {
        return q1.empty() && q2.empty();
    }
};

@tab java

import java.util.LinkedList;

class MyStack {

    private LinkedList<Integer> q1, q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if (q1.isEmpty()) {
            q1.offer(x);
            while (!q2.isEmpty()) {
                q1.offer(q2.poll());
            }
        } else {
            q2.offer(x);
            while (!q1.isEmpty()) {
                q2.offer(q1.poll());
            }
        }
    }

    public int pop() {
        int topElement;
        if (!q1.isEmpty()) {
            topElement = q1.poll();
        } else {
            topElement = q2.poll();
        }
        return topElement;
    }

    public int top() {
        return q1.isEmpty() ? q2.peek() : q1.peek();
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}

@tab golang

import "container/list"

type MyStack struct {
    q1, q2 *list.List
}

func Constructor() MyStack {
    return MyStack{
        q1: list.New(),
        q2: list.New(),
    }
}

func (this *MyStack) Push(x int) {
    if this.q1.Len() == 0 {
        this.q1.PushBack(x)
        for this.q2.Len() > 0 {
            this.q1.PushBack(this.q2.Remove(this.q2.Front()))
        }
    } else {
        this.q2.PushBack(x)
        for this.q1.Len() > 0 {
            this.q2.PushBack(this.q1.Remove(this.q1.Front()))
        }
    }
}

func (this *MyStack) Pop() int {
    var topElement int
    if this.q1.Len() != 0 {
        topElement = this.q1.Remove(this.q1.Front()).(int)
    } else {
        topElement = this.q2.Remove(this.q2.Front()).(int)
    }
    return topElement
}

func (this *MyStack) Top() int {
    if this.q1.Len() != 0 {
        return this.q1.Front().Value.(int)
    }
    return this.q2.Front().Value.(int)
}

func (this *MyStack) Empty() bool {
    return this.q1.Len() == 0 && this.q2.Len() == 0
}

:::

155. 最小栈

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

实现 MinStack 类:

MinStack() 初始化堆栈对象。

void push(int val) 将元素val推入堆栈。

void pop() 删除堆栈顶部的元素。

int top() 获取堆栈顶部的元素。

int getMin() 获取堆栈中的最小元素。

解题思路

用两个栈，一个栈保存当前push进去元素所对应的最小元素，另一个栈就是普通的push pop。
所以push就push两次，一次直接push当前元素，另一次push当前最小元素
pop也pop两次，获取最小元素就是访问保存最小元素栈的栈顶。
具体操作：
1. 初始化：定义两个栈st和st1。st 用作普通栈，st1 用于存储当前栈中的最小元素。
2. push 操作：
  
  a. 将要插入的元素 val 添加到 st 向量的末尾。
  
  b. 如果 st1 非空，则将 val 与 st1 向量末尾的元素进行比较，将较小值添加到 st1 向量的末尾。
  
  c. 如果 st1 为空，则直接将 val 添加到 st1 向量的末尾。
3. pop 操作：分别从 st 和 st1 向量的末尾删除一个元素。
4. top 操作：返回 st 向量末尾的元素。
5. getMin 操作：返回 st1 向量末尾的元素，即当前栈中的最小值。

::: code-tabs @tab cpp

class MinStack {
public:
    vector<int> st;
    vector<int> st1;
    MinStack() {

    }
    
    void push(int val) {
        if(!st1.empty()) {
            st1.emplace_back(min(val, st1.back()));
        }else {
            st1.push_back(val);
        }
        st.emplace_back(val);
    }
    
    void pop() {
        st.pop_back();
        st1.pop_back();
    }
    
    int top() {
        return st.back();
    }
    
    int getMin() {
        return st1.back();
    }
};

@tab java

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> min_stack;
    public MinStack() {
        stack = new Stack<>();
        min_stack = new Stack<>();
    }
    public void push(int x) {
        stack.push(x);
        if(min_stack.isEmpty() || x <= min_stack.peek())
            min_stack.push(x);
    }
    public void pop() {
        if(stack.pop().equals(min_stack.peek()))
            min_stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min_stack.peek();
    }
}

@tab golang

type MinStack struct {
	stackData, stackMin []int
}

func Constructor() MinStack {
	return MinStack{make([]int, 0), make([]int, 0)}
}

func (this *MinStack) Push(val int) {
	this.stackData = append(this.stackData, val)
	if len(this.stackMin)==0 {
		this.stackMin = append(this.stackMin, val)
	} else {
		min := this.GetMin()
		if val <= min {
			this.stackMin = append(this.stackMin, val)
		} else {
			this.stackMin = append(this.stackMin, min)
		}
	}
}

func (this *MinStack) Pop() {
	this.stackData = this.stackData[:len(this.stackData)-1]
	this.stackMin = this.stackMin[:len(this.stackMin)-1]
}

func (this *MinStack) Top() int {
	return this.stackData[len(this.stackData)-1]
}

func (this *MinStack) GetMin() int {
	return this.stackMin[len(this.stackMin)-1]
}

:::

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。

解题思路：

跟括号匹配其实一个思路，只不过这次变成了3种括号，碰到左括号就压栈，碰到右括号就看栈顶左括号匹不匹配，不匹配就g，匹配就把栈顶pop掉。具体操作如下：

初始化一个字符向量（vector）st，用作栈。
遍历字符串 s 中的所有字符：

a. 如果字符为开括号 (、[ 或 {，将其添加到栈 st 的末尾。

b. 如果字符为闭括号 )，检查栈 st 是否为空且栈顶元素为对应的开括号 (。如果是，则从栈中弹出栈顶元素；否则，返回 false。

c. 如果字符为闭括号 ]，检查栈 st 是否为空且栈顶元素为对应的开括号 [。如果是，则从栈中弹出栈顶元素；否则，返回 false。

d. 如果字符为闭括号 }，检查栈 st 是否为空且栈顶元素为对应的开括号 {。如果是，则从栈中弹出栈顶元素；否则，返回 false。
在遍历结束后，检查栈 st 是否为空。如果为空，说明所有括号都正确闭合，返回 true；否则，返回 false。

通过使用栈数据结构，我们可以在遍历过程中有效地跟踪和匹配开括号和闭括号。在遇到闭括号时，我们检查栈顶元素是否与之匹配，如果匹配则弹出栈顶元素，否则返回 false。在遍历结束后，如果栈为空，则说明所有括号都正确闭合。

::: code-tabs @tab cpp

class Solution {
public:
    bool isValid(string s) {
        vector<char> st;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] == '(' || s[i] == '[' || s[i] == '{') {
                st.emplace_back(s[i]);
            }else if(s[i] == ')'){
                if(!st.empty() && st.back() == '(') {
                    st.pop_back();
                }else {
                    return false;
                }
            }else if(s[i] == ']') {
                if(!st.empty() && st.back() == '[') {
                    st.pop_back();
                }else {
                    return false;
                }
            }else if(s[i] == '}') {
                if(!st.empty() && st.back() == '{') {
                    st.pop_back();
                }else {
                    return false;
                }
            }
        }
        return st.size() == 0;
    }
};

@tab java

import java.util.Stack;

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

@tab golang

func isValid(input string) bool {
    st := []rune{}
    for _, c := range input {
        if c == '(' || c == '[' || c == '{' {
            st = append(st, c)
        } else if c == ')' {
            if len(st) != 0 && st[len(st)-1] == '(' {
                st = st[:len(st)-1]
            } else {
                return false
            }
        } else if c == ']' {
            if len(st) != 0 && st[len(st)-1] == '[' {
                st = st[:len(st)-1]
            } else {
                return false
            }
        } else if c == '}' {
            if len(st) != 0 && st[len(st)-1] == '{' {
                st = st[:len(st)-1]
            } else {
                return false
            }
        }
    }
    return len(st) == 0
}

:::

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

232. 用栈实现队列

225. 用队列实现栈

155. 最小栈

20. 有效的括号

FilesExpand file tree

01.md

Latest commit

History

01.md

File metadata and controls

232. 用栈实现队列

225. 用队列实现栈

155. 最小栈

20. 有效的括号