ByteCode, dedicated to share the latest technology original articles, involving Kotlin, Jetpack, translation, system source code, LeetCode/point Offer/multithreading/domestic and foreign large factory algorithm problems and so on a series of articles.

I have unconsciously brushed 210+ questions on LeetCode and submitted a total of 1000+ times. Starting from this article, every article of algorithm type will be animated and implemented by Java and Kotlin. And each topic has its solution idea, time complexity, space complexity and source code. Click on the link below for more information.

  • Job interview with major companies at home and abroad
  • LeetCode: Read online

In this article you will learn the following:

  • The definition of the stack
  • The realization of the stack
    • Why not use the Java stack
      • The performance is low
      • The original data structure is broken
    • It’s not recommended anymore. Why is it still used
    • Why recommendedDequeInterface replacement stack
      • Faster efficiency than Java stacks
      • Block out irrelevant methods
    • Stack and ArrayDeque
    • Time complexity of the stack
  • Stack application: valid parentheses

The definition of the stack

A stack is a last in, first out (LIFO) data structure. The push operation is usually used to insert data into the stack to the bottom, and the pop operation is used to remove data from the top of the stack. The loading and unloading operations are animated as shown below.

The realization of the stack

The most common way to implement a Stack is through a dynamic array. The Stack library Stack is also built into Java and Kotlin, but Stack is no longer recommended.

Why not

  • The performance is low

The poor performance is due to Stack inheriting from Vector, which locks each method, as shown below:

. public synchronized void trimToSize() { } public synchronized void ensureCapacity(int minCapacity) { } public synchronized void setSize(int newSize) { } public synchronized int capacity() { } public synchronized int size() { } public synchronized boolean isEmpty() { } ......Copy the code

Because of the need to be compatible with older projects, it was difficult to optimize from scratch, so Vector was phased out, and ArrayList and CopyOnWriteArrayList were used instead. If ArrayList is not thread-safe, Use CopyOnWriteArrayList for thread-safe situations.

  • The original data structure is broken

A Stack is defined to do push and pop on one side, and should contain no other methods on or off the Stack, but the Stack inherits from Vector, allowing the Stack to use methods common to its parent Vector class, as shown below.

Val stack = stack <Int>() stack.push(6) stack.add(1,10) stack.removeat (1) stack.pop() stack.addall (arrayListOf())......Copy the code

As you can see, you can call addXXX(), removeXXX(), and so on in addition to the push() and pop() methods, but this breaks the stack structure. So there should be no ability to add or remove elements anywhere in a stack’s data structure.

Why are they still in use

But why is Stack still being used by many partners in actual projects? If you swipe LeetCode a lot, you’ll see a lot of people using Stack to do algorithm-based problems. There are two main reasons for this.

  • The JDK is officially not recommendedStackThe reason many people still use it is because the JDK has not been addeddeprecationAnnotations, which are simply stated against use in documentation and comments, are rarely paid attention to implementation details
  • When doing algorithm problems, the focus is on the algorithm logic thinking to solve the problem, not on different languagesStackImplementation details, but developers using the Java language need to pay attention not only to the algorithmic logic itself, but also to its implementation details

Why is the Deque interface recommended for stack replacement

If the JDK doesn’t recommend using Stack, check out the official documentation on which collection classes should be used instead.

As illustrated in the annotation section of the figure, stack-related operations should be provided by the Deque interface, a data structure such as Deque and its subclasses, such as ArrayDeque, are recommended.

val stack: Deque<Int> = ArrayDeque()
Copy the code

What are the benefits of using the Deque interface to implement stack functionality:

  • Faster than Stack

This class may be faster than Stack as a Stack and faster than LinkedList as a queue. Because the original Java Stack inherits from Vector, which adds a lock to each method, the subclass of Deque, ArrayDeque, has no lock overhead.

  • Block out irrelevant methods

The original Java Stack contains methods to add or remove elements anywhere, which are not the way the Stack should be, so it needs to be shielded from these irrelevant methods.

This problem can be solved by declaring a Deque interface, in which the methods used by the stack are declared, regardless of how the class is implemented. For upper users, only the methods related to the stack can be called.

The differences between Stack and ArrayDeque are shown below.

Collection types The data structure Thread safe or not
Stack An array of is
ArrayDeque An array of no

The following describes the common Stack methods.

operation methods
Into the stack push(E item)
Out of the stack pop()
Look at the top Peek () returns null if null

The common methods of ArrayDeque are shown below.

operation methods
Into the stack push(E item)
Out of the stack Returns null if the poll() stack is empty

An exception is thrown when the POP () stack is empty
Look at the top Peek () returns null if null

Time complexity of the stack

The core implementation of stack is realized through dynamic array, so the time complexity is O(n) during expansion, and the time complexity of other operations such as push(E item), POP (), peek(), and so on is O(1).

