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.

This article from the stack – v – a deque the thinking of the article, is also to my previous article | algorithm animation diagrams are “abandoned” the Java stack, why still use the content of the supplement.

In this article you will learn the following:

  • Why not use the Java stack
  • JDK recommended useArrayDequeInstead ofStackIs that really reasonable?
  • How to implement a true stack

Before we begin, let’s briefly review the content of the last article.

Why not use the Java 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 stack is a great data structure, but the implementation of the Java stack has the following problems, so the JDK does not recommend using the Java stack.

  • 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

Vector was made obsolete because it needed to be compatible with older projects, so ArrayList and CopyOnWriteArrayList were used instead, and for thread-safe purposes CopyOnWriteArrayList was used. Otherwise, ArrayList can be used for non-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.

The JDK recommends using ArrayDeque instead of Stack

In JDK documentation, Stack operations should be provided by the Deque interface, and a subclass of Deque, ArrayDeque, is recommended instead of Stack. As shown in the annotation part of the figure below.

Using the Deque interface to implement stack functionality has the following benefits:

  • Faster thanStack 快

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.

Using ArrayDeque instead of Stack is not recommended

Since there are so many benefits to using the Deque interface to implement stacks, why not recommend ArrayDeque instead of Stack? Baddotrobot.com/blog/2013/0…

Because an interface Deque is a linear data structure with a two-ended queue, that is, it can be inserted and deleted at both ends. The stack can only do insert and delete at one end.

The definition of a stack is to perform push and pop operations on one side. There should be no other methods of pushing and removing the stack, but the stack can also operate on the other side based on the Deque interface, as shown below.

val stack: Deque<Int> = ArrayDeque() stack.push(1) stack.poll() // Throws an exception when stack is empty stack.peek() // Returns null stack.offerlast (2) stack.pollLast() stack.peekLast()Copy the code

As shown above, you can also call offerLast(), pollLast(), peekLast(), and so on to insert data to the other end of the queue.

If you’re doing an algorithm problem, you can either use ArrayDeque or Stack, because the focus is different, and when you’re doing an algorithm problem, the focus is on the logic of the algorithm to solve the problem. But using Stack directly is not recommended for large projects, nor is using ArrayDeque instead of Stack. We can encapsulate a real stack based on ArrayDeque, allowing only insertion and deletion at one end, as shown below.

interface Stack<E> {
    fun push(e: E)
    fun pop(): E?
    fun peek(): E?
    fun size(): Int
    fun empty(): Boolean
}

class ArrayStack<E> : Stack<E> {

    private val deque = ArrayDeque<E>()

    override fun push(e: E) = deque.push(e)

    override fun pop(): E? = deque.poll()

    override fun peek(): E? = deque.peek()

    override fun size() = deque.size

    override fun empty(): Boolean = deque.isEmpty()

}
Copy the code

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

More code, more articles

Welcome to our official account: ByteCode for the latest technical 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

  • For more Kotlin and Jetpack projects, check out Github

  • 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

Must-read articles these days

  • | algorithm animation diagrams are “abandoned” Java stack, why still use
  • 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