Stack and Queue Implementations in C: Array vs Linked List with Real-World TU BCA Lab Programs
Author: Bhuban Subedi | Subject: Data Structures and Algorithms (CACS201) | Semester: Third Semester
When students transition into the Tribhuvan University (TU) BCA Third Semester, Data Structures and Algorithms (CACS201) introduces the true backbone of computer science logic.
Among linear data structures, Stacks and Queues form the bedrock of compiler parsers, memory management call stacks, task schedulers in operating systems, and breadth-first search algorithms.
In the TU board examination, Stack and Queue questions appear constantly in both theoretical derivations (e.g., Infix to Postfix conversion, Circular Queue modulo arithmetic) and 10-mark full C implementation lab questions. In this guide, we will write fully compilable, error-free implementations for Stacks, Linear Queues, and Circular Queues.
1. The Stack Data Structure (LIFO Principle)
A Stack is a linear data structure that operates on the LIFO (Last In, First Out) principle. The element that is inserted last is always the first one to be removed. All insertions and deletions occur at a single designated end called TOP.
Stack Operations:
PUSH (Insert) POP (Remove)
| ^
v |
+---------------------+
| Data 3 | <-- TOP (Current Index)
+---------------------+
| Data 2 |
+---------------------+
| Data 1 |
+---------------------+
(Bottom)
Core Stack Operations & Boundary Conditions:
push(element): Adds an item to the top. Must check for Stack Overflow (TOP == MAX - 1).pop(): Removes and returns the top item. Must check for Stack Underflow (TOP == -1).peek()/top(): Views the top element without removing it.isEmpty(): Returns true ifTOP == -1.isFull(): Returns true ifTOP == MAX - 1.
2. Complete C Implementation: Array-Based Stack with Menu
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
struct Stack {
int items[MAX_SIZE];
int top;
};
// Function prototypes
void initStack(struct Stack *s);
int isFull(struct Stack *s);
int isEmpty(struct Stack *s);
void push(struct Stack *s, int value);
int pop(struct Stack *s);
void display(struct Stack *s);
int main() {
struct Stack s;
initStack(&s);
int choice, val;
while (1) {
printf("\n--- STACK OPERATIONS MENU (LIFO) ---\n");
printf("1. Push Element\n2. Pop Element\n3. Display Stack\n4. Exit\n");
printf("Enter choice (1-4): ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter value to push: ");
scanf("%d", &val);
push(&s, val);
break;
case 2:
val = pop(&s);
if (val != -1) {
printf("Popped Element: %d\n", val);
}
break;
case 3:
display(&s);
break;
case 4:
exit(0);
default:
printf("Invalid selection! Try again.\n");
}
}
return 0;
}
void initStack(struct Stack *s) {
s->top = -1;
}
int isFull(struct Stack *s) {
return s->top == MAX_SIZE - 1;
}
int isEmpty(struct Stack *s) {
return s->top == -1;
}
void push(struct Stack *s, int value) {
if (isFull(s)) {
printf("[ERROR] Stack Overflow! Cannot push %d.\n", value);
return;
}
s->top++;
s->items[s->top] = value;
printf("[SUCCESS] Pushed %d to stack.\n", value);
}
int pop(struct Stack *s) {
if (isEmpty(s)) {
printf("[ERROR] Stack Underflow! Stack is completely empty.\n");
return -1;
}
int poppedValue = s->items[s->top];
s->top--;
return poppedValue;
}
void display(struct Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty!\n");
return;
}
printf("\nCurrent Stack (Top to Bottom):\n");
for (int i = s->top; i >= 0; i--) {
printf("| %d | %s\n", s->items[i], (i == s->top) ? "<-- TOP" : "");
}
printf("+---+\n");
}
3. Classic Stack Application: Infix to Postfix Conversion
In TU theory exams, manual conversion of expressions from Infix to Postfix using operator precedence tables is a regular 6-mark problem.
Operator Precedence & Associativity:
- Parentheses:
( )(Highest) - Exponentiation:
^(Right to Left) - Multiplication & Division:
*,/(Left to Right) - Addition & Subtraction:
+,-(Lowest, Left to Right)
Solved TU Board Question:
“Convert the following Infix expression to Postfix notation using a Stack table:”
$$A + (B * C – (D / E \wedge F) * G) * H$$
+------------+------------------+------------------------------+
| Symbol | Stack (Bottom->) | Output Postfix String |
+------------+------------------+------------------------------+
| A | Empty | A |
| + | + | A |
| ( | + ( | A |
| B | + ( | A B |
| * | + ( * | A B |
| C | + ( * | A B C |
| - | + ( - | A B C * |
| ( | + ( - ( | A B C * |
| D | + ( - ( | A B C * D |
| / | + ( - ( / | A B C * D |
| E | + ( - ( / | A B C * D E |
| ^ | + ( - ( / ^ | A B C * D E |
| F | + ( - ( / ^ | A B C * D E F |
| ) | + ( - | A B C * D E F ^ / |
| * | + ( - * | A B C * D E F ^ / |
| G | + ( - * | A B C * D E F ^ / G |
| ) | + | A B C * D E F ^ / G * - |
| * | + * | A B C * D E F ^ / G * - |
| H | + * | A B C * D E F ^ / G * - H |
| End of Exp | Empty | A B C * D E F ^ / G * - H * +|
+------------+------------------+------------------------------+
$$\mathbf{Resulting\ Postfix:\ A B C * D E F \wedge / G * – H * +}$$
4. The Queue Data Structure (FIFO Principle)
A Queue operates on the FIFO (First In, First Out) principle. Insertion happens at the REAR end (Enqueue), and deletion happens at the FRONT end (Dequeue).
Enqueue (Insert) Dequeue (Remove)
| ^
v |
+---------------+---------------+---------------+---------------+
REAR | Data 4 | Data 3 | Data 2 | Data 1 | FRONT
+---------------+---------------+---------------+---------------+
The Major Flaw of Linear Queues:
In a fixed linear array queue, as elements are dequeued, FRONT increments forward. Eventually, REAR hits MAX - 1. Even if earlier slots become empty after dequeues, you cannot insert new elements because REAR == MAX - 1 triggers a false Queue Full condition!
5. Circular Queue: Solving Memory Wastage via Modulo Arithmetic
To eliminate the memory fragmentation of linear queues, we wrap the array into a circular ring where the slot after MAX - 1 is index 0.
[Index 0]
/ \
[Index 4] [Index 1]
| |
[Index 3]-----------[Index 2]
Circular Pointer Movement using Modulo:
$$\text{Next Position} = (\text{Current Position} + 1) \pmod{\text{MAX}}$$
Complete Circular Queue Program in C:
#include <stdio.h>
#include <stdlib.h>
#define SIZE 5
struct CircularQueue {
int items[SIZE];
int front;
int rear;
};
void initQueue(struct CircularQueue *q) {
q->front = -1;
q->rear = -1;
}
int isFull(struct CircularQueue *q) {
return ((q->rear + 1) % SIZE) == q->front;
}
int isEmpty(struct CircularQueue *q) {
return q->front == -1;
}
void enqueue(struct CircularQueue *q, int value) {
if (isFull(q)) {
printf("[ERROR] Circular Queue is FULL! Cannot insert %d\n", value);
return;
}
if (isEmpty(q)) {
q->front = 0;
q->rear = 0;
} else {
q->rear = (q->rear + 1) % SIZE;
}
q->items[q->rear] = value;
printf("[SUCCESS] Enqueued %d (Rear at index %d)\n", value, q->rear);
}
int dequeue(struct CircularQueue *q) {
if (isEmpty(q)) {
printf("[ERROR] Circular Queue is EMPTY!\n");
return -1;
}
int data = q->items[q->front];
if (q->front == q->rear) { // Only one element was present
q->front = -1;
q->rear = -1;
} else {
q->front = (q->front + 1) % SIZE;
}
return data;
}
void display(struct CircularQueue *q) {
if (isEmpty(q)) {
printf("Queue is empty!\n");
return;
}
printf("Circular Queue elements: ");
int i = q->front;
while (1) {
printf("%d ", q->items[i]);
if (i == q->rear) break;
i = (i + 1) % SIZE;
}
printf("\n(Front at index %d, Rear at index %d)\n", q->front, q->rear);
}
int main() {
struct CircularQueue q;
initQueue(&q);
enqueue(&q, 10);
enqueue(&q, 20);
enqueue(&q, 30);
enqueue(&q, 40);
enqueue(&q, 50); // Queue is now full (5 items)
display(&q);
printf("\nDequeued: %d\n", dequeue(&q));
printf("Dequeued: %d\n", dequeue(&q));
display(&q);
printf("\nInserting new element 60 to verify circular wrap-around...\n");
enqueue(&q, 60); // Wraps around to index 0!
display(&q);
return 0;
}
Summary & TU Exam Takeaways
- Stack is LIFO; Queue is FIFO.
- Stack Underflow occurs at
top == -1; Stack Overflow occurs attop == MAX - 1. - Linear Queues suffer from false overflow. Circular Queues solve this using $(i + 1) \pmod{\text{MAX}}$ index calculation.
- All basic Stack/Queue operations (
push,pop,enqueue,dequeue) execute in $O(1)$ constant time.
