Brush the route reference:

Github.com/chefyuan/al…

Github.com/youngyangya…

Hi, everyone. I am the third person who urges myself to brush the problem by writing a blog. In this section, we will check the line stack and queue.

Stack and queue basics

Before we start brushing, let’s take a look at some stack and queue basics.

The structure of the stack

A stack is a first-in, last-out sequential table structure.

The stack structure is relatively simple, but not much.

The realization of the stack

Because a stack is a linear table, linear tables support stack operations, and ArrayList and LinkedList can both be used as stacks.

You can create a Stack directly using the Stack class, which inherits an expiration.

Deque<TreeNode> stack = new LinkedList<TreeNode>();// Type is TreeNode
Stack<TreeNode> stack = new Stack<TreeNode>();
Copy the code

The queue structure

A queue is a first-in, first-out data structure

Queue implementation

Queues are also table structures and are more commonly implemented by LinkedList.

  Queue<TreeNode> queue = new LinkedList<TreeNode>();
Copy the code

Ok, the two data structures are also relatively simple, let’s start our brush problem journey!

Brush the topic field

Offer 09. Implement queues with two stacks

☕ Title: Offer 09. Implementing queues with two stacks (leetcode-cn.com/problems/yo…)

❓ Difficulty: Simple

📕 description:

Implement a queue with two stacks. Implement appendTail and deleteHead to insert an integer at the end of the queue and delete an integer at the head of the queue. (If there are no elements in the queue, the deleteHead operation returns -1)

Example 1:

Input:"CQueue"."appendTail"."deleteHead"."deleteHead"[[]], [3],[],[] output: [null.null.3, -1]
Copy the code

Example 2:

Input:"CQueue"."deleteHead"."appendTail"."appendTail"."deleteHead"."deleteHead"[[]], [], [5], [2],[],[] output: [null, -1.null.null.5.2]
Copy the code

💡 ideas:

Stacks are fifo and queues are fifO data structures.

So how do you use stacks to simulate queues?

You need two stacks, one for the headStack and one for the tailStack.

• The tailStack acts as the tail of the queue and simulates enqueuing, pushing an element to the top of the tailStack when it is enqueued.
• HeadStack acts as the head of the queue, simulating the queue exit operation. When an element exits the queue, the element at the top of the headStack pops.
• When there are no elements in the headStack, push all elements in the tailStack into the headStack.

In this way, the queue entry and exit order is simulated with two stacks.

Let’s look at the code implementation:

public class CQueue {

    // Define two stacks
    Deque<Integer> headStack, tailStack;

    public CQueue(a) {
        headStack = new LinkedList<>();
        tailStack = new LinkedList<>();
    }

    / / team
    public void appendTail(int value) {
        // Join the queue and press the value into the tailStack
        tailStack.push(value);
    }

    / / out of the team
    public int deleteHead(a) {
        // If the queue head is empty
        if (headStack.isEmpty()) {
            // All elements in the tailStack are pushed off the stack and into the headStack
            while (!tailStack.isEmpty()) {
                headStack.push(tailStack.pop());
            }
        }
        if (headStack.isEmpty()) {
            return -1;
        }
        returnheadStack.pop(); }}Copy the code

🚗 Time complexity: O(1) when joining the team, O(n) when leaving the team.

🏠 Space complexity: Two stacks are introduced, so the space complexity is O(n).

One more question, LeetCode232. Implementing queues with stacks is basically the same.

LeetCode225. Stack implementation with queues

☕ Title: 225. Implementing stacks with queues (leetcode-cn.com/problems/im…)

❓ Difficulty: Simple

📕 description:

You can implement a last in, first out (LIFO) stack with just two queues and support all four operations of a normal stack (push, top, POP, and Empty).

Implement MyStack class:

• Void push(int x) pushes element x to the top of the stack.
• Int pop() removes and returns the top element of the stack.
• Int top() returns the top element of the stack.
• Boolean empty() Returns true if the stack is empty; Otherwise, return false.

Note:

• You can only use the basic operations of the queue — i.epush to back,peek/pop from front,size 和 is emptyThese operations.
• Your language may not support queues. You can use a list or a deque to simulate a queue, as long as it’s standard queue operations.

Example:

Input:"MyStack"."push"."push"."top"."pop"."empty"[[]], [1], [2[], [], [], [] output: [null.null.null.2.2.false] MyStack MyStack =new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); / / return 2
myStack.pop(); / / return 2
myStack.empty(); / / returns False
Copy the code

💡 ideas:

This one, to tell you the truth, at first glance, I kind of want to be lazy, because if I use a two-way queue:

Doesn’t it just pop, but it says in the problem, standard queue operation, so we’re going to use one-way queues.

So how do we do that?

