Thread Safe LIFO Data Structure Implementations – 线程安全的LIFO数据结构实现

最后修改: 2018年 8月 7日

1. Introduction


In this tutorial, we’ll discuss various options for Thread-safe LIFO Data structure implementations.


In the LIFO data structure, elements are inserted and retrieved according to the Last-In-First-Out principle. This means the last inserted element is retrieved first.


In computer science, stack is the term used to refer to such data structure. 


A stack is handy to deal with some interesting problems like expression evaluation, implementing undo operations, etc. Since it can be used in concurrent execution environments, we might need to make it thread-safe. 


2. Understanding Stacks


Basically, a Stack must implement the following methods:


  1. push() – add an element at the top
  2. pop() – fetch and remove the top element
  3. peek() – fetch the element without removing from the underlying container

As discussed before, let’s assume we want a command processing engine.


In this system, undoing executed commands is an important feature.


In general, all the commands are pushed onto the stack and then undo operation can simply be implemented:


  • pop() method to get the last executed command
  • call the undo() method on the popped command object

3. Understanding Thread Safety in Stacks


If a data structure is not thread-safe, when accessed concurrently, it might end up having race conditions.


Race conditions, in a nutshell, occur when the correct execution of code depends on the timing and sequence of threads. This happens mainly if more than one thread shares the data structure and this structure is not designed for this purpose.


Let’s examine a method below from a Java Collection class, ArrayDeque:


public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    // ... other book-keeping operations removed, for simplicity
    head = (h + 1) & (elements.length - 1);
    return result;

To explain the potential race condition in the above code, let us assume two threads executing this code as given in the below sequence:


  • First thread executes the third line: sets the result object with the element at the index ‘head’
  • The second thread executes the third line: sets the result object with the element at the index ‘head’
  • First thread executes the fifth line: resets the index ‘head’ to the next element in the backing array
  • The second thread executes the fifth line: resets the index ‘head’ to the next element in the backing array

Oops! Now, both the executions would return the same result object


To avoid such race conditions, in this case, a thread shouldn’t execute the first line till the other thread finishes resetting the ‘head’ index at the fifth line. In other words, accessing the element at the index ‘head’ and resetting the index ‘head’ should happen atomically for a thread.

为了避免这种竞赛条件,在这种情况下,一个线程不应该执行第一行,直到另一个线程在第五行完成了对 “头 “索引的重设。换句话说,对于一个线程来说,访问索引为 “头 “的元素和重置索引 “头 “应该是原子发生的。

Clearly, in this case, correct execution of code depends on the timing of threads and hence it’s not thread-safe.


4. Thread-safe Stacks Using Locks


In this section, we’ll discuss two possible options for concrete implementations of a thread-safe stack. 


In particular, we’ll cover the Java Stack and a thread-safe decorated ArrayDeque. 


Both use Locks for mutually exclusive access.


4.1. Using the Java Stack


Java Collections has a legacy implementation for thread-safe Stack, based on Vector which is basically a synchronized variant of ArrayList.

Java Collections有一个用于线程安全的Stack的传统实现,基于Vector,基本上是ArrayList的同步变体。

However, the official doc itself suggests considering using ArrayDeque. Hence we won’t get into too much detail.


Although the Java Stack is thread-safe and straight-forward to use, there are major disadvantages with this class:

尽管Java Stack是线程安全的,使用起来也很简单,但这个类有很大的缺点。

  • It doesn’t have support for setting the initial capacity
  • It uses locks for all the operations. This might hurt the performance for single threaded executions.

4.2. Using ArrayDeque


Using the Deque interface is the most convenient approach for LIFO data structures as it provides all the needed stack operations. ArrayDeque is one such concrete implementation.  


Since it’s not using locks for the operations, single-threaded executions would work just fine. But for multi-threaded executions, this is problematic.


However, we can implement a synchronization decorator for ArrayDeque. Though this performs similarly to Java Collection Framework’s Stack class, the important issue of Stack class, lack of initial capacity setting, is solved.

然而,我们可以为ArrayDeque实现一个同步装饰器。尽管这与Java Collection Framework的Stack类的性能相似,但Stack类的重要问题–缺乏初始容量设置–得到了解决。

Let’s have a look at this class:


public class DequeBasedSynchronizedStack<T> {

    // Internal Deque which gets decorated for synchronization.
    private ArrayDeque<T> dequeStore;

    public DequeBasedSynchronizedStack(int initialCapacity) {
        this.dequeStore = new ArrayDeque<>(initialCapacity);

    public DequeBasedSynchronizedStack() {
        dequeStore = new ArrayDeque<>();

    public synchronized T pop() {
        return this.dequeStore.pop();

    public synchronized void push(T element) {

    public synchronized T peek() {
        return this.dequeStore.peek();

    public synchronized int size() {
        return this.dequeStore.size();

Note that our solution does not implement Deque itself for simplicity, as it contains many more methods.


Also, Guava contains SynchronizedDeque which is a production-ready implementation of a decorated ArrayDequeue.


5. Lock-free Thread-safe Stacks


ConcurrentLinkedDeque is a lock-free implementation of Deque interface. This implementation is completely thread-safe as it uses an efficient lock-free algorithm.


Lock-free implementations are immune to the following issues, unlike lock based ones.


  • Priority inversion – This occurs when the low-priority thread holds the lock needed by a high priority thread. This might cause the high-priority thread to block
  • Deadlocks – This occurs when different threads lock the same set of resources in a different order.

On top of that, Lock-free implementations have some features which make them perfect to use in both single and multi-threaded environments.


  • For unshared data structures and for single-threaded access, performance would be at par with ArrayDeque
  • For shared data structures, performance varies according to the number of threads that access it simultaneously.

And in terms of usability, it is no different than ArrayDeque as both implement the Deque interface.


6. Conclusion


In this article, we’ve discussed the stack data structure and its benefits in designing systems like Command processing engine and Expression evaluators.

在这篇文章中,我们已经讨论了stack 数据结构及其在设计命令处理引擎和表达式评估器等系统中的好处。

Also, we have analyzed various stack implementations in the Java collections framework and discussed their performance and thread-safety nuances.


As usual, code examples can be found over on GitHub.