Stack
An Abstract Data Type
Abstract Data Type
A stack is an ADT because it is defined in terms of its operations (push, pop, peek) and usage
(LIFO principle), without concern for how those operations are actually implemented in memory.
A Stack is defined by the principle LIFO (Last In, First Out).
It only allows restricted operations:
Push(x) → Insert element at top
Pop() → Remove element from top
Peek() → View top element
isEmpty() / isFull() → Check status
Notice that the concept of a stack does not depend on whether we use an array or a linked list.
That’s why Stack is an ADT.
Example
• Imagine a stack of plates in the cafeteria:
• You can add a plate (push) only at the top.
• You can remove a plate (pop) only from the top.
• You don’t care if the stack is implemented using array (plates in a
shelf with slots) or linked list (plates connected one after another).
• You only care about what operations are possible.
Implementation of Stack
Stack implementation using Array
#include <stdio.h>
#define MAX 5 // maximum size of stack
int stack[MAX];
int top = -1; // initially empty
// Check if stack is full
int isFull() {
return top == MAX - 1;
}
// Check if stack is empty
int isEmpty() {
return top == -1;
}
// Push operation
void push(int x) {
if (isFull()) {
printf("Stack Overflow\n");
} else {
stack[++top] = x;
printf("%d pushed\n", x);
}
}
// Pop operation
int pop() {
if (isEmpty()) {
printf("Stack Underflow\n");
return -1;
}
return stack[top--];
}
// Peek operation
int peek() {
if (isEmpty()) {
printf("Stack is empty\n");
return -1;
}
return stack[top];
}
// Display elements
void display() {
if (isEmpty()) {
printf("Stack is empty\n");
} else {
printf("Stack: ");
for (int i = top; i >= 0; i--) {
printf("%d ", stack[i]);
}
printf("\n");
}
}
int main() {
push(10);
push(20);
push(30);
display();
printf("Top element = %d\n", peek());
printf("Popped = %d\n", pop());
display();
return 0;
}
Output:
10 pushed
20 pushed
30 pushed
Stack: 30 20 10
Top element = 30
Popped = 30
Stack: 20 10
Stack Implementation using Linked List
#include <stdio.h>
#include <stdlib.h>
// Node structure
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL; // initially empty
// Check if empty
int isEmpty() {
return top == NULL;}
// Push operation
void push(int x) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (!newNode) { // checks whether newNode is null if allocation fails for the newNode
printf("Heap Overflow\n");
return; }
newNode->data = x;
newNode->next = top;
top = newNode;
printf("%d pushed\n", x);
}
// Pop operation
int pop() {
if (isEmpty()) {
printf("Stack Underflow\n");
return -1;
}
int val = top->data;
struct Node* temp = top;
top = top->next;
free(temp);
return val;
}
// Peek operation
int peek() {
if (isEmpty()) {
printf("Stack is empty\n");
return -1;
}
return top->data;
}
// Display elements
void display() {
if (isEmpty()) {
printf("Stack is empty\n");
} else {
struct Node* temp = top;
printf("Stack: ");
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n"); }
}
int main() {
push(10);
push(20);
push(30);
display();
printf("Top element = %d\n", peek());
printf("Popped = %d\n", pop());
display();
return 0;
}
Applications of Stack
• Expression Evaluation & Conversion
1. Prefix Expression (Polish
Notation)
• In prefix, operators come before operands.
Example:
• Infix A+B
• Prefix +AB
Rules:
• Operator is written first, then operands.
• No parentheses are required.
2. Postfix Expression (Reverse
Polish Notation)
• In postfix, operators come after operands.
Example:
• Infix A+B
• Postfix AB+
Rules:
• Operands first, operator later
• No parentheses needed.
Operator precedence (preferences) and
associativity in expressions
Infix to Prefix expression evaluation
Infix to Postfix expression
evaluation