Stack application: valid parentheses

The solution can be found at github.com/hi-dhl/Leet… . Each problem will be implemented in Java and Kotlin, and each problem will have a solution idea, time complexity, space complexity, and source code,

Topic describes

Given a string containing only ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘, ‘]’, check whether the string is valid

A valid string must meet the following conditions:

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

Note that an empty string can be considered a valid string.

Example 1:
    Input: "()"
    Output: true

Example 2:
    Input: "()[]{}"
    Output: true

Example 3:
    Input: "(]"
    Output: false

Example 4:
    Input: "([)]"
    Output: false

Example 5:
    Input: "{[]}"
    Output: true
Copy the code

Algorithm process

  1. If an open parenthesis is encountered, push the corresponding close parenthesis onto the stack
  2. If you see a close parenthesis
    • Checks whether the current stack is empty
    • If not empty, determine whether the current element is equal to the top element on the stack
    • If it is not equal and a matching parenthesis is found, return ahead of timefalse, end the loop
  3. Repeat Step 1 and Step 2.
  4. At the end of the loop, check for valid parentheses by determining if the stack is empty

Complexity analysis

If the length of the string is N:

  • Time complexity:O(N). Valid parentheses need to traverse the string once, and the time required isO(N).
  • Space complexity:O(N). If the input string is full of open parentheses, for example(((((((, the stack size is the length of the input string, and the required space complexity isO(N)

Kotlin implementation

class Solution { fun isValid(s: String): Boolean {val stack = ArrayDeque<Char>() // Start traversing string for (c in s) {when (c) {// get left parentheses, Press the corresponding right parenthesis into the stack '(' - > stack. Push (')') '[' - > stack. Push ()'] ' '{' - > stack. Push ('}') else - > {/ / right parenthesis, judge whether the current element and stack elements are equal, Not equal to return ahead of schedule, end of cycle if (stack. The isEmpty () | | stack. The poll ()! = c) {return false}}}} // Return stack.isempty ()}}Copy the code

Java implementation

class Solution { public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<Character>(); // start traversing the string for (int I = 0; i < s.length(); i++) { char c = s.charAt(i); / / had left parenthesis, press the corresponding right parenthesis into the stack of the if (c = = '(') {stack. Push (')); } else if (c == '[') { stack.push(']'); } else if (c == '{') { stack.push('}'); } else {/ / right parenthesis, judge whether the current element and stack elements are equal, not equal to return early, the end of the cycle the if (stack. The isEmpty () | | stack. The poll ()! = c) { return false; }}} return stack.isempty (); }}Copy the code

Repository KtKit is a small and useful tool library written in the Kotlin language, containing a series of tools commonly used in the project, is gradually improving.

  • KtKit warehouse address: https://github.com/hi-dhl/KtKit
  • KtKit online: https://ktkit.hi-dhl.com

If this warehouse is helpful to you, please star for me at the upper right corner of the warehouse. Thank you very much for your support, and you are also welcome to submit PR


A “like” would be the biggest encouragement if it helps

More code, more articles


Finally, I recommend the projects and websites I have been updating and maintaining:

  • Personal blog, will all articles classification, welcome to check hi-dhl.com

  • Androidx-jetpack-practice androidX-Jetpack-practice androidX-Jetpack-Practice androidX-Jetpack-Practice AndroidX-Jetpack-Practice

  • LeetCode/multiple thread solution, language Java and Kotlin, including a variety of solutions, problem solving ideas, time complexity, spatial complexity analysis

    • Job interview with major companies at home and abroad
    • LeetCode: Read online

  • Android10 Source code Analysis series of articles, understand the system Source code, not only help to analyze the problem, in the interview process, is also very helpful to us, the warehouse continues to update, welcome to check android10-source-Analysis

  • Collate and translate a series of selected foreign Technical articles, each Article will have a translator’s thinking part, a more in-depth interpretation of the original text, the warehouse continues to update, welcome to visit the Technical-Article-Translation

Must-read articles these days

  • Kotlin code affecting Performance (1)
  • Jetpack Splashscreen parsing | power generation IT migrant workers get twice the result with half the effort
  • Kotlin’s Technique and Analysis (3)
  • Kotlin’s Technique and Principle Analysis that few people know (II)
  • Kotlin’s Technique and Principle Analysis that few people know (1)
  • Uncover the == and === in Kotlin
  • The Kotlin hermetic class evolved
  • The sealed class in Kotlin is superior to the tagged class
  • What is Kotlin Sealed? Why does Google use it all
  • Android 12 behavior changes that affect applications
  • AndroidStudio
  • Kotlin StateFlow search features practice DB + NetWork
  • The end of the Kotlin plugin and the rise of ViewBinding
  • Surprisingly simple, DataBinding and ViewBinding