UNIT 3 – Data Structures: Stacks, Queues, and Expressions
1. Write a C program to perform all the operations of a Stack
A stack is a linear data structure that follows the Last In, First Out (LIFO) principle. The
basic operations of a stack are:
- Push: Insert an element
- Pop: Remove the top element
- Peek/Top: View the top element
- IsEmpty/IsFull: Check for empty or full stack
C Program:
#include <stdio.h>
#define SIZE 100
int stack[SIZE], top = -1;
void push(int value) {
if(top == SIZE - 1)
printf("Stack Overflow\n");
else {
top++;
stack[top] = value;
printf("Pushed %d\n", value);
}
void pop() {
if(top == -1)
printf("Stack Underflow\n");
else {
printf("Popped %d\n", stack[top]);
top--;
void peek() {
if(top == -1)
printf("Stack is Empty\n");
else
printf("Top element: %d\n", stack[top]);
void display() {
if(top == -1)
printf("Stack is Empty\n");
else {
printf("Stack elements: ");
for(int i = top; i >= 0; i--)
printf("%d ", stack[i]);
printf("\n");
}
int main() {
push(10);
push(20);
peek();
display();
pop();
display();
return 0;
2. Explain the mechanism to convert an infix expression to prefix and postfix
expressions using an example
Infix: Operators are between operands (A + B)
Prefix (Polish): Operators precede operands (+AB)
Postfix (Reverse Polish): Operators follow operands (AB+)
Conversion Steps:
1. Infix to Postfix:
- Use a stack to hold operators and maintain precedence.
- Output operands directly.
- Pop operators based on precedence and parentheses.
2. Infix to Prefix:
- Reverse the infix expression.
- Replace ( with ) and vice versa.
- Apply infix-to-postfix logic.
- Reverse the result.
Example:
Infix: (A + B) * C
Postfix: AB+C*
Prefix: *+ABC
Applications:
- Expression evaluation
- Compilers and interpreters
- Stack-based expression parsing
3. Design an algorithm for implementation of Dequeue
A Dequeue (Double Ended Queue) allows insertion and deletion from both front and rear.
Types:
- Input-restricted dequeue: Insert at rear only, delete at both ends.
- Output-restricted dequeue: Delete at front only, insert at both ends.
Array-based Dequeue Implementation:
#define SIZE 5
int dq[SIZE];
int front = -1, rear = -1;
Insert at Rear:
if((rear + 1) % SIZE == front)
printf("Overflow\n");
else {
if(front == -1)
front = rear = 0;
else
rear = (rear + 1) % SIZE;
dq[rear] = value;
Insert at Front:
if((rear + 1) % SIZE == front)
printf("Overflow\n");
else {
if(front == -1)
front = rear = 0;
else
front = (front - 1 + SIZE) % SIZE;
dq[front] = value;
Delete from Front:
if(front == -1)
printf("Underflow\n");
else {
printf("Deleted %d", dq[front]);
if(front == rear)
front = rear = -1;
else
front = (front + 1) % SIZE;
Delete from Rear:
if(front == -1)
printf("Underflow\n");
else {
printf("Deleted %d", dq[rear]);
if(front == rear)
front = rear = -1;
else
rear = (rear - 1 + SIZE) % SIZE;
Applications:
- Job scheduling
- Palindrome checking
- Undo/redo operations
4. Convert the following infix expressions into postfix
a) (A + B) / (C + D) – (D * E)
Postfix: AB+CD+/DE*-
b) (A – B) * (C + D)
Postfix: AB-CD+*
c) A – (B / C + (D % E * F) / G) * H
Postfix: ABC/DE%F*G/+H*-
Conversion uses operator precedence and stack-based logic.
Operators: ^ > *, /, % > +, -
Associativity: Most are left-associative.
Use stack for operators and output operands directly.