Stacks and Queues: Array and Linked List Implementations

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

A stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle. This means the last element added to the stack will be the first one to be removed. A simple and effective analogy is a stack of plates: you place a new plate on top and you also take a plate from the top. The plate at the bottom of the stack was the first one placed, but it will be the last one you can access.

The core operations of a stack are:

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

The following video from the take U forward channel provides an excellent conceptual overview of both stacks and queues. For now, let's focus on the stack portion.

Now, let's explore how to build a stack.

1.1. Implementing a Stack with an Array

An array is a natural choice for implementing a stack. The main idea is to use an array to store the elements and an integer variable, often called top, to keep track of the index of the topmost element.

• Initialization: We declare an array of a fixed size and initialize top to -1, signifying an empty stack.
• push(x): We first check for "stack overflow" (i.e., if top is already at the last index). If there's space, we increment top and then place the new element at stackArray[top].
• pop(): We first check for "stack underflow" (i.e., if the stack is empty, top == -1). If not empty, we return the element at stackArray[top] and then decrement top.
• top(): We check for underflow. If not empty, we simply return stackArray[top].
• isEmpty(): We return true if top == -1, and false otherwise.

Let's see this implemented.

The main drawback of this approach is its static nature. The size of the stack must be defined beforehand, which can lead to wasted memory or, worse, a stack overflow if the size is underestimated.

1.2. Implementing a Stack with a Linked List

To overcome the fixed-size limitation of arrays, we can use a linked list. This implementation is dynamic, meaning it only uses as much memory as it needs. This should feel familiar from our previous module. The idea is to treat the head of the linked list as the top of the stack.

• Initialization: We create a head (or top) node pointer and initialize it to null.
• push(x): This is equivalent to inserting a new node at the beginning of the linked list. We create a new node, point its next reference to the current head, and then update head to be this new node.
• pop(): This is equivalent to deleting the head of the list. We retrieve the data from the head, update head to head.next, and return the data. We must handle the case where the list is empty.
• top(): We simply return the data stored in the head node, after checking it's not null.

The following video explains this dynamic implementation.

This linked-list approach provides O(1) time complexity for all core operations, just like the array implementation, but with the added benefit of dynamic sizing.

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

A queue is another linear data structure that, in contrast to a stack, follows the First-In, First-Out (FIFO) principle. The first element added to the queue is the first one to be removed. Think of a line at a ticket counter: the first person to get in line is the first person to be served.

The core operations are similar to a stack's but with different behavior:

• enqueue(element) (or push): Adds an element to the back (rear) of the queue.
• dequeue() (or pop): Removes and returns the element from the front of the queue.
• peek() (or front): Returns the front element without removing it.
• isEmpty(): Checks if the queue is empty.
• size(): Returns the number of elements.

Let's return to the introductory video to see the FIFO principle explained.

2.1. Implementing a Queue with a Circular Array

If we implement a queue with a standard array and two pointers, front and rear, we run into a problem. When we dequeue an element, we increment front. Over time, front moves forward, leaving unused, "wasted" space at the beginning of the array. To fix this, we use a circular array.

A circular array allows the pointers to "wrap around" to the beginning when they reach the end of the array. This is elegantly achieved using the modulo operator (%).

• Initialization: We declare an array of fixed size and pointers start and end, and a currSize variable, all initialized to indicate an empty queue (e.g., pointers at -1, size at 0).
• enqueue(x): We check if the queue is full (currSize == maxSize). If not, we calculate the new end index using end = (end + 1) % maxSize, place the element at arr[end], and increment currSize.
• dequeue(): We check if the queue is empty. If not, we retrieve the element from arr[start], calculate the new start index using start = (start + 1) % maxSize, and decrement currSize.

The implementation details, especially handling the edge cases of a completely empty or full queue, are important.

2.2. Implementing a Queue with a Linked List

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

• Initialization: We create front and rear node pointers, both initialized to null.
• enqueue(x): We create a new node. We link the current rear node's next pointer to this new node, and then update rear to point to the new node. If the queue was empty, we must also set front to this new node.
• dequeue(): We retrieve the data from the front node, and then update front to be front.next. If this was the last element, we must also update rear to null.

The following image helps visualize the difference between using a contiguous block of memory (arrays) and non-contiguous memory blocks (linked lists).

Let's watch the final segment of the video for the linked list implementation of a queue.

Conclusion

In this lesson, we established a solid foundation by building stacks and queues from scratch. This theoretical understanding is what separates a good programmer from a great one and is frequently tested in interviews.

Key Takeaways:

• Stack (LIFO): The last element in is the first one out. Implemented with an array and a top pointer, or more dynamically with a linked list by adding/removing at the head.
• Queue (FIFO): The first element in is the first one out. Implemented efficiently with a circular array (using front, rear, and modular arithmetic), or dynamically with a linked list by using front and rear pointers to manage the ends.
• Complexity: For all four implementations (Stack/Queue with Array/Linked List), the core operations (push/pop, enqueue/dequeue) achieve O(1) time complexity. The primary trade-off is between the static, fixed-size nature of arrays and the dynamic, flexible nature of linked lists.

In our next lesson, we will put this knowledge to practical use. We'll transition from implementing these structures ourselves to using Java's powerful, pre-built Stack, Queue, and Deque classes to solve the classic "Valid Parentheses" problem.