Definition of stack and its operations · Array implementation of…
Open in the Padhaiko app2.1 Definition of stack and its operations
Stack and LIFO Principle
A stack is a linear data structure in which all insertions and deletions are restricted to a single end called the top. Because the most recently inserted element is always the first to be removed, a stack follows the Last In, First Out (LIFO) principle.
Think of a stack of plates: you place a new plate on top and lift the top plate off first.
+-------+
top --> | D | <-- Push / Pop happen only here
+-------+
| C |
+-------+
| B |
+-------+
| A | <-- Bottom (inserted first, removed last)
+-------+Stack ADT Specification
As an Abstract Data Type (ADT), a stack is defined by a collection of homogeneous elements and five core operations:
| Operation | Behavior | Condition / Error State | Time Complexity |
|---|---|---|---|
push(S, x) | Inserts element x at the top of stack S | Stack Overflow if the stack is full | |
pop(S) | Removes and returns the top element of S | Stack Underflow if the stack is empty | |
peek(S) / top(S) | Returns the top element without removing it | Error if the stack is empty | |
isEmpty(S) | Returns true (1) if S has no elements, else false (0) | Always valid | |
isFull(S) | Returns true (1) if S has reached fixed capacity, else false | Relevant for bounded/array stacks |
- Real-world examples: Web browser Back-button history, Undo/Redo buffers in text editors, and the function call stack during program execution and recursion.
- Core algorithmic applications: Expression conversion (infix to postfix/prefix), expression evaluation, balanced-parenthesis checking, syntax parsing, and backtracking / Depth-First Search (DFS).
2.2 Array implementation of stack ADT
In a static (array-based) implementation, stack elements are stored in a contiguous one-dimensional array items[MAX] alongside an integer index top that tracks the topmost filled slot.
- Initialization: Set
top = -1to represent an empty stack. - Empty condition:
top == -1(isEmpty). - Full condition:
top == MAX - 1(isFull). - Push: Increment
topfirst (top = top + 1), then storeitems[top] = element. - Pop: Read
items[top]first, then decrementtop(top = top - 1).
#include <stdio.h>
#define MAX 100
typedef struct {
int items[MAX];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
int isEmpty(const Stack *s) {
return s->top == -1;
}
int isFull(const Stack *s) {
return s->top == MAX - 1;
}
void push(Stack *s, int element) {
if (isFull(s)) {
printf("Stack Overflow\n");
return;
}
s->items[++(s->top)] = element;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack Underflow\n");
return -1;
}
return s->items[(s->top)--];
}
int peek(const Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return -1;
}
return s->items[s->top];
}
void display(const Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty\n");
return;
}
for (int i = s->top; i >= 0; i--) {
printf("%d\n", s->items[i]);
}
}2.3 Stack applications
One of the classic applications of stacks in compilers and calculators is converting and evaluating arithmetic expressions without ambiguity over operator precedence or parentheses.
| Notation | Operator Position | Parentheses Needed? | Example |
|---|---|---|---|
| Infix | Between operands (A + B) | Yes | (A + B) * (C - D) |
| Prefix (Polish) | Before operands (+ A B) | No | * + A B - C D |
| Postfix (Reverse Polish / RPN) | After operands (A B +) | No | A B + C D - * |
| Precedence Level | Operator(s) | Meaning | Associativity |
|---|---|---|---|
| Highest () | ^ | Exponentiation | Right-to-Left |
| Middle () | *, / | Multiplication, Division | Left-to-Right |
| Lowest () | +, - | Addition, Subtraction | Left-to-Right |
2.3.1 Expression conversion: Infix to postfix and prefix expression
Infix to Postfix Conversion
To convert a valid infix expression to postfix using an operator stack:
- Initialize an empty operator stack and an empty output string
postfix. - Scan the infix expression from left to right:
- Operand: Append directly to
postfix. - Left parenthesis
(: Push onto the operator stack. - Right parenthesis
): Pop operators from the stack and append topostfixuntil(is reached; pop and discard(. - Operator
op: While the stack is non-empty, the top is not(, and the top operator has higher precedence thanop—or equal precedence whenopis left-associative (+,-,*,/)—pop the top operator and append it topostfix. Then pushoponto the stack.
- Operand: Append directly to
- After scanning all symbols, pop all remaining operators from the stack and append them to
postfix.
#include <stdio.h>
#include <ctype.h>
int precedence(char op) {
if (op == '^' || op == '$') return 3;
if (op == '*' || op == '/') return 2;
if (op == '+' || op == '-') return 1;
return 0;
}
int isRightAssociative(char op) {
return (op == '^' || op == '$');
}
void infixToPostfix(const char *infix, char *postfix) {
char opstack[100];
int top = -1, k = 0;
for (int i = 0; infix[i] != '\0'; i++) {
char ch = infix[i];
if (ch == ' ' || ch == '\t') continue;
if (isalnum((unsigned char)ch)) {
postfix[k++] = ch;
} else if (ch == '(') {
opstack[++top] = ch;
} else if (ch == ')') {
while (top >= 0 && opstack[top] != '(') {
postfix[k++] = opstack[top--];
}
if (top >= 0 && opstack[top] == '(') top--;
} else {
while (top >= 0 && opstack[top] != '(' &&
(precedence(opstack[top]) > precedence(ch) ||
(precedence(opstack[top]) == precedence(ch) && !isRightAssociative(ch)))) {
postfix[k++] = opstack[top--];
}
opstack[++top] = ch;
}
}
while (top >= 0) {
postfix[k++] = opstack[top--];
}
postfix[k] = '\0';
}Infix to Prefix Conversion
To convert an infix expression to prefix using the stack-based reversal method:
- Reverse the infix expression string and swap every
(with)(and)with(). - Convert this reversed infix expression to a postfix-like string using an operator stack (with the associativity rule noted below).
- Reverse the resulting string to obtain the final prefix expression.
2.3.2 Expression evaluation: Infix and postfix expression evaluation
Postfix Expression Evaluation
Postfix expressions are evaluated in a single left-to-right pass using an operand stack:
- Initialize an empty operand stack.
- Scan each token of the postfix expression from left to right:
- Operand: Push its numeric value onto the stack.
- Binary operator
op: Pop the top element asop2(right operand), then pop the next element asop1(left operand). Computeresult = op1 op op2and pushresultonto the stack.
- At the end of the expression, the single value remaining on top of the stack is the final answer.
#include <stdio.h>
#include <ctype.h>
#include <math.h>
int evalPostfix(const char *postfix) {
int stack[100], top = -1;
for (int i = 0; postfix[i] != '\0'; i++) {
char ch = postfix[i];
if (ch == ' ') continue;
if (isdigit((unsigned char)ch)) {
stack[++top] = ch - '0';
} else {
int op2 = stack[top--];
int op1 = stack[top--];
switch (ch) {
case '+': stack[++top] = op1 + op2; break;
case '-': stack[++top] = op1 - op2; break;
case '*': stack[++top] = op1 * op2; break;
case '/': stack[++top] = op1 / op2; break;
case '^':
case '$': stack[++top] = (int)pow(op1, op2); break;
}
}
}
return stack[top];
}Direct Infix Expression Evaluation (Two-Stack Method)
An infix expression can be evaluated directly without building an explicit postfix string by maintaining two stacks: a value (operand) stack and an operator stack.
Two-Stack Direct Infix Evaluation Algorithm
Scan tokens from left to right:
- Number (operand): Push onto the value stack.
(: Push onto the operator stack.): While the top of the operator stack is not(, pop one operatorop, popop2thenop1from the value stack, and pushop1 op op2back onto the value stack. Pop and discard(.- Operator
curr: While the operator stack is non-empty, its top is not(, and the top operator has higher precedence (or equal precedence ifcurris left-associative), pop and apply that top operator using the top two values on the value stack. Then pushcurronto the operator stack. - End of input: Apply all remaining operators on the operator stack; the single value left on the value stack is the result.
Worked Examples
1
Trace the state of an array-based stack S with capacity MAX = 3 (initially top = -1) for the sequence of operations: push(10), push(20), pop(), push(30), push(40), push(50), peek(), pop().
Executing each operation sequentially: Track top, the active array slice items[0..top], and any return value or condition:
| Operation | Condition Check | top After | Stack Contents (bottom -> top) | Output / Status |
|---|---|---|---|---|
| Initial | isEmpty = true | -1 | [] | Empty stack |
push(10) | top < 2 (not full) | 0 | [10] | Inserted 10 |
push(20) | top < 2 (not full) | 1 | [10, 20] | Inserted 20 |
pop() | top >= 0 (not empty) | 0 | [10] | Returns 20 |
push(30) | top < 2 (not full) | 1 | [10, 30] | Inserted 30 |
push(40) | top < 2 (not full) | 2 | [10, 30, 40] | Inserted 40 (now full) |
push(50) | top == MAX - 1 | 2 | [10, 30, 40] | Stack Overflow (ignored) |
peek() | top >= 0 | 2 | [10, 30, 40] | Returns 40 (top unchanged) |
pop() | top >= 0 | 1 | [10, 30] | Returns 40 |
After all operations complete, top = 1 and the stack contains [10, 30] (30 at the top). The push(50) call triggers Stack Overflow.
2
Convert the infix expression A + (B * C - (D / E - F) * G) * H to postfix notation, showing the operator stack and postfix output after every symbol.
Scanning left-to-right with precedence (*,/) > (+,-): Apply the infix-to-postfix algorithm, popping equal-or-higher precedence left-associative operators when a new operator arrives and popping back to ( on each ):
| Scanned Symbol | Action Taken | Operator Stack | Postfix Output |
|---|---|---|---|
A | Append operand | (empty) | A |
+ | Push + | + | A |
( | Push ( | +( | A |
B | Append operand | +( | AB |
* | Push * | +(* | AB |
C | Append operand | +(* | ABC |
- | Pop * (higher prec), push - | +(- | ABC* |
( | Push ( | +(-( | ABC* |
D | Append operand | +(-( | ABC*D |
/ | Push / | +(-(/ | ABC*D |
E | Append operand | +(-(/ | ABC*DE |
- | Pop / (higher prec), push - | +(-(- | ABC*DE/ |
F | Append operand | +(-(- | ABC*DE/F |
) | Pop -, discard ( | +(- | ABC*DE/F- |
* | Push * (higher than -) | +(-* | ABC*DE/F- |
G | Append operand | +(-* | ABC*DE/F-G |
) | Pop *, pop -, discard ( | + | ABC*DE/F-G*- |
* | Push * (higher than +) | +* | ABC*DE/F-G*- |
H | Append operand | +* | ABC*DE/F-G*-H |
| End | Pop remaining *, + | (empty) | ABC*DE/F-G*-H*+ |
The equivalent postfix expression is ABC*DE/F-G*-H*+.
3
Convert the infix expression (A + B) * C - (D - E) ^ (F + G) into prefix notation using the stack-based reversal method, where ^ denotes exponentiation.
Reversing the infix expression and swapping parentheses: Original: (A + B) * C - (D - E) ^ (F + G) Reversed with ( and ) swapped: (G + F) ^ (E - D) - C * (B + A)
Converting the reversed expression with the stack:
| Symbol | Operator Stack | Output Buffer |
|---|---|---|
( | ( | |
G | ( | G |
+ | (+ | G |
F | (+ | GF |
) | (empty) | GF+ |
^ | ^ | GF+ |
( | ^( | GF+ |
E | ^( | GF+E |
- | ^(- | GF+E |
D | ^(- | GF+ED |
) | ^ | GF+ED- |
- | - (popped ^) | GF+ED-^ |
C | - | GF+ED-^C |
* | -* | GF+ED-^C |
( | -*( | GF+ED-^C |
B | -*( | GF+ED-^CB |
+ | -*(+ | GF+ED-^CB |
A | -*(+ | GF+ED-^CBA |
) | -* | GF+ED-^CBA+ |
| End | (empty) | GF+ED-^CBA+*- |
Reversing the output buffer: Reversing GF+ED-^CBA+*- character by character produces -*+ABC^-DE+FG.
The equivalent prefix expression is -*+ABC^-DE+FG.
4
Evaluate the postfix expression 6 2 3 + - 3 8 2 / + * 2 ^ 3 + (where ^ is exponentiation) using an operand stack, showing the stack after every token.
Scanning tokens left-to-right and evaluating binary operators (op1 op op2): Remember that the first popped item is op2 (right operand) and the second popped item is op1 (left operand).
| Token | Action | Operand Stack (bottom -> top) |
|---|---|---|
6 | Push 6 | [6] |
2 | Push 2 | [6, 2] |
3 | Push 3 | [6, 2, 3] |
+ | Pop 3, 2; push 2 + 3 = 5 | [6, 5] |
- | Pop 5, 6; push 6 - 5 = 1 | [1] |
3 | Push 3 | [1, 3] |
8 | Push 8 | [1, 3, 8] |
2 | Push 2 | [1, 3, 8, 2] |
/ | Pop 2, 8; push 8 / 2 = 4 | [1, 3, 4] |
+ | Pop 4, 3; push 3 + 4 = 7 | [1, 7] |
* | Pop 7, 1; push 1 * 7 = 7 | [7] |
2 | Push 2 | [7, 2] |
^ | Pop 2, 7; push 7^2 = 49 | [49] |
3 | Push 3 | [49, 3] |
+ | Pop 3, 49; push 49 + 3 = 52 | [52] |
The postfix expression evaluates to .
Exercises
Exercises
Define Stack as an ADT. Explain Stack Overflow and Stack Underflow, and write C functions for push, pop, and isEmpty using an array representation.
Stack ADT definition: A Stack ADT is a LIFO linear collection supporting push(x), pop(), peek(), isEmpty(), and isFull(), where insertions and deletions occur exclusively at one end (top).
Overflow and underflow:
- Stack Overflow: Attempting to
pushonto a fixed-capacity stack that is already full (top == MAX - 1). - Stack Underflow: Attempting to
poporpeekfrom an empty stack (top == -1).
Array-based C functions:
#define MAX 50
typedef struct {
int data[MAX];
int top;
} Stack;
int isEmpty(const Stack *s) { return s->top == -1; }
void push(Stack *s, int x) {
if (s->top == MAX - 1) { printf("Overflow\n"); return; }
s->data[++(s->top)] = x;
}
int pop(Stack *s) {
if (isEmpty(s)) { printf("Underflow\n"); return -1; }
return s->data[(s->top)--];
}A Stack is a LIFO ADT; Overflow occurs on push when top == MAX - 1, and Underflow occurs on pop when top == -1, implemented in per operation using an array and index top.
Convert the infix expression A + B - (C * D / E + F) - G * H into postfix expression showing the operator stack status at each symbol.
Tracing the operator stack left-to-right:
| Symbol | Stack | Postfix Output |
|---|---|---|
A | A | |
+ | + | A |
B | + | AB |
- | - (pop +) | AB+ |
( | -( | AB+ |
C | -( | AB+C |
* | -(* | AB+C |
D | -(* | AB+CD |
/ | -(/ (pop *) | AB+CD* |
E | -(/ | AB+CD*E |
+ | -(+ (pop /) | AB+CD*E/ |
F | -(+ | AB+CD*E/F |
) | - (pop +, discard () | AB+CD*E/F+ |
- | - (pop -) | AB+CD*E/F+- |
G | - | AB+CD*E/F+-G |
* | -* | AB+CD*E/F+-G |
H | -* | AB+CD*E/F+-GH |
| End | (empty) | AB+CD*E/F+-GH*- |
The postfix expression is AB+CD*E/F+-GH*-.
Convert the infix expression A * (B + C) - (D / E) + F into both postfix and prefix expressions, showing the stack trace for each conversion.
Infix to Postfix trace: Scanning A * (B + C) - (D / E) + F left-to-right:
| Symbol | Stack | Postfix Output |
|---|---|---|
A | A | |
* | * | A |
( | *( | A |
B | *( | AB |
+ | *(+ | AB |
C | *(+ | ABC |
) | * | ABC+ |
- | - (pop *) | ABC+* |
( | -( | ABC+* |
D | -( | ABC+*D |
/ | -(/ | ABC+*D |
E | -(/ | ABC+*DE |
) | - (pop /) | ABC+*DE/ |
+ | + (pop -) | ABC+*DE/- |
F | + | ABC+*DE/-F |
| End | (empty) | ABC+*DE/-F+ |
Infix to Prefix trace (reverse, swap parentheses, convert with strict-higher popping for left-assoc ops, then reverse): Reversed with swapped parentheses: F + (E / D) - (C + B) * A.
| Symbol | Stack | Buffer |
|---|---|---|
F | F | |
+ | + | F |
( | +( | F |
E | +( | FE |
/ | +( / | FE |
D | +(/ | FED |
) | + | FED/ |
- | +- (do not pop equal-prec +) | FED/ |
( | +-( | FED/ |
C | +-( | FED/C |
+ | +-(+ | FED/C |
B | +-(+ | FED/CB |
) | +- | FED/CB+ |
* | +-* | FED/CB+ |
A | +-* | FED/CB+A |
| End | (empty) | FED/CB+A*-+ |
Reversing FED/CB+A*-+ gives +-*A+BC/DEF.
- Postfix:
ABC+*DE/-F+ - Prefix:
+-*A+BC/DEF
Evaluate the postfix expression A B + C * D E F G - * + / using an operand stack for .
Substituting values and tracing the operand stack: The numeric postfix expression is 2 3 + 10 * 5 2 4 6 - * + /.
| Token | Operation (op1 op op2) | Operand Stack |
|---|---|---|
2 | Push 2 | [2] |
3 | Push 3 | [2, 3] |
+ | 2 + 3 = 5 | [5] |
10 | Push 10 | [5, 10] |
* | 5 * 10 = 50 | [50] |
5 | Push 5 | [50, 5] |
2 | Push 2 | [50, 5, 2] |
4 | Push 4 | [50, 5, 2, 4] |
6 | Push 6 | [50, 5, 2, 4, 6] |
- | 4 - 6 = -2 | [50, 5, 2, -2] |
* | 2 * (-2) = -4 | [50, 5, -4] |
+ | 5 + (-4) = 1 | [50, 1] |
/ | 50 / 1 = 50 | [50] |
The postfix expression evaluates to .
Evaluate the infix expression 10 + 5 - (4 * 6 / 3 + 8) - 2 * 1 directly using the two-stack infix evaluation algorithm (value stack and operator stack).
Tracing the Value Stack and Operator Stack token-by-token:
| Token | Action | Value Stack | Operator Stack |
|---|---|---|---|
10 | Push value 10 | [10] | |
+ | Push + | [10] | + |
5 | Push value 5 | [10, 5] | + |
- | Pop + (), push - | [15] | - |
( | Push ( | [15] | -( |
4 | Push 4 | [15, 4] | -( |
* | Push * | [15, 4] | -(* |
6 | Push 6 | [15, 4, 6] | -(* |
/ | Pop * (), push / | [15, 24] | -(/ |
3 | Push 3 | [15, 24, 3] | -(/ |
+ | Pop / (), push + | [15, 8] | -(+ |
8 | Push 8 | [15, 8, 8] | -(+ |
) | Pop + (), discard ( | [15, 16] | - |
- | Pop - (), push - | [-1] | - |
2 | Push 2 | [-1, 2] | - |
* | Push * (higher than -) | [-1, 2] | -* |
1 | Push 1 | [-1, 2, 1] | -* |
| End | Pop * (), pop - () | [-3] | (empty) |
The infix expression evaluates directly to .
Trace the evaluation of the postfix expression 4 6 4 + * 8 / using an operand stack.
Scanning tokens left-to-right:
| Token | Action | Operand Stack |
|---|---|---|
4 | Push 4 | [4] |
6 | Push 6 | [4, 6] |
4 | Push 4 | [4, 6, 4] |
+ | Pop 4, 6; push 6 + 4 = 10 | [4, 10] |
* | Pop 10, 4; push 4 * 10 = 40 | [40] |
8 | Push 8 | [40, 8] |
/ | Pop 8, 40; push 40 / 8 = 5 | [5] |
The postfix expression 4 6 4 + * 8 / evaluates to .