Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 5

Stack and Queue Implementation: Array vs. Linked-List Trade-offs

Recommended resources

Hello! Welcome to our fifth lesson in the "Data Structures & Algorithmic Analysis" module.

In our last lesson, we contrasted dynamic arrays and linked lists, focusing on their fundamental performance trade-offs regarding memory layout, access speed, and insertion/deletion efficiency. We concluded that the choice between them depends entirely on the problem's access patterns.

Today, we'll build directly on that foundation. We'll explore two new, essential data structures: the stack and the queue. These are not fundamental in the way arrays and linked lists are; instead, they are Abstract Data Types (ADTs). An ADT defines a set of behaviors or rules (like "last one in is the first one out") without specifying how it should be built.

Our goal is to implement both stacks and queues using the structures we already know—arrays and linked lists—and to analyze the trade-offs of each implementation. This exercise is central to developing an "architectural mindset": understanding how to choose the right underlying implementation to meet the requirements of an abstract interface.

1. The Stack: Last-In, First-Out (LIFO)

A stack is a data structure that follows the Last-In, First-Out (LIFO) principle. The last element added to the stack is the first one to be removed. Think of a stack of plates: you add a new plate to the top, and you also take a plate from the top. As a software engineer, you've encountered this principle constantly with the call stack, where functions are "pushed" onto the stack when called and "popped" off when they return.

The core operations of a stack ADT are:

  • push(item): Adds an item to the top of the stack.
  • pop(): Removes and returns the item from the top of the stack.
  • peek() (or top()): Returns the item at the top without removing it.
  • isEmpty(): Checks if the stack is empty.
  • size(): Returns the number of items in the stack.

To solidify these concepts, please start by watching this short introductory segment.

L1. Introduction to Stack and Queue | Implementation using Data Structures

The video 'L1. Introduction to Stack and Queue' by take U forward provides a clear, animated explanation of the stack's LIFO principle and its core operations.

Watch from 00:42 to 05:27. Focus on how the push, pop, and top operations manipulate the collection of elements.

2. Implementing a Stack

Now, let's explore the two primary ways to build a stack.

2.1. Array-Backed Stack

This is the most common implementation. We use a dynamic array (like Python's list or Java's ArrayList) to store the elements. The "top" of the stack is simply the end of the array.

  • push(item): Append the item to the end of the array. This is an O(1) amortized operation.
  • pop(): Remove the item from the end of the array. This is an O(1) operation.
  • peek(): Access the last element of the array by its index. This is O(1).

This approach is simple and highly efficient. For a detailed walkthrough of the implementation logic, including how a simple index can track the top of the stack, please watch the following segment.

L1. Introduction to Stack and Queue | Implementation using Data Structures

This section of the 'take U forward' video demonstrates how to implement a stack from scratch using an array. It covers the logic for each operation and analyzes the time and space complexity.

Watch from 10:57 to 19:35. Pay attention to how an index variable top is used to manage the stack within the array and the reasoning behind the O(1) time complexity for each operation.

2.2. Linked List-Backed Stack

Alternatively, we can use a singly linked list. The "top" of the stack corresponds to the head of the linked list.

Stack using Linked List Implementation
Caption: This diagram illustrates how `push` works in a linked-list-backed stack. A new item ('2') is added by creating a new node, making it the new `head` of the list, and linking it to the old `head` ('9'). This is an `O(1)` operation.
  • push(item): Add the new item as the new head of the list. This is O(1).
  • pop(): Remove the head of the list and make the next node the new head. This is O(1).
  • peek(): Access the data in the head node. This is O(1).

This is also a very efficient implementation. Let's see it in action.

L1. Introduction to Stack and Queue | Implementation using Data Structures

We'll return to the same video to see the linked list implementation of a stack. Notice how operations are mapped to manipulations of the list's head.

Watch from 31:55 to 38:19. Contrast this with the array implementation. Note that there's no need to pre-allocate a fixed size; the structure grows and shrinks one node at a time.

2.3. Trade-off Analysis: Stack Implementations

Both implementations provide O(1) time complexity for all core stack operations. So, which one is better? The decision comes down to the subtle trade-offs we've discussed before.

Aspect Array-Backed Stack (Dynamic Array) Linked List-Backed Stack
Time Complexity O(1) for all operations (amortized for push) O(1) for all operations
Memory Usage Can have wasted space (unused capacity in the array) No wasted space, but has memory overhead for a pointer on every element.
Cache Locality Excellent. Elements are contiguous in memory. Poor. Nodes can be scattered anywhere in memory.
Implementation Often simpler, leveraging built-in dynamic array types. Requires manual node and pointer management.

Conclusion: For stacks, the array-backed implementation is generally preferred in practice. Its superior cache performance can lead to a significant speed advantage in real-world applications, and the simplicity of leveraging built-in list types is a major plus.

3. The Queue: First-In, First-Out (FIFO)

A queue follows the First-In, First-Out (FIFO) principle. The first element added is the first one to be removed. This mirrors real-world queues, like people lining up for a service. In software, queues are fundamental for managing tasks, handling requests in a web server, or processing jobs in order.

