Stack data structure::
The stack is a linear data structure that follows the Last-In, First-Out (LIFO) principle, where elements are added and
removed from only one end, called the "top". Stack is also known as restricted data structure because insertion and
deletion operations can be performed at only one end.
Implementing Stacks: Array vs. Linked List
Arrays and linked lists are the two common approaches while implementing a stack. Each has its strengths and
limitations, making them suitable for different scenarios.
1. Array-based implementation
Array implementation uses contiguous memory locations, where each element is stored side-by-side.
Imagine you are organizing books on a small shelf with a fixed number of slots. Each slot represents an index in an
array. You can quickly add or remove books from the end, but if the shelf is full, there is no room for more unless you
replace the entire shelf.
Advantages
Fast indexing: Direct access to elements using their index.
Predictable layout: Memory allocation is straightforward and consistent.
Limitations
Fixed size: You risk overflow if the stack exceeds the pre-defined size.
Inflexibility: Resizing the stack requires creating a new array, which can be computationally expensive.
Linked list-based implementation
In a linked list implementation, we represent the stack as a series of nodes. Each node contains the data and a pointer
to the next node.
Imagine you are stacking plates at a buffet, but there is no fixed shelf. Instead, each plate rests on another. You can
dynamically add or remove plates without worrying about a fixed limit.
Advantages
Dynamic resizing: There is no predetermined size; the stack grows and shrinks as needed.
Efficient memory usage: Memory is allocated only when needed, avoiding wastage of space.
Limitations
Pointer overhead: Each node requires extra memory for the pointer, making it less space-efficient.
Slightly slower operations: Manipulating pointers adds a small performance cost compared to arrays.
Key Properties of a Stack
LIFO (Last-In, First-Out): The fundamental principle of a stack, meaning the last element added is the first to be
removed.
Single Access Point: All operations (insertion and deletion) occur only at the "top" of the stack.
Linear Structure: Elements are arranged in a sequential, ordered manner.
Abstract Data Type (ADT): A stack is an ADT, meaning its behavior is defined by its operations, independent of its
implementation (which can be done using arrays or linked lists).
Fixed or Dynamic Size: Stacks can have a predefined maximum capacity (fixed size using arrays) or can grow and
shrink as needed (dynamic size using linked lists).
Error Conditions: Trying to push an element onto a full stack results in a stack overflow, while trying to pop from an
empty stack causes a stack underflow
Operations defined on Stack(Common Functions)
1. Push( ): Inserting an element is defined as Push( ) operation in stack.
2. Pop( ): This operation deletes elements from the stack.
3. IsEmpty( ): It checks whether the stack is empty or not. It returns either true or false.
4. IsFull( ): It checks whether the stack is full or not. IsFull( ) is checked only during actual implementation.
5. peek( ): This operation gives the value of the top data element of the stack without removing [Link] referred as peep
operation
Stack Implementation using arrays ::
#include <stdio.h>
#define MAX 5 // stack size
int stack[MAX];
int top = -1;
// Check if stack is full
int isFull() {
if (top == MAX - 1)
return 1;
else
return 0;
}
// Check if stack is empty
int isEmpty() {
if (top == -1)
return 1;
else
return 0;
}
// Push operation
void push(int value) {
if (isFull())
printf("Stack Overflow\n");
else {
top++;
stack[top] = value;
printf("%d pushed into stack\n", value);
}
}
// Pop operation
void pop() {
if (isEmpty())
printf("Stack Underflow\n");
else {
printf("%d popped from stack\n", stack[top]);
top--;
}
}
// Peek operation
void peek() {
if (isEmpty())
printf("Stack is Empty\n");
else
printf("Top element is %d\n", stack[top]);
}
// Display stack elements
void display() {
if (isEmpty())
printf("Stack is Empty\n");
else {
printf("Stack elements are:\n");
for (int i = top; i >= 0; i--)
printf("%d\n", stack[i]);
}
}
int main() {
int choice, value;
while (1) {
printf("\n--- Stack Operations ---\n");
printf("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
return 0;
default:
printf("Invalid choice\n");
}
}
return 0;
}
Stack implementation using arrays is best used when the size of the stack is fixed or known in advance. Arrays are
preferred when high performance is needed because they provide faster access due to contiguous memory. They are
also useful in systems where dynamic memory allocation is not allowed, such as embedded systems. However, array-
based stacks should be avoided when the size is unpredictable, as they can lead to stack overflow.
What approach is suitable then::
Linked List implementation
It allows dynamic size- stack can grow/shrink as needed, It avoids stack overflow (no fixed size limitation like arrays),
Memory is used efficiently (only allocated when needed), suitable when the number of elements is unknown or very
large,Insertion and deletion (push/pop) are always O(1).
Stack Implementation using linked List ::
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Node* top = NULL;
int isEmpty() {
return (top == NULL);
}
void push(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Stack Overflow\n");
return;
}
newNode->data = value;
newNode->next = top;
top = newNode;
printf("%d pushed into stack\n", value);
}
void pop() {
if (isEmpty()) {
printf("Stack Underflow\n");
return;
}
struct Node* temp = top;
printf("%d popped from stack\n", temp->data);
top = top->next;
free(temp);
}
void peek() {
if (isEmpty())
printf("Stack is Empty\n");
else
printf("Top element is %d\n", top->data);
}
void display() {
if (isEmpty()) {
printf("Stack is Empty\n");
return;
}
struct Node* temp = top;
printf("Stack elements are:\n");
while (temp != NULL) {
printf("%d\n", temp->data);
temp = temp->next;
}
}
int main() {
int choice, value;
while (1) {
printf("\n--- Stack using Linked List ---\n");
printf("1. Push\n2. Pop\n3. Peek\n4. Display\n5. Exit\n");
printf("Enter choice: ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value: ");
scanf("%d", &value);
push(value);
break;
case 2:
pop();
break;
case 3:
peek();
break;
case 4:
display();
break;
case 5:
return 0;
default:
printf("Invalid choice\n");
}
}
}
Applications of Stack (irrespective of its implementation using array or linked list)
1. Expression evaluation and conversion:Used to convert infix expressions to postfix/prefix and evaluate them.
2. Parenthesis and syntax checking: Ensures symbols like (), {}, [] are balanced in programs.
3. Function calls and recursion handling:Uses a call stack to store function execution states.
4. Undo and redo operations:Tracks user actions in applications like text editors.
5. Backtracking algorithms:Used in problems like maze solving, DFS traversal, and puzzles.
6. Reversing data:Helps reverse strings, numbers, or sequences.
Stack Application::
I) Recursion : Refer separate material provided
II) Expression evaluation and conversion in data structures typically use the stack data structure to manage operator
precedence and associativity, enabling computers to process arithmetic and logical expressions efficiently.
Expression Notations
Expressions can be represented in three main notations:
Infix Notation: The standard human-readable format, with operators placed between operands (e.g., A + B). It is
complex for computers to evaluate directly due to precedence and parentheses rules.
Postfix Notation (Reverse Polish Notation): Operators are placed after their operands (e.g., A B +). This notation
simplifies evaluation using a stack as it eliminates the need for parentheses and explicit precedence rules.
Prefix Notation (Polish Notation): Operators are placed before their operands (e.g., + A B). Like postfix, it can be
evaluated efficiently with a stack.
The primary methods involve converting expressions from infix to postfix (or prefix) notation and then evaluating the
converted expression. When we choose infix notataion it is more natural and easier to read and understand for
humans,widely used and supported by most programming languages and calculators but to evaluate requires
paranthesis to specify the order of operations making it difficult to parse and evaluate [Link] use postfix or
prefix which eliminates the need for parentheses,easier to read and understand for humans and Computers evaluate
postfix and prefix expressions more efficiently than infix because they do not need to scan back and forth to handle
operator precedence or parse parentheses.
Manual conversion (using precedence and associativity)
1. Infix A+B*C
* has higher precedence than +
2. Infix A+B*C-D
* first, then + and - (left to right)
3. Infix: (A + B) * (C - D) / E
Brackets →Multiplication →Division
4. Infix: A + B * (C - D) / E ^ F
H/W Solve them: i)A / B ^ C - (D * E - A * C) ii)A + B * (C ^ D - E) ^ (F + G * H) - I
5. Postfix expression: A B + C D - * E /
Final Infix:: ((A + B) * (C - D)) / E
NOTE** we scan left to right, but evaluation happens only when an operator is encountered using the last two
operands.
6. *-A/BC-/AKL (Evaluate Right →Left)
Final Infix :: (A - (B / C)) * ((A /K)- L)
Convert Infix expression to Postfix expression using Stack
In infix expressions, the operator precedence is implicit unless we use parentheses. Therefore, we must define the
operator precedence inside the algorithm for the infix to postfix conversion.
The order of precedence you can check out C Operator Precedence.
Points to consider:
The order of the numbers or operands remains unchanged. But the order of the operators gets changed in the
conversion.
Stacks are used for converting an infix expression to a postfix expression. The stack that we use in the algorithm
will change the order of operators from infix to Postfix.
Postfix expressions do not contain parentheses.
Algorithm:
Create a stack.
For each character c in the input stream:
if c is an operand
{
Output c
}
else if c is a right parentheses
{
Pop and output tokens until a left parentheses is popped
}
else
{ // c is an operator or left parentheses
Pop and output tokens until one of the lower priorities than c are encountered, or a left parentheses is
encountered, or the stack is empty.
Push c
}
Pop and output tokens until the stack is empty.
For a better understanding, let’s trace out an example: A * B- (C + D) + E
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Push
void push(char x) {
stack[++top] = x;
}
// Pop
char pop() {
if (top == -1)
return -1;
return stack[top--];
}
// Peek
char peek() {
if (top == -1)
return -1;
return stack[top];
}
// Check operator
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' ||
c == '%' || c == '^' || c == '<' || c == '>' || c == '=');
}
// Precedence
int precedence(char c) {
switch(c) {
case '^': return 4;
case '*':
case '/':
case '%': return 3;
case '+':
case '-': return 2;
case '<':
case '>': return 1;
case '=': return 0;
default: return -1;
}
}
// Associativity (Right = 1, Left = 0)
int isRightAssociative(char c) {
if (c == '^')
return 1;
return 0;
}
int main() {
char exp[MAX];
int i = 0;
printf("Enter infix expression: ");
scanf("%s", exp);
while (exp[i] != '\0') {
// Operand
if (isalnum(exp[i])) {
printf("%c", exp[i]);
}
// Left Parenthesis
else if (exp[i] == '(') {
push(exp[i]);
}
// Right Parenthesis
else if (exp[i] == ')') {
while (peek() != '(') {
printf("%c", pop());
}
pop(); // remove '('
}
// Operator
else if (isOperator(exp[i])) {
while (top != -1 &&
((precedence(peek()) > precedence(exp[i])) ||
(precedence(peek()) == precedence(exp[i]) &&
!isRightAssociative(exp[i])))) {
printf("%c", pop());
}
push(exp[i]);
}
i++;
}
// Pop remaining operators
while (top != -1) {
printf("%c", pop());
}
return 0;
}
Convert Prefix expression to Postfix expression using stack
Converting a prefix expression to a postfix expression is almost the same as the above conversions. The one difference
is that we’ll use stack to store operands this time.
Algorithm:
Reverse the prefix string.
Create a stack.
For each character c in the input stream:
if c is an operand
{
Push it in the stack
}
else
{ // c is an operator
Pop two tokens(operand) from the stack. Concatenate the operands and the operator, as (operand 1 + operand 2 +
operator). And push this string back in the stack
}
Note: This string will now act as an operand.
Repeat until the stack is empty or the input string ends.
For a better understanding, let’s trace out an example: * + A B – C D
Reversed String: D C – B A + *
When you see an operator,
pop the top two elements from stack
first popped = operand1
second popped = operand2
result = operand1 operand2 operator
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define MAX 100
char stack[MAX][MAX]; // stack of strings
int top = -1;
// Push string
void push(char str[]) {
strcpy(stack[++top], str);
}
// Pop string
char* pop() {
return stack[top--];
}
// Reverse string
void reverse(char exp[]) {
int i, j;
char temp;
int n = strlen(exp);
for(i = 0, j = n - 1; i < j; i++, j--) {
temp = exp[i];
exp[i] = exp[j];
exp[j] = temp;
}
printf("Reversed string %s\n",exp);
}
// Check operator
int isOperator(char c) {
return (c == '+' || c == '-' || c == '*' || c == '/' || c == '^' || c == '%');
}
int main() {
char prefix[MAX];
char op1[MAX], op2[MAX], temp[MAX];
printf("Enter prefix expression: ");
scanf("%s", prefix);
// Step 1: Reverse prefix
reverse(prefix);
int len;
// Step 2: Traverse
for(int i = 0; prefix[i] != '\0'; i++) {
// Operand
if (isalnum(prefix[i])) {
char str[2];
str[0] = prefix[i];
str[1] = '\0';
push(str);
}
// Operator
else if (isOperator(prefix[i])) {
strcpy(op1, pop());
strcpy(op2, pop());
// Concatenate: op1 op2 operator
strcpy(temp, op1);
strcat(temp, op2);
len = strlen(temp);
temp[len] = prefix[i];
temp[len+1] = '\0';
push(temp);
}
}
// Final result
printf("Postfix Expression: %s\n", pop());
return 0;
}
Postfix evaluation::
Postfix evaluation in C is typically implemented using a Stack data structure to store operands while scanning the
expression from left to right. This notation, also known as Reverse Polish Notation (RPN), eliminates the need for
parentheses and complex precedence rules
Why Postfix evaluation is better??
No Parentheses: Postfix never needs brackets to define order, making the expression shorter and simpler to
parse.
No Precedence Rules: The order of operations is determined entirely by the position of operators; no
"BODMAS/PEMDAS" logic is required.
Single-Pass Evaluation: The computer scans the expression exactly once from left to right without ever needing
to look back or jump ahead.
Stack-Friendly: It maps perfectly to a Last-In, First-Out (LIFO) stack, which is the most efficient way for
hardware and compilers to handle math.
No Backtracking: Unlike infix, the machine doesn't have to "wait" to see if a higher-priority operator (like
multiplication) is coming up later.
Easier than Prefix: While prefix also avoids parentheses, it often requires a right-to-left scan or more complex
recursion, whereas postfix is straightforward for a computer's standard left-to-right reading
Algorithm for Postfix Evaluation
1. Create an empty stack called operandStack.
2. Scan the string from left to right.
1. If the token is an operand, convert it from a string to an integer and push the value onto the
operand stack.
2. If the token is an operator, *, /, +, or -, it will need two operands. Pop the operandStack twice. The
first pop is the second operand and the second pop is the first operand. Perform the arithmetic
operation. Push the result back on the operand stack.
3. When the input expression has been completely processed, the result is on the stack. Pop the operand stack
andreturnthevalue
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int x) {
stack[++top] = x;
}
int pop() {
return stack[top--];
}
// Evaluate postfix
int evaluatePostfix(char exp[]) {
int i = 0;
while (exp[i] != '\0') {
if (exp[i] == ' ') {
i++;
continue;
}
// If operand (single or multi-digit but spaces included between)
if (isdigit(exp[i])) {
int num = 0;
// Build the full number
while (isdigit(exp[i])) {
num = num * 10 + (exp[i] - '0');
i++;
}
push(num);
}
// If operator
else {
int op2 = pop();
int op1 = pop();
int result;
switch (exp[i]) {
case '+': result = op1 + op2; break;
case '-': result = op1 - op2; break;
case '*': result = op1 * op2; break;
case '/': result = op1 / op2; break;
}
push(result);
i++;
}
}
return pop();
}
int main() {
char exp[MAX];
printf("Enter postfix expression (with spaces): ");
fgets(exp, MAX, stdin);
printf("Result = %d\n", evaluatePostfix(exp));
return 0;
}
Time and space complexity: