Stacks in DSA: Complete Guide to Stack Data Structure

Introduction to Stack Data Structure

A stack is a linear data structure which follows the Last In, First Out (LIFO) principle. The last element added to the stack will be the first one to be removed. Stacks are fundamental in computer science and widely used in compilers, expression evaluation, recursion, browser history, and undo operations.

Why Learn Stacks?

• Simple yet powerful abstract data type
• Basis for more complex structures: stacks of stacks, evaluation frameworks
• Frequently used in technical interviews and competitive programming

Basic Operations

Here are the key operations supported by a stack:

Operation	Description	Time Complexity
push(x)	Insert element x on the top	O(1)
pop()	Remove and return the top element	O(1)
top() / peek()	Look at the top element without removing	O(1)
isEmpty()	Check if stack has zero elements	O(1)
size()	Return number of elements	O(1) or O(n) depending on implementation

Implementing Stack

Using Array (Static Stack)

// C++ example
const int MAX = 1000;
int arr[MAX];
int top = -1;

bool isEmpty() { return top == -1; }
bool isFull() { return top == MAX - 1; }

void push(int x) {
  if (!isFull()) arr[++top] = x;
}

int pop() {
  if (!isEmpty()) return arr[top--];
  return INT_MIN;
}

int peek() {
  if (!isEmpty()) return arr[top];
  return INT_MIN;
}
  

Using Linked List (Dynamic Stack)

// C++ singly-linked list stack
struct Node { int data; Node* next; };

Node* top = nullptr;

bool isEmptyLL() { return top == nullptr; }

void pushLL(int x) {
  Node* newNode = new Node();
  newNode->data = x;
  newNode->next = top;
  top = newNode;
}

int popLL() {
  if (isEmptyLL()) return INT_MIN;
  Node* temp = top;
  int val = temp->data;
  top = top->next;
  delete temp;
  return val;
}

int peekLL() {
  return isEmptyLL() ? INT_MIN : top->data;
}
  

Time & Space Complexity

Stack operations (push, pop, peek) all have O(1) time complexity. Space complexity depends on data structure: using array (O(n) fixed), linked list (O(n) dynamic).

Applications of Stacks

1. Expression evaluation: Convert infix to postfix and evaluate using stack.
2. Recursion: System call stack stores return addresses and local variables.
3. Syntax parsing: Used in compilers and interpreters to validate parentheses, brackets.
4. Backtracking: Maze solving, depth-first search.
5. Undo mechanisms: In editors, last action undone first.
6. Browser navigation: Forward and back.

Example: Balanced Parentheses

Check if an expression has balanced parentheses:

// C# example
bool IsBalanced(string expr) {
  Stack<char> s = new Stack<char>();
  foreach (char c in expr) {
    if (c == '(' || c == '[' || c == '{') s.Push(c);
    else if (c == ')' || c == ']' || c == '}') {
      if (s.Count == 0) return false;
      char top = s.Pop();
      if (!Matches(top, c)) return false;
    }
  }
  return s.Count == 0;
}
  

Stack Interview Questions

Prepare the most common stack-related coding questions:

• Implement a stack using queues
• Evaluate postfix/infix expressions
• Find the largest rectangle in a histogram using stack
• Next Greater Element problem
• Implement browser history using two stacks

Advanced Variants and Extensions

Advanced stack types include:

• Min‑Stack / Max‑Stack: Supports O(1) getMin or getMax operations.
• Two‑stack queue: Implement a queue using two stacks
• Multi‑stack: E.g. keep multiple stacks in a single array.
• Thread‑safe stacks: Lock‑free or synchronized versions in concurrent programming.

Conclusion

Stacks are one of the fundamental building blocks in Data Structures & Algorithms. Learning stack concepts—operations, implementation, time complexity, and applications—is essential for coding interviews and efficient problem solving. Practice implementing stacks in code, solving related problems, and using stacks in real‑world scenarios.

---

© Code To Career