Implementing Stacks

In this post, we will dive into the implementation details of stacks and explore how they can be implemented using arrays and linked lists. We will discuss the basic operations of stacks and provide coding examples in popular programming languages.

Introduction to Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It is similar to a stack of plates, where the last plate added is the first one to be removed. Stacks have two main operations:

1. Push: Adds an element to the top of the stack.
2. Pop: Removes the top element from the stack.

Stacks can be compared to lists or arrays with limited functionality. However, their simplicity and efficiency make them useful in various scenarios such as parsing expressions, backtracking, and undo functionality.

Implementing Stacks using Arrays

One way to implement a stack is by using an array. The top of the stack is represented by the index of the last element in the array. The implementation steps are as follows:

1. Initialize: Create an empty array to store the elements and initialize the top index value to -1.
2. Push: Increment the top index by 1 and insert the element in the array at that index.
3. Pop: Remove the element at the top index and decrement the top index by 1.
4. Peek: Return the element at the top index without modifying the stack.

The following code snippet demonstrates the implementation of a stack using an array in Python:

class Stack:
    def __init__(self):
        self.stack = []
      
    def push(self, item):
        self.stack.append(item)
      
    def pop(self):
        if not self.is_empty():
            return self.stack.pop()
      
    def peek(self):
        if not self.is_empty():
            return self.stack[-1]
      
    def is_empty(self):
        return len(self.stack) == 0

Implementing Stacks using Linked Lists

Another approach to implementing a stack is by utilizing a linked list. In this implementation, each element in the stack is represented by a node containing the value and a reference to the next node. The operations are similar to the array-based implementation:

1. Initialize: Create an empty linked list.
2. Push: Create a new node and set the next reference to the current top node. Update the top node to the new node.
3. Pop: Remove the top node and update the top node to its next reference.
4. Peek: Return the value of the top node without modifying the stack.

The following code snippet demonstrates the implementation of a stack using a linked list in Java:

class Node {
    int value;
    Node next;
  
    public Node(int value) {
        this.value = value;
    }
}

class Stack {
    Node top;
  
    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
    }
  
    public int pop() {
        if (!isEmpty()) {
            int value = top.value;
            top = top.next;
            return value;
        }
        return -1; // or throw an exception for an empty stack
    }
  
    public int peek() {
        if (!isEmpty()) {
            return top.value;
        }
        return -1; // or throw an exception for an empty stack
    }
  
    public boolean isEmpty() {
        return top == null;
    }
}

Conclusion

In this post, we explored the implementation of stacks using arrays and linked lists. Both approaches have their advantages and can be chosen based on the specific requirements of your application. Stacks are powerful data structures that can be efficiently implemented and utilized in various programming scenarios. In the next post, we will delve into using stacks in algorithms, highlighting their practical applications.