What is a Stack?

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Stacks are used in various applications, including expression evaluation, backtracking, and memory management.

Representation of a Stack Data Structure

Here is a visual representation of how a stack works:

Initial State:
|   |  <-- Top
-----
After Pushing Elements (Push 1, Push 2, Push 3):
| 3 |  <-- Top
| 2 |
| 1 |
-----
After Popping an Element (Pop):
| 2 |  <-- Top
| 1 |
-----
After Pushing Another Element (Push 4):
| 4 |  <-- Top
| 2 |
| 1 |
-----

Types of Stacks

1. Static Stack: Implemented using arrays with a fixed size. The size of the stack is determined at the time of creation and cannot be changed.
2. Dynamic Stack: Implemented using linked lists or dynamic arrays, allowing the stack to grow and shrink as needed.

Key Operations on Stacks

1. Push: Adding an element to the top of the stack.
   • Example: Push 5 -> Stack: [5]
2. Pop: Removing the top element from the stack.
   • Example: Pop -> Stack: []
3. Peek/Top: Accessing the top element without removing it.
   • Example: Top -> 5
4. isEmpty: Checking if the stack is empty.
   • Example: isEmpty() -> True if stack is empty, False otherwise

Here are some basic implementations of a stack in C++, Java, and Python.

C++ program to implement Stack

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> stack;

    // Push elements to the stack
    stack.push(1);
    stack.push(2);
    stack.push(3);
    cout << "Stack elements: ";
    stack<int> temp_stack = stack;
    while (!temp_stack.empty()) {
        cout << temp_stack.top() << " ";
        temp_stack.pop();
    }
    cout << endl;

    // Peek the top element
    cout << "Top element: " << stack.top() << endl;

    // Pop an element from the stack
    stack.pop();
    cout << "After popping, stack elements: ";
    temp_stack = stack;
    while (!temp_stack.empty()) {
        cout << temp_stack.top() << " ";
        temp_stack.pop();
    }
    cout << endl;

    // Check if the stack is empty
    cout << "Is stack empty? " << (stack.empty() ? "Yes" : "No") << endl;

    return 0;
}

Java program to implement Stack

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // Push elements to the stack
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("Stack elements: " + stack);

        // Peek the top element
        System.out.println("Top element: " + stack.peek());

        // Pop an element from the stack
        stack.pop();
        System.out.println("After popping, stack elements: " + stack);

        // Check if the stack is empty
        System.out.println("Is stack empty? " + (stack.isEmpty() ? "Yes" : "No"));
    }
}

Python program to implement Stack

class Stack:
    def __init__(self):
        self.elements = []

    def push(self, x):
        self.elements.append(x)

    def pop(self):
        if not self.elements:
            print("Stack is empty!")
            return
        return self.elements.pop()

    def top(self):
        if not self.elements:
            print("Stack is empty!")
            return None
        return self.elements[-1]

    def is_empty(self):
        return len(self.elements) == 0

    def print_stack(self):
        print(" ".join(map(str, reversed(self.elements))))

# Main function
if __name__ == "__main__":
    stack = Stack()
    stack.push(1)
    stack.push(2)
    stack.push(3)
    print("Stack elements:", end=" ")
    stack.print_stack()

    print("Top element:", stack.top())

    stack.pop()
    print("After popping, stack elements:", end=" ")
    stack.print_stack()

    print("Is stack empty?", "Yes" if stack.is_empty() else "No")

Advantages of Stacks

1. Simple to Implement: Stacks have straightforward operations and are easy to implement.
2. Efficient Operations: Push and pop operations are performed in constant time (O(1)).

Disadvantages of Stacks

1. Limited Access: Only the top element can be accessed, which may not be suitable for all applications.
2. Fixed Size: Static stacks have a fixed size, which can be limiting.

When to Use Stacks ?

Stacks are preferred when:

• You need to reverse the order of elements.
• You need to implement recursive algorithms without using the system stack.
• You need to manage function calls and local variables in programming languages.

Practice Problems on Stacks

1. Evaluate Reverse Polish Notation
   • Problem: Given an array of strings representing an expression in Reverse Polish Notation, evaluate the expression.
   • Example: Input: ["2", "1", "+", "3", "*"], Output: 9
2. Valid Parentheses
   • Problem: Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
   • Example: Input: "()[]{}", Output: True
3. Min Stack
   • Problem: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
   • Example: MinStack stack = new MinStack(); stack.push(-2); stack.push(0); stack.push(-3); stack.getMin(); -> Returns -3.
4. Implement Queue using Stacks
   • Problem: Implement a queue using two stacks.
   • Example: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); -> Returns 1; queue.pop(); -> Returns 1; queue.empty(); -> Returns false.
5. Largest Rectangle in Histogram
   • Problem: Given an array of integers representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
   • Example: Input: [2,1,5,6,2,3], Output: 10

Frequently Asked Questions (FAQs) on Stack

Q1: What is the difference between a stack and a queue?

• A: A stack follows the Last In, First Out (LIFO) principle, while a queue follows the First In, First Out (FIFO) principle.

Q2: How is memory managed for stacks?

• A: In most programming languages, stacks are managed by the runtime environment. For dynamic stacks, memory is allocated and deallocated dynamically as elements are pushed and popped.

Q3: Can stacks be implemented using linked lists?

• A: Yes, stacks can be implemented using linked lists, where each node represents an element in the stack.

Q4: What are some common applications of stacks?

• A: Common applications include expression evaluation, backtracking algorithms, syntax parsing, and managing function calls in programming languages.

Q5: How do you check for balanced parentheses using a stack?

• A: Push opening brackets onto the stack, and for each closing bracket, check if it matches the top of the stack. If it matches, pop the stack; otherwise, the parentheses are not balanced.

Q6: How do you implement a stack in a language that doesn't have built-in stack support?

• A: You can implement a stack using arrays or linked lists by providing push, pop, and top operations.

Q7: What is the time complexity of stack operations?

• A: The time complexity for push, pop, and top operations is O(1), as they involve a constant number of operations.