Very simple, we take advantage of the first in, first out (FIFO) nature of the queue. Each time the queue is simulated, we first remove the element that was queued before the queue, and keep only the last element that was queued.

Then rejoin the queue, which reverses the order of the elements in the queue so that they are in the same order on the stack.

The code implementation is as follows:

public class MyStack {
    // Unidirectional queue
    Queue<Integer> queue;

    /** * Initialize your data structure here. */
    public MyStack(a) {
        queue = new LinkedList<>();
    }

    /** * Push element x onto stack. */
    public void push(int x) {
        // Team elements
        queue.offer(x);
        // Remove the element from the team and rejoin it
        for (int i = 0; i < queue.size() - 1; i++) { queue.offer(queue.poll()); }}/** * Removes the element on top of the stack and returns that element. */
    public int pop(a) {
        return queue.poll();
    }

    /** * Get the top element. */
    public int top(a) {
        return queue.peek();
    }

    /** * Returns whether the stack is empty. */
    public boolean empty(a) {
        returnqueue.isEmpty(); }}Copy the code

🚗 Time complexity: O(n) for loading and O(1) for unloading.

🏠 Space complexity: Queue is introduced, and the space complexity is O(n).

LeetCode20. Valid parentheses

☕ Title: 20. Valid parentheses (leetcode-cn.com/problems/va…)

❓ Difficulty: Simple

📕 description:

Given a only include a ‘(‘,’) ‘, ‘{‘,’} ‘, ‘/’, ‘ ‘the string s, determine whether a string is effective.

A valid string must meet the following requirements:

• An open parenthesis must be closed with a close parenthesis of the same type.
• The left parentheses must be closed in the correct order.

Example 1:

Input: s = "()" output: trueCopy the code

Example 2:

Input: s = "()[]{}" Output: trueCopy the code

Example 3:

Input: s = "(]" Output: falseCopy the code

Example 4:

Input: s = "([)]" Output: falseCopy the code

Example 5:

Input: s = "{[]}" Output: trueCopy the code

Tip:

• 1 <= s.length <= 104
• sOnly by brackets'[] {} ()'composition

💡 ideas:

This is a classic stack application topic.

What’s the idea?

If they match, the element is pushed onto the stack. If they match, the element is pushed off the stack. If they do not match, false is returned.

Note that the stack is empty

    public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        // Iterate over the string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // When an open parenthesis is encountered, push it
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            // The right parenthesis matches
            if (c == ') ') {
                if(stack.isEmpty() || stack.pop() ! ='(') {
                    return false; }}if (c == '] ') {
                if(stack.isEmpty() || stack.pop() ! ='[') {
                    return false; }}if (c == '} ') {
                if(stack.isEmpty() || stack.pop() ! ='{') {
                    return false; }}}return stack.isEmpty();
    }
Copy the code

🚗 Time complexity: O(n).

🏠 Space complexity: O(n).

LeetCode1047. Remove all adjacent duplicates in a string

Given a string S consisting of lowercase letters, the deduplication operation selects two adjacent and identical letters and deletes them.

The deduplication operation is repeated on S until the deletion cannot continue.

Returns the final string after all deduplication operations have been completed. The answer is guaranteed to be unique.

Example:

Input: "abbaca" Output: "ca" Explanation: For example, in "abbaca", we can delete "bb" because the two letters are adjacent and identical, this is the only duplicate item that can be deleted at this time. Then we get the string "aaca", where only "aa" can be deduplicated, so the final string is "ca".Copy the code

💡 ideas:

Is this the same problem as the last one?

Iterates over the character, pushing the top element off the stack if the character matches the top element.

If not, the element is pushed onto the stack.

In this way, all the elements left in the stack are adjacent to each other.

The code is as follows: The last element off the stack needs to be reversed

    public String removeDuplicates(String s) {
        Deque<Character> stack = new LinkedList<>();
        // Iterate over the string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(stack.isEmpty() || stack.peek() ! = c) {/ / into the stack
                stack.push(c);
            } else {
                // The top element goes off the stackstack.pop(); }}// Concatenate stack characters
        StringBuilder str = new StringBuilder();
        while(! stack.isEmpty()) { str.append(stack.pop()); }return str.reverse().toString();
    }
Copy the code

🚗 Time complexity: O(n).

🏠 Space complexity: O(n).

LeetCode150. Inverse Polish expression evaluation

☕ Title: 150. Inverse Polish expression evaluation (leetcode-cn.com/problems/ev…)

❓ Difficulty: medium

📕 description:

Evaluate the expression according to the inverse Polish notation.

Valid operators include +, -, *, and /. Each operand can be an integer or another inverse Polish expression.

Description:

• Integer division preserves only integer parts.

• Given the inverse Polish expression is always valid. In other words, the expression always yields a valid value and never has a divisor of 0.

Example 1:

