A Stack is a linear data structure that follows the LIFO (Last In First Out) principle where insertion and deletion occur at the TOP.
LIFO (Last In First Out) means the element inserted last is removed first.
- Push (Insertion)
- Pop (Deletion)
- Peek (Top element)
- isEmpty()
- isFull()
A Queue is a linear data structure that follows the FIFO (First In First Out) principle.
FIFO (First In First Out) means the element inserted first is removed first.
A Circular Queue is a queue in which the last position is connected back to the first position to utilize space efficiently.
A Priority Queue is a queue where elements are processed based on priority rather than order of insertion.
A Deque (Double Ended Queue) is a queue in which insertion and deletion can be performed at both ends.
- Overflow → When insertion is attempted in a full data structure
- Underflow → When deletion is attempted in an empty data structure
- Expression evaluation
- Function calls (recursion)
A stack is a linear data structure that follows the LIFO (Last In First Out) principle. All insertions and deletions happen at one end called TOP. Stack is used in expression evaluation, recursion, and conversion of expressions.
In array implementation, a fixed-size array is used to store stack elements and a variable top is used to indicate the index of the topmost element. Initially, top = -1, which means the stack is empty. This is the simplest and most common implementation of stack.
int stack[MAX];
int top = -1;
When a new element is inserted:
- Check whether the stack is full.
- If full, report overflow.
- Otherwise increment top.
- Insert the element at stack[top].
if(top == MAX - 1)
Overflow;
else
{
top = top + 1;
stack[top] = value;
}
When an element is removed:
- Check whether the stack is empty.
- If empty, report underflow.
- Otherwise read stack[top].
- Decrement top.
if(top == -1)
Underflow;
else
{
value = stack[top];
top = top - 1;
}
peek() returns the top element without removing it.
- Simple to implement
- Easy to access top element
- Faster due to contiguous memory
- Fixed size
- Memory may be wasted
- Overflow occurs if the array is full
In linked list implementation, each stack element is stored in a node and nodes are connected using pointers. The top pointer points to the first node of the list, which represents the top of the stack. This makes stack dynamic in size.
struct Node
{
int data;
struct Node *next;
};
To insert an element:
- Create a new node.
- Store the value in the node.
- Make the new node point to the current top.
- Update top to the new node.
newNode->next = top;
top = newNode;
To delete an element:
- Check if stack is empty.
- Store the current top in a temporary pointer.
- Move top to the next node.
- Free the old top node.
temp = top;
top = top->next;
free(temp);
- Dynamic size
- No fixed capacity
- Better memory utilization
- Extra memory needed for pointer
- Slightly complex implementation
| Feature | Array | Linked List |
|---|---|---|
| Size | Fixed | Dynamic |
| Memory | Contiguous | Non-contiguous |
| Overflow | Possible | Only if memory exhausted |
| Access | Faster | Slightly slower |
| Flexibility | Low | High |
| Operation | Array | Linked List |
|---|---|---|
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
| Peek | O(1) | O(1) |
The syllabus and unit notes show stack applications such as expression evaluation, expression conversion, recursion, and Tower of Hanoi. Stack is especially useful because it follows LIFO order, which matches the way expressions are processed and function calls are stored.
Operator is written between operands.
Example: A + B
Operator is written after operands.
Example: AB+
Operators must be arranged according to precedence and associativity. Stack stores operators temporarily until they can be placed in the correct order.
- If symbol is an operand, add it to output.
- If symbol is (, push it on stack.
- If symbol is ), pop until ( is found.
- If symbol is an operator, pop operators with higher or equal precedence and then push the current operator.
Convert: A + B * C
Postfix: ABC*+
Convert: 3 * 3 / (4 - 1) + 6 * 2
Postfix: 33*41-/62*+
The unit notes show this exact kind of step-by-step postfix conversion using stack.
Postfix expressions are easy to evaluate using a stack.
- Scan the expression from left to right.
- If operand is found, push it.
- If operator is found, pop two operands.
- Perform the operation.
- Push the result back.
- Final stack value is the answer.
This is a standard application of stack in expression evaluation.
Expression: 2 3 1 * + 9 -
Step-by-step:
Push 2
Push 3
Push 1
* → 3 × 1 = 3
+ → 2 + 3 = 5
Push 9
- → 5 - 9 = -4
Final answer: -4
- Recursion
- Tower of Hanoi
- Maze solving
- Parenthesis balancing
- Undo/redo operations
| Notation | Form | Example |
|---|---|---|
| Infix | Operand Operator Operand | A + B |
| Prefix | Operator Operand Operand | +AB |
| Postfix | Operand Operand Operator | AB+ |
A queue is a linear data structure that follows the FIFO (First In First Out) principle. The syllabus includes queue representation using arrays and linked lists, along with circular queue, priority queue, and queue applications.
In array implementation, a fixed-size array is used with two pointers:
- front for deletion
- rear for insertion
Initially:
front = -1
rear = -1
Steps:
- Check if queue is full.
- If full, report overflow.
- If queue is empty, set front = rear = 0.
- Otherwise increment rear.
- Insert element at queue[rear].
if(rear == MAX - 1)
Overflow;
else
{
if(front == -1)
front = 0;
rear = rear + 1;
queue[rear] = value;
}
Steps:
- Check if queue is empty.
- If empty, report underflow.
- Read element at queue[front].
- Increment front.
if(front == -1 || front > rear)
Underflow;
else
{
value = queue[front];
front = front + 1;
}
- Simple
- Easy to implement
- Fixed size
- Space may be wasted
In linked list implementation, nodes are dynamically created and linked. Two pointers are maintained:
- front points to first node
- rear points to last node
This is more flexible because the queue can grow dynamically.
struct Node
{
int data;
struct Node *next;
};
- Create new node.
- Insert it at rear.
- Update rear pointer.
- Check if queue is empty.
- Remove node from front.
- Move front pointer to next node.
- Dynamic size
- Better memory utilization
- More complex
- Extra pointer memory needed
| Feature | Array | Linked List |
|---|---|---|
| Size | Fixed | Dynamic |
| Insertion | O(1) | O(1) |
| Deletion | O(1) | O(1) |
| Memory | Contiguous | Dynamic nodes |
| Overflow | Possible | Only memory-based |
A circular queue is a queue where the last position is connected back to the first position, so memory is used efficiently. The syllabus specifically includes circular queue under queue operations.
In a normal linear queue, deleted spaces at the front are not reused properly. Circular queue removes this limitation by wrapping around using modulo arithmetic.
front = -1
rear = -1
- Check overflow condition.
- If queue is empty, set front = rear = 0.
- Otherwise update rear using modulo.
- Insert the element.
if((rear + 1) % MAX == front)
Overflow;
else if(front == -1)
{
front = rear = 0;
queue[rear] = value;
}
else
{
rear = (rear + 1) % MAX;
queue[rear] = value;
}
- Check if queue is empty.
- Remove the element at front.
- If only one element is present, reset queue.
- Otherwise move front using modulo.
if(front == -1)
Underflow;
else if(front == rear)
{
front = rear = -1;
}
else
{
front = (front + 1) % MAX;
}
Queue size = 5
Insert 10, 20, 30
front = 0, rear = 2
Delete 10
front = 1, rear = 2
Insert 40, 50
rear wraps around to use free space
- Better space utilization
- No wastage of deleted slots
- Useful in buffers and scheduling
- Slightly complex
- Full and empty conditions are harder to detect
A priority queue is a queue in which each element is assigned a priority, and the element with higher priority is removed before lower priority elements. Priority queue is part of the queue-related topics in your syllabus.
- Ascending priority queue
Smaller value means higher priority. - Descending priority queue
Larger value means higher priority.
Insertion happens based on priority or at the end with priority tracking.
Deletion removes the element with the highest priority.
Elements:
A(2), B(5), C(1), D(4)
If lower number = higher priority:
C(1) → A(2) → D(4) → B(5)
Priority queue can be implemented using:
- Array
- Linked list
- Heap
Heap is the most efficient implementation for priority queue operations.
- CPU scheduling
- Printer jobs
- Network packet handling
- Emergency management systems
- Graph algorithms like Dijkstra and Prim
- Important tasks handled first
- Useful for real-time systems
- Efficient scheduling
- More complex than simple queue
- Deletion may be costly in array implementation
The unit notes on stack specifically cover expression conversion and postfix evaluation using stack. This is one of the standard applications of stack.
Operator appears between operands.
A + B * C
Operator appears after operands.
ABC*+
- Scan expression from left to right.
- If the symbol is an operand, append it to output.
- If symbol is (, push it onto stack.
- If symbol is an operator:
pop operators with higher or equal precedence
push current operator - If symbol is ), pop until ( appears.
- After input ends, pop all remaining operators.
while(symbol != end)
{
if operand
output = output + symbol;
else if symbol == '('
push(symbol);
else if operator
{
while(stack not empty and precedence(top) >= precedence(symbol))
output = output + pop();
push(symbol);
}
else if symbol == ')'
{
while(top != '(')
output = output + pop();
pop(); // remove '('
}
}
while(stack not empty)
output = output + pop();
Convert:
3 * 3 / (4 - 1) + 6 * 2
Postfix:
33*41-/62*+
This is exactly the style of postfix conversion shown in the stack unit notes.
- Scan postfix expression left to right.
- If operand, push it.
- If operator, pop two operands.
- Apply operator.
- Push result back.
- Final stack value is answer.
for each token in postfix
{
if operand
push(token);
else
{
op2 = pop();
op1 = pop();
result = op1 operator op2;
push(result);
}
}
answer = pop();
Postfix:
2 3 1 * + 9 -
Steps:
Push 2
Push 3
Push 1
* → 3 × 1 = 3
+ → 2 + 3 = 5
Push 9
- → 5 - 9 = -4
Final answer:
-4
Tower of Hanoi is a classic recursive problem and is also a standard stack application listed in your course outline. It involves moving disks from one peg to another using an auxiliary peg, following the rule that a larger disk can never be placed on a smaller disk.
- Only one disk can be moved at a time.
- A larger disk cannot be placed on a smaller disk.
- Only top disk of any peg can be moved.
Three pegs:
- Source
- Auxiliary
- Destination
Example for 3 disks:
Source: A
Auxiliary: B
Destination: C
Initial:
A: [3,2,1]
B: [ ]
C: [ ]
Goal:
A: [ ]
B: [ ]
C: [3,2,1]
For n disks:
- Move n-1 disks from source to auxiliary.
- Move largest disk to destination.
- Move n-1 disks from auxiliary to destination.
This is a classic recursion pattern where the problem is reduced into smaller subproblems.
TowerOfHanoi(n, source, auxiliary, destination)
{
if(n == 1)
{
move disk from source to destination;
return;
}
TowerOfHanoi(n-1, source, destination, auxiliary);
move disk from source to destination;
TowerOfHanoi(n-1, auxiliary, source, destination);
}
Moves:
1. A → C
2. A → B
3. C → B
4. A → C
5. B → A
6. B → C
7. A → C
Total moves:
2^n - 1 = 2^3 - 1 = 7
Recursion uses the call stack internally. Every recursive call is stored on the stack until the base case is reached. So Tower of Hanoi can be viewed both as a recursion problem and a stack-based problem.
- Disk movement simulation
- Recursion understanding
- Algorithmic problem solving
- Stack behavior demonstration
| Topic | Important Point |
|---|---|
| Stack | LIFO structure |
| Queue | FIFO structure |
| Circular Queue | Reuses empty spaces |
| Priority Queue | Higher priority first |
| Infix to Postfix | Stack-based conversion |
| Tower of Hanoi | Recursive + stack-based |
0 Comments