The core operations of a queue ADT are:

  • enqueue(item) (or add): Adds an item to the back of the queue.
  • dequeue() (or remove): Removes and returns the item from the front of the queue.
  • peek() (or front()): Returns the item at the front without removing it.

4. Implementing a Queue

Implementing a queue efficiently is more challenging than a stack. Let's see why.

4.1. Array-Backed Queue: The Challenge and the Circular Solution

A naive approach using a dynamic array would be to enqueue by appending to the end (O(1)) and dequeue by removing from the beginning. However, as we know from our previous lessons, removing from the front of an array is an O(N) operation because all subsequent elements must be shifted. This is highly inefficient for a core queue operation.

To solve this, we use a clever technique: the circular array (or ring buffer). We use a fixed-size array and two pointers: front and rear.

  • enqueue adds an element at the rear index and moves the rear pointer forward.
  • dequeue removes an element from the front index and moves the front pointer forward.

When a pointer reaches the end of the array, it wraps around to the beginning. This allows the queue to "move" through the array without ever needing to shift elements, making both enqueue and dequeue O(1) operations.

The details of managing the pointers and wrap-around logic are crucial.

L1. Introduction to Stack and Queue | Implementation using Data Structures

This segment explains the implementation of a queue using a circular array. This is a key algorithmic technique for achieving efficient array-based queues.

Watch from 19:35 to 31:55. Focus on how the start (front) and end (rear) pointers move and wrap around. Understand how this avoids the O(N) shifting problem.

4.2. Linked List-Backed Queue

A linked list provides a more straightforward solution. We maintain pointers to both the head and the tail of the list.

  • enqueue(item): Add the new item to the end of the list by updating the tail. This is O(1).
  • dequeue(): Remove the item from the head of the list. This is O(1).
  • peek(): Access the data in the head node. This is O(1).

This implementation is simple to reason about and naturally dynamic.

L1. Introduction to Stack and Queue | Implementation using Data Structures

Finally, let's see how a queue is implemented with a linked list, using both start (head) and end (tail) pointers for efficiency.

Watch from 38:19 to 45:06. Observe how maintaining a tail pointer is essential for an O(1) enqueue operation.

4.3. Trade-off Analysis: Queue Implementations

Here, the choice is more nuanced than with the stack.

Aspect Circular Array-Backed Queue Linked List-Backed Queue
Time Complexity O(1) for all operations (amortized if resizing is added) O(1) for all operations
Memory Usage Fixed capacity leads to potential waste. No per-element overhead. Perfectly dynamic size, but has pointer overhead per element.
Cache Locality Good. The queue occupies a contiguous block (or two). Poor. Nodes can be scattered anywhere in memory.
Implementation More complex; requires careful pointer arithmetic and wrap-around logic. Simpler and more intuitive pointer manipulation.

Conclusion: The linked list-backed queue is often favored for its implementation simplicity and true dynamic sizing. The circular array is a powerful, high-performance alternative, especially in systems where memory is tightly controlled (like embedded systems) or when maximizing cache hits is critical, but it comes with higher implementation complexity.

Test your understanding!

You are designing a job scheduler for a printer. Print jobs arrive and must be processed in the order they were received. The number of jobs can vary dramatically, from zero during the night to hundreds during peak hours.

Which ADT and implementation would you choose to manage the print jobs, and why? Justify your choice based on the trade-offs we've discussed.

Show answer

  • ADT: A Queue is the correct ADT because the requirement is to process jobs in the order they are received (First-In, First-Out).

  • Implementation: A Linked List-backed Queue is the stronger choice here.

  • Justification:

    1. Dynamic Size: The problem states that the number of jobs varies "dramatically." A linked list naturally grows and shrinks to fit the exact number of jobs, using memory efficiently without needing to pre-allocate a massive buffer for peak times. A circular array would either waste a lot of memory during slow periods or require a complex and potentially costly resizing strategy to handle peaks.
    2. Implementation Simplicity: The logic for a linked list queue is more straightforward than managing a resizing circular buffer.

While the circular array would have better cache performance, the simplicity and memory flexibility of the linked list are more critical given the highly variable workload described.

Conclusion

You have now mastered the concepts and implementations of two cornerstone data structures, the stack and the queue. More importantly, you've analyzed how the choice of an underlying structure (array vs. linked list) impacts their performance and complexity.

Key Takeaways:

  • Stacks (LIFO) and Queues (FIFO) are Abstract Data Types that define behavior.
  • An array-backed stack is simple and highly efficient (O(1)), often making it the preferred implementation.
  • An array-backed queue requires a circular buffer to achieve O(1) performance for both enqueue and dequeue operations.
  • A linked-list-backed queue (with head and tail pointers) offers a simpler, more flexible implementation, also with O(1) performance.
  • The choice of implementation is a classic architectural decision, balancing time complexity, memory usage, cache performance, and implementation difficulty.

Next Steps

Now that you know how to build stacks and queues, the next step is to use them. In our next lesson, we will apply these data structures to solve classic problems that specifically require LIFO and FIFO behavior, such as validating balanced parentheses and performing a level-order traversal of a tree.