Input: tokens = [" 2 ", "1", "+", "3", "*"] output: 9: the formula into common infix arithmetic expression is: ((2 + 1) * 3) = 9Copy the code

Example 2:

Input: tokens = "4", "13", "5", "/", "+"] output: 6: this formula into common infix arithmetic expression is: (4 +) = 6 (13/5)Copy the code

Example 3:

Input: tokens = [" 10 ", "6", "9", "3", "+", "11", "*", "/", "*", "17", "+", "5", "+"] output: 22 explanation: this formula into common infix arithmetic expression is: ((10 * (6 / ((9 + 3) * - 11))) + 17) + 5 = ((10 * (6 / (12 * - 11))) + 17) + 5 = ((10 * (6 / - 132)) + 17) + 5 = ((10 * 0) + 17 + 5 = 0 + 17 + 5 = 17 + 5 = 22Copy the code

Inverse Polish expression:

An inverse Polish expression is an expression with a suffix, which means the operator is written after it.

• The usual formula is an infix expression, such as (1 + 2) * (3 + 4).
• The inverse Polish expression of the formula is (1 2 +) (3 4 +) *).

The inverse Polish expression has two main advantages:

• After removing the parentheses, the expression has no ambiguity. Even if the above formula is written as 1, 2 + 3, 4 + *, the correct result can be calculated according to the order.
• Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.

💡 ideas:

See, the answer to this question is:

Suitable for stack operation: the number is pushed into the stack; When encountering an operator, the top two numbers on the stack are calculated and the result is pushed onto the stack.

The code implementation is as follows:

    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (isNumber(s)) {
                stack.push(Integer.parseInt(s));
            } else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                if (s.equals("+")) {
                    stack.push(num1 + num2);
                } else if (s.equals("-")) {
                    stack.push(num2 - num1);
                } else if (s.equals("*")) {
                    stack.push(num1 * num2);
                } else if (s.equals("/")) { stack.push(num2 / num1); }}}return stack.pop();
    }

    boolean isNumber(String token) {
        return! ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }
Copy the code

🚗 Time complexity: O(n).

🏠 Space complexity: O(n).

LeetCode402. Remove K digits

☕ Title: 150. Inverse Polish expression evaluation (leetcode-cn.com/problems/ev…)

❓ Difficulty: medium

📕 description:

Given a non-negative integer num and an integer k represented as a string, remove the k digits from the number to minimize the remaining digits. Please return the smallest number as a string.

Example 1:

Enter num ="1432219", k = 3Output:"1219"Explanation: Remove three numbers4.3, and2Form a new minimum number1219 。
Copy the code

Example 2:

Input: num = "10200", k = 1 Output: "200" Explanation: Remove the first 1 and the remaining number is 200. Note that the output cannot have any leading zeros.Copy the code

Example 3:

Input: num = "10", k = 2 Output: "0" Description: Remove all digits from the original number.Copy the code

💡 ideas:

• If the current stack is not empty and the value of the element at the top of the stack is greater than the value of the element at the top of the stack and the number of elements removed does not reach k, then the element at the top of the stack is removed and the count value is increased by 1.

• If the currently traversed element is larger than the value of the element at the top of the stack, the element is pushed directly.

• If the current iterated element is “0” and the stack is empty, then the loop is skipped.

• If count < k (num = “123456”, k = 3) iterates through the entire string, then the first three elements in the stack are removed in sequence, i.e. “654 “, and the remaining” 321 “is flipped to the minimum value.

• If the current stack is empty (after removing the largest element, all other elements are “0”), simply return “0”.

The code is as follows:

    public String removeKdigits(String num, int k) {
        if (k == num.length()) return "0";
        / / stack
        Deque<Character> stack = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < num.length(); i++) {
            while(! stack.isEmpty() && stack.peek() > num.charAt(i) && count < k) { stack.pop(); count++; }// When the stack is empty and the current bit is 0, we do not need to push it onto the stack
            if (num.charAt(i) == '0' && stack.isEmpty()) continue;
            stack.push(num.charAt(i));
        }
        while(! stack.isEmpty() && count < k) { stack.pop(); count++; }// This is the last stack empty, delete a bit, such as our 10, delete a bit to 0,
        // This logic will return "", so let it return "0"
        if (stack.isEmpty()) return "0";
        StringBuffer sb = new StringBuffer();
        while(! stack.isEmpty()) { sb.append(stack.pop()); }return sb.reverse().toString();
    }

Copy the code

conclusion

Everyone is familiar with the catchy summary of 😂 :

Do simple things repeatedly. Do repetitive things. Do certified things creatively. –

I am three points evil, a full stack of literary and military development.

We’ll see you next time.

---

Reference:

[1]. Github.com/youngyangya…

[2]. Github.com/chefyuan/al…

[3]. Leetcode-cn.com/problems/re…