Stacks and Queues: Array and Linked List Implementations

1. Stacks and Queues: The Core Principles

At a high level, both stacks and queues are collections of items. What distinguishes them is the rule governing how items are added and removed.

• A Stack follows the LIFO (Last-In, First-Out) principle. The last item you add is the first one you get to take out. Think of a stack of plates: you add a new plate to the top and you also remove a plate from the top.
• A Queue follows the FIFO (First-In, First-Out) principle. The first item you add is the first one you get to take out. This is exactly like a line at a grocery store: the first person in line is the first person to be served.

To get a quick overview of these concepts and their standard operations, you can watch the introductory part of the following video.

2. Implementing a Stack

A stack's primary operations are:

• push(item): Add an item to the top.
• pop(): Remove and return the item from the top.
• top() or peek(): Return the top item without removing it.
• isEmpty(): Check if the stack is empty.
• size(): Return the number of items.

We can build a stack using either an array (or a dynamic list) or a linked list.

2.1. Stack Implementation using an Array (or Python List)

Using a dynamic array, like a Python list, is the most straightforward method. The "top" of the stack corresponds to the end of the list.

• push(item) is implemented with list.append(item).
• pop() is implemented with list.pop().
• top() is implemented by accessing the last element, list[-1].

These operations are all amortized O(1), making this a very efficient approach.

While using Python's built-in list is simple, interviewers might ask you to implement it from scratch using a fixed-size array to test your understanding of the underlying mechanics. This involves manually managing an index or pointer for the top of the stack.

For a deeper look into this lower-level implementation, you can review the array-based stack section from the "take U forward" video, which demonstrates managing the top index explicitly. This is not something you'd typically code in Python but is excellent foundational knowledge.

2.2. Stack Implementation using a Linked List

A singly linked list is also a natural fit for a stack. The "top" of the stack is simply the head of the list.

• push(item): Create a new node and make it the new head, pointing its next to the old head.
• pop(): Store the head's value, update the head to head.next, and return the stored value.
• top(): Return the value of the head node.

All these operations are a true O(1) time complexity because they only involve manipulating the head pointer.

The Codecademy article you just read provided a Python class for this. For another excellent walkthrough, the following video shows a step-by-step Python implementation.

3. Implementing a Queue

A queue's primary operations are:

• enqueue(item): Add an item to the back (rear) of the queue.
• dequeue(): Remove and return the item from the front of the queue.
• front() or peek(): Return the front item without removing it.
• isEmpty(): Check if the queue is empty.
• size(): Return the number of items.

3.1. Queue Implementation using an Array (or Python List)

A naive implementation using a Python list might look like this:

• enqueue(item) uses list.append(item). This is O(1).
• dequeue() uses list.pop(0). This is O(n) because all subsequent elements must be shifted one position to the left.

This inefficiency for dequeue is a critical point to raise in an interview. While simple, it's not performant for large queues. The proper array-based solution is a circular queue, which uses two pointers (front and rear) and allows the queue to wrap around the end of the array.

In Python, the collections.deque object is a highly optimized double-ended queue (which can act as a regular queue) that provides O(1) appends and pops from both ends. It's the standard library's solution to this problem.

3.2. Queue Implementation using a Linked List

A linked list provides a very efficient way to build a queue. To achieve O(1) for both enqueue and dequeue, we need to maintain pointers to both the front (head) and rear (tail) of the list.

• enqueue(item): Add a new node at the rear of the list and update the rear pointer.
• dequeue(): Remove the node from the front of the list and update the front pointer.

4. Summary of Trade-offs

Choosing the right underlying structure is a matter of trade-offs. Here’s a summary that is crucial for interview discussions:

Conclusion

In this lesson, you've gone deep into the mechanics of stacks and queues, learning how to build them from the ground up using both arrays and linked lists. This foundational knowledge is non-negotiable for anyone serious about acing technical interviews.

Key Takeaways:

• Stack (LIFO): Easily implemented with a dynamic array's append/pop or a linked list's add_to_head/remove_from_head. Both are efficient.
• Queue (FIFO): A naive implementation with a list's pop(0) is inefficient (O(n)). The correct implementations use a circular array or a linked list with front and rear pointers to achieve O(1) enqueue and dequeue operations.
• Understand the "Why": Be ready to explain why list.pop(0) is slow and how a linked list or circular array solves this problem. This demonstrates a deeper level of understanding.

Now that you know how to build and analyze these structures, our next lesson will focus on applying them. You will apply stacks to solve classic problems like parentheses matching and expression evaluation, which are common interview questions that directly test your understanding of the LIFO principle.