Stack in Data Structures B.Tech/BCA Notes 2025 with Examples and PDF

A stack is a linear data structure that follows the Last In First Out (LIFO) principle, which means that the element inserted last will be removed first. This structure can be visualized like a stack of plates where the last plate placed on top is the first one to be removed. Stacks are widely used in various applications such as expression evaluation, syntax parsing, backtracking algorithms, and memory management. In this chapter of B.Tech Data Structures Notes 2025, we will explore the concept of stacks in detail including operations, implementation, applications, advantages, limitations, and real-world examples. These Unit 2 Notes Data Structures are carefully prepared as part of Engineering Study Material and are available for Free Download PDF format.

The basic operations associated with a stack are push, which adds an element to the top of the stack; pop, which removes the top element; peek or top, which returns the top element without removing it; and isEmpty, which checks whether the stack is empty. A stack can be implemented using arrays or linked lists. When implemented using an array, the size is fixed and thus limits the number of elements that can be stored. This implementation is straightforward but not dynamic. On the other hand, the linked list implementation allows for dynamic memory allocation, where nodes are created at runtime and linked sequentially.

Push Operation involves adding a new element to the top of the stack. In the case of an array, we increment the top index and assign the value. In linked list implementation, we create a new node, point its next to the current top, and then update the top pointer. Pop Operation removes the top element. For an array, we simply decrement the top index, while for a linked list, we move the top pointer to the next node and delete the current top. Peek Operation provides the topmost element without deletion. isEmpty Operation checks if the top pointer is at -1 in the case of an array, or NULL in the case of a linked list. These operations have a time complexity of O(1), making stack operations highly efficient.

Insert diagram here to demonstrate stack push and pop operations using both array and linked list.

Applications of Stack

Stacks are used in numerous areas across computer science and real-world applications. Function Call Management in recursive programming uses a call stack. Expression Evaluation including postfix and prefix notations are solved using stacks. Undo Mechanisms in text editors rely on stacks to keep track of user actions. Backtracking Algorithms in maze-solving or puzzle games store previous states in a stack. Parsing Expressions in compilers and interpreters use stacks for syntax validation. Memory Management leverages stack memory for storing local variables and function calls.

Comparison: Array vs Linked List Implementation of Stack

Feature	Array-Based Stack	Linked List-Based Stack
Memory Allocation	Static	Dynamic
Memory Usage	Can be wasteful	Efficient
Size Limitation	Fixed	Flexible
Ease of Implementation	Easier	Slightly complex
Time Complexity (push/pop)	O(1)	O(1)
Overflow Possibility	Yes	No (until memory is full)

Real-Life Examples of Stack

Undo feature in MS Word or Photoshop.
Web browsers back button.
Reversing a word or string.
Expression evaluation like converting infix to postfix.
Depth First Search (DFS) algorithm in Graph Theory.

Stack Operations Using Array – Example in C

#define MAX 100
int stack[MAX];
int top = -1;

void push(int value) {
  if (top == MAX - 1)
    printf("Stack Overflow\n");
  else
    stack[++top] = value;
}

int pop() {
  if (top == -1)
    printf("Stack Underflow\n");
  else
    return stack[top--];
}

int peek() {
  return stack[top];
}

Stack Operations Using Linked List – Example in C

typedef struct Node {
  int data;
  struct Node* next;
} Node;

Node* top = NULL;

void push(int value) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = value;
  newNode->next = top;
  top = newNode;
}

int pop() {
  if (top == NULL)
    printf("Stack Underflow\n");
  else {
    int temp = top->data;
    Node* del = top;
    top = top->next;
    free(del);
    return temp;
  }
}

int peek() {
  return top->data;
}

Short Answer Questions (2-3 Marks)

Q1: Define stack and its basic operations. A1: A stack is a linear data structure that follows LIFO. Basic operations include push, pop, peek, and isEmpty.

Q2: What is the time complexity of stack operations? A2: The time complexity of push, pop, and peek operations is O(1).

Q3: Mention any two applications of stack. A3: Expression evaluation and function call management are two major applications of stack.

Q4: What is stack overflow? A4: Stack overflow occurs when we try to push an element into a stack that is already full (in array implementation).

Q5: Which data structure is used for backtracking? A5: Stack is used for backtracking algorithms such as maze solving.

Long Answer Questions (5-10 Marks)

Q1: Explain the array and linked list implementation of a stack. A1: Stack can be implemented using both arrays and linked lists. Array implementation uses a fixed-size array with a top pointer. Push increments the top and inserts a value, pop decrements the top. However, it is not dynamic. Linked list implementation uses nodes with data and next pointers. A new node is inserted at the top for push, and top is updated in pop. Linked list allows dynamic memory usage.

Q2: Write a program to reverse a string using a stack. A2: Use stack to push all characters of the string and then pop them to reverse.

void reverse(char *str) {
  int len = strlen(str);
  char stack[len];
  int top = -1;

  for (int i = 0; i < len; i++)
    stack[++top] = str[i];

  for (int i = 0; i < len; i++)
    str[i] = stack[top--];
}

Q3: Explain the role of stack in expression evaluation. A3: Stack is crucial in evaluating postfix expressions. Each operand is pushed onto the stack, and when an operator is encountered, operands are popped, operation is performed, and result is pushed back. This ensures correct order of operations without parentheses.

Q4: Compare stack with queue. A4: Stack uses LIFO; queue uses FIFO. In a stack, the last inserted element is removed first; in a queue, the first inserted is removed first. Stack supports backtracking; queue is used in scheduling. Stack operations are push and pop; queue has enqueue and dequeue.

Chapter Summary

Stack is a linear data structure based on LIFO principle Basic operations: push, pop, peek, isEmpty Implemented using arrays (fixed size) or linked lists (dynamic) Used in function calls, expression evaluation, undo mechanisms, DFS, backtracking Time complexity of major operations is O(1) Stack overflow occurs in fixed-size array implementation when the limit is exceeded Linked list implementation allows flexible size and no overflow until memory is exhausted Array is simple but limited; linked list is dynamic but slightly complex