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 recommended
Deque
Interface replacement stack- Faster efficiency than Java stacks
- Block out irrelevant methods
- Stack and ArrayDeque
- Time complexity of the stack
- Why not use the Java 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 recommended
Stack
The reason many people still use it is because the JDK has not been addeddeprecation
Annotations, 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 languages
Stack
Implementation 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
- If an open parenthesis is encountered, push the corresponding close parenthesis onto the stack
- 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 time
false
, end the loop
- Repeat Step 1 and Step 2.
- 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