Data Structures Part 2: Stack, Queue, and Deque ADTs
In Data Structures Part 1, we focused on Concrete Data Types. We discussed Arrays, Singly Linked Lists, Doubly Linked Lists, and Circular Linked Lists. Please read Part 1 for context before starting with Part 2.
Stack ADT
A Stack is a linear data structure that stores arbitrary objects. Stack operations are performed based on the Last In First Out (LIFO) principle. Data is inserted at the top (last node) and removed at the top (last node) of the stack. A Stack can be implemented using either an Array or a Singly Linked List as the underlying data structure.
History and applications of a Stack
The name “Stack” was derived from the metaphor of a stack of plates in a spring-loaded plate dispenser. A plate dispenser’s operations involve pushing and popping plates on the stack.
The Stack data structure is used by text editors for the undo or redo operations, string reversal, and web browsers for page-visited history. A Stack can also be used indirectly as an auxiliary data structure when writing algorithms or as a component of other data structures.
Operations
A Stack supports the following two main methods:
push(e): Insert element e, to be the top of the stack.
pop(): Removes the topmost element from the stack, or null if the stack is empty.
A Stack supports the following three auxiliary methods:
size(): Returns the number of elements in the stack.
isEmpty: Returns a Boolean value indicating if the stack is empty or not.
top(): Returns the topmost element in the stack or null if the stack is empty.
Performance and memory usage
A Stack can be implemented using either an Array or a Singly Linked List CDTs.
Array-Based: An ArrayStack is easy to implement and efficient. Each operation runs in time O(1). The memory usage is O(n), where n represents the number of elements. The drawbacks of this implementation are the capacity of the stack needs to be set at compile-time and cannot be changed, and if we try to push a new element onto an already full stack it will throw an exception.
Singly Linked List: Singly Linked List Stack aims to solve the problem identified in the ArrayStack implementation. By using a Singly Linked List under the hood, the capacity of the Stack is dynamic. The top of the will be set to the head of the Singly Linked List since we can insert (push(e)) and delete (pop()) in constant time O(1) at the head. For the size() and isEmpty() methods to run in constant time we can keep track of the number of elements in an instance variable. Therefore, a Stack backed by a Singly Linked List is the most efficient implementation since all operations run in O(1) and memory usage is O(n).
Kotlin Implementation
Queue ADT
A Queue is a linear data structure that stores arbitrary objects. Queue operations are performed based on the First In First Out (FIFO) principle. Data is inserted at the tail (last node) and removed at the head (first node) of the queue. A Queue can be implemented using either an Array or a Singly Linked List as the underlying data structure.
History and Applications of a Queue
The name “Queue” is derived from a line of people waiting to purchase a movie ticket at the Movie Theatre. The first customer in the queue will be removed from the front of the queue. New customers will join the queue from the back (rear).
The Queue data structure is used to access shared resources (printer), message queues, and process scheduling. A Queue can also be used indirectly as an auxiliary data structure when writing algorithms or as a component of other data structures.
Operations
A Queue supports the following operations:
enqueue(e): Inserts the element e at the rear of the queue.
dequeue(): Removes and returns the element at the front of the queue, and returns null if the queue is empty.
front(): Returns the element at the front of the queue, and returns null if the queue is empty.
size(): Returns the number of elements in the queue.
isEmpty(): Returns a Boolean value that indicates whether the queue is empty.
Performance and memory usage
A Queue can be implemented using either an Array, Array-List, or a Singly Linked List CDTs.
Array-Based: To avoid the dequeue() operation from taking O(n) time to run, where n represents the number of elements needed to shift forward, we need to define two variables f and r which have the following meaning.
f: refers to the index of the first element in the Queue, which is next to be dequeued unless the Queue is empty (f = r=0). Initially set to 0. When an element is dequeued we need to increment the f index to the next element in the Queue.
r: refers to the index of the next available cell in the Queue. Initially set to 0. When a new element is enqueued we need to increment the r index to the next available cell in the Queue.
By using the f and r variables we are able to implement the front(), enqueue(e), and dequeue() methods in constant time, O(1). This implementation has two drawbacks. The first drawback is that if we repeatedly enqueue and dequeue element N until f =r=N. If were then to enqueue once more, an IndexOutOfBounds error would be thrown. The second drawback is we have to specify the maximum size of the Queue.
The memory usage in a normal Array-Based Queue is O(n), where n represents the number of elements.
Circular Queue (Array-Based): The Circular Queue implementation aims to solve the first problem identified in the normal Array-Based Queue implementation. To implement a Circular Queue the modulo (%) operator is used, to wrap indices around the end of the Array, (f + 1) % N or (r + 1) % N. Each method in a Circular Queue runs in constant time, O(1).
The memory usage in a Circular Queue is O(n), where n represents the number of elements. Since this implementation also uses an Array under the hood, the second drawback identified in the Array-Based implementation still exists here.
Singly Linked List: The Singly Linked List implementation aims to solve the drawbacks identified in the previous two implementations. By using a Singly Linked List under the hood, each Queue operation runs in time O(1) and we don’t have to specify the maximum size of the Queue. This benefit comes at the expense of increasing the amount of space used as new elements are added to the Queue. The memory usage is O(n), where n represents the number of elements.
To implement a Queue using a Singly Linked List we need to maintain references to both head and tail nodes in the list. In this way, we can remove from the head and add new nodes at the tail efficiently.
Deque ADT
A Deque, also known as a double-ended queue, is a data structure that supports insertion and deletion operations at both the front and back of the queue. A Deque is usually pronounced as “deck” to avoid confusion with the dequeue method of a Queue ADT.
History and Applications of a Queue
A Deque can be used to implement a waitlist feature in a Restaurant application. The restaurant usher might remove the first customer from the queue to find that there are no tables available. Thus, the usher will reinsert the customer at the front of the queue. The customer at the end of the queue might feel that the queue is too long and leave the restaurant.
We can also think of its application in a web browser's history, where the most recently visited sites are added to the front of the deque and the sites at the back of the deque are removed after N minutes.
Operations
A Deque supports the following operations:
addFirst(e): Inserts a new element e at the front of the deque.
addLast(e): Inserts a new element e at the back of the deque.
removeFirst(): Removes and returns the first element of the deque. Returns null if the deque is empty.
removeLast(): Removes and returns the last element of the deque. Returns null if the deque is empty.
first(): Returns the first element of the deque. Returns null if the deque is empty.
last(): Returns the last element of the deque. Returns null if the deque is empty.
size(): Returns the number of elements in the deque.
isEmpty(): Returns a boolean value indicating whether or not the deque is empty.
Performance and memory usage
A Deque ADT using a Doubly Linked List under the hood, does not have a predefined size. Thus, the space used by a list with n elements is O(n). All Deque operations run in constant time, O(1).
Kotlin Implementation
Conclusion
In Data Structures Part 3: List Abstractions, we’ll discuss Array-List ADT, Position & Positional List ADT, and Iterators.
References
- Goodrich, M.T., Tamassia, R., 2011. Data structures & algorithms in java, fifth edition. Wiley, Hoboken, N.J
- Goodrich, M.T., Tamassia, R. & Goldwasser M.H., 2015. Data structures & algorithms in java, sixth edition. Wiley, Hoboken, N.J
