Stacks and Queues in C Programming: A

Comprehensive Guide
Abstract
This document provides an exhaustive exploration of stacks and queues in C programming,
two fundamental linear data structures that form the backbone of numerous algorithms
and applications in computer science. Stacks operate on the Last-In-First-Out (LIFO)
principle, where the most recently added element is the first to be removed, while queues
follow the First-In-First-Out (FIFO) principle, processing elements in the order they
arrive[33][34][38]. This comprehensive guide examines implementation techniques using
both arrays and linked lists, essential operations, memory management considerations,
practical applications including function call management and job scheduling, and
advanced concepts such as implementing one structure using the other. Through detailed
explanations and over 40 code examples with explanatory comments, readers will gain
mastery of stack and queue manipulation essential for algorithm design, systems
programming, and technical interviews[34][37][39].

1. Introduction to Stacks and Queues

1.1 What is a Stack?
A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle,
meaning the element inserted last is the first one to be removed[33][38]. The analogy of a
stack of plates perfectly illustrates this behavior: you can only add plates to the top of the
stack and remove plates from the top. The plate you placed last is the first one you'll take
off.
Stacks are fundamental to many computing operations, from managing function calls
during program execution to evaluating arithmetic expressions and implementing undo
functionality in applications. The restricted access pattern—allowing operations only at
one end called the "top"—provides both simplicity and powerful utility for specific problem
domains.
The two primary operations that define a stack are:

• Push: Add an element to the top of the stack

• Pop: Remove the element from the top of the stack
Additional supporting operations include:
• Peek/Top: View the top element without removing it
• isEmpty: Check if the stack contains any elements
• isFull: Check if the stack has reached capacity (for array-based implementations)
1.2 What is a Queue?
A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle,
meaning the element inserted first is the first one to be removed[33][36][38]. The real-world
analogy is a line of people waiting at a ticket counter: the person who arrives first gets
served first, and new arrivals join at the back of the line.
Queues are essential in scenarios requiring orderly processing, such as printer job
scheduling, breadth-first search algorithms, CPU task scheduling, and handling
asynchronous data transfer between processes. The discipline of FIFO ordering ensures
fairness and predictability in resource allocation and task management.
The two primary operations that define a queue are:

• Enqueue: Add an element to the rear (back) of the queue

• Dequeue: Remove an element from the front of the queue
Additional supporting operations include:
• Front/Peek: View the front element without removing it
• Rear: View the rear element
• isEmpty: Check if the queue contains any elements
• isFull: Check if the queue has reached capacity (for array-based implementations)

1.3 Stack vs Queue Comparison

Understanding the fundamental differences between stacks and queues is crucial for
selecting the appropriate data structure:

Aspect Stack Queue

Principle LIFO (Last In First Out) FIFO (First In First Out)
Insertion Push at top Enqueue at rear
Deletion Pop from top Dequeue from front
Access Points One end (top) Two ends (front and rear)
Pointers Needed One (top) Two (front and rear)
Example Stack of plates Line at ticket counter
Applications Function calls, undo/redo Job scheduling, BFS
Order Reverse order Same order

Table 1: Comparison between stacks and queues[33][34][38]

1.4 Why Use Stacks and Queues?

Stack Applications:

• Function Call Management: Every programming language uses a call stack to

manage function execution and return addresses[38]
• Expression Evaluation: Converting infix to postfix notation and evaluating
mathematical expressions
 • Backtracking Algorithms: Maze solving, tree traversal (depth-first search), and
game state exploration
• Undo/Redo Operations: Text editors and graphics applications maintain operation
history using stacks[38]
• Browser History: Back and forward navigation in web browsers
• Syntax Parsing: Checking balanced parentheses, brackets, and braces in code
Queue Applications:

• Job Scheduling: Operating systems use queues to manage processes waiting for CPU
time[38]
• Resource Sharing: Print spoolers, disk scheduling, and network packet routing[38]
• Breadth-First Search: Level-order tree traversal and shortest path algorithms
• Asynchronous Data Transfer: Buffers for IO operations, keyboard input handling
• Call Center Systems: Managing customer service requests in order of arrival
• Simulation Systems: Modeling real-world waiting scenarios for analysis

2. Stack Implementation Using Arrays

2.1 Array-Based Stack Structure
An array-based stack uses contiguous memory allocation and a top pointer to track the
current stack position[34]:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

// Structure for array-based stack

struct Stack {
int items[MAX_SIZE];
int top;
};
// Initialize stack
void initStack(struct Stack* stack) {
stack->top = -1; // Empty stack indicated by top = -1
}
// Check if stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

// Check if stack is full

int isFull(struct Stack* stack) {
return stack->top == MAX_SIZE - 1;
}
2.2 Push Operation
The push operation adds an element to the top of the stack:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Stack {
int items[MAX_SIZE];
int top;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}
int isFull(struct Stack* stack) {
return stack->top == MAX_SIZE - 1;
}

// Push element onto stack

void push(struct Stack* stack, int value) {
// Check for stack overflow
if (isFull(stack)) {
printf("Stack Overflow! Cannot push %d\n", value);
return;
}

// Increment top and add element

stack->top++;
stack->items[stack->top] = value;
printf("Pushed: %d\n", value);

int main() {
struct Stack stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
 return 0;

Output:
Pushed: 10
Pushed: 20
Pushed: 30
Pushed: 40

2.3 Pop Operation

The pop operation removes and returns the top element:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Stack {
int items[MAX_SIZE];
int top;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

int isFull(struct Stack* stack) {

return stack->top == MAX_SIZE - 1;
}
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow!\n");
return;
}
stack->top++;
stack->items[stack->top] = value;
}
// Pop element from stack
int pop(struct Stack* stack) {
// Check for stack underflow
if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from empty stack\n");
return -1;
}

// Get top element and decrement top

int value = stack->items[stack->top];
stack->top--;
return value;

}
int main() {
struct Stack stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);

printf("\nPopped: %d\n", pop(&stack));

printf("Popped: %d\n", pop(&stack));
printf("Popped: %d\n", pop(&stack));

return 0;

}
Output:
Popped: 40
Popped: 30
Popped: 20

2.4 Peek Operation

The peek operation returns the top element without removing it:
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

struct Stack {
int items[MAX_SIZE];
int top;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}

int isFull(struct Stack* stack) {

return stack->top == MAX_SIZE - 1;
}
void push(struct Stack* stack, int value) {
if (isFull(stack)) {
printf("Stack Overflow!\n");
return;
}
stack->top++;
stack->items[stack->top] = value;
}
// Peek at top element without removing
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return -1;
}
return stack->items[stack->top];
}

int main() {
struct Stack stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);

printf("Top element: %d\n", peek(&stack));

printf("Top element again: %d\n", peek(&stack));

return 0;

}
2.5 Display Stack
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int items[MAX_SIZE];
int top;
};

void initStack(struct Stack* stack) {

stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, int value) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow!\n");
return;
}
stack->top++;
stack->items[stack->top] = value;
}

// Display all elements in stack

void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return;
}

printf("Stack (top to bottom): ");

// Display from top to bottom
for (int i = stack->top; i >= 0; i--) {
printf("%d ", stack->items[i]);
}
printf("\n");

int main() {
struct Stack stack;
initStack(&stack);
 push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
push(&stack, 50);

display(&stack);

return 0;

Output:
Stack (top to bottom): 50 40 30 20 10

3. Stack Implementation Using Linked List

3.1 Node Structure for Stack
A linked list-based stack uses dynamic memory allocation, eliminating the fixed-size
limitation[34]:
#include <stdio.h>
#include <stdlib.h>
// Node structure for linked list stack
struct Node {
int data;
struct Node* next;
};

// Stack structure with top pointer

struct Stack {
struct Node* top;
};
// Initialize stack
void initStack(struct Stack* stack) {
stack->top = NULL;
}
// Check if stack is empty
int isEmpty(struct Stack* stack) {
return stack->top == NULL;
}
3.2 Push Operation (Linked List)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
struct Stack {
struct Node* top;
};

void initStack(struct Stack* stack) {

stack->top = NULL;
}
int isEmpty(struct Stack* stack) {
return stack->top == NULL;
}
// Push element onto linked list stack
void push(struct Stack* stack, int value) {
// Allocate memory for new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {
printf("Memory allocation failed! Stack overflow\n");
return;
}

// Initialize new node

newNode->data = value;
newNode->next = stack->top; // Point to current top

// Update top to new node

stack->top = newNode;
printf("Pushed: %d\n", value);

}
int main() {
struct Stack stack;
initStack(&stack);
 push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);

return 0;

3.3 Pop Operation (Linked List)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};
struct Stack {
struct Node* top;
};
void initStack(struct Stack* stack) {
stack->top = NULL;
}

int isEmpty(struct Stack* stack) {

return stack->top == NULL;
}
void push(struct Stack* stack, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = stack->top;
stack->top = newNode;
}
// Pop element from linked list stack
int pop(struct Stack* stack) {
// Check for stack underflow
if (isEmpty(stack)) {
printf("Stack Underflow! Cannot pop from empty stack\n");
return -1;
}
 // Get top node
struct Node* temp = stack->top;
int value = temp->data;

// Update top to next node

stack->top = stack->top->next;

// Free memory
free(temp);

return value;

int main() {
struct Stack stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);

printf("\nPopped: %d\n", pop(&stack));

printf("Popped: %d\n", pop(&stack));

return 0;

3.4 Complete Stack Implementation (Linked List)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};
struct Stack {
struct Node* top;
};
void initStack(struct Stack* stack) {
stack->top = NULL;
}

int isEmpty(struct Stack* stack) {

return stack->top == NULL;
}
void push(struct Stack* stack, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = stack->top;
stack->top = newNode;
printf("Pushed: %d\n", value);
}
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow!\n");
return -1;
}
struct Node* temp = stack->top;
int value = temp->data;
stack->top = stack->top->next;
free(temp);
return value;
}

// Peek at top element

int peek(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return -1;
}
return stack->top->data;
}
// Display stack
void display(struct Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty\n");
return;
}
 struct Node* current = stack->top;
printf("Stack (top to bottom): ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");

// Free all nodes in stack

void destroyStack(struct Stack* stack) {
while (!isEmpty(stack)) {
pop(stack);
}
}
int main() {
struct Stack stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);
push(&stack, 50);

display(&stack);

printf("\nTop element: %d\n", peek(&stack));

printf("\nPopped: %d\n", pop(&stack));

printf("Popped: %d\n", pop(&stack));

display(&stack);

// Clean up
destroyStack(&stack);
 return 0;

4. Queue Implementation Using Arrays

4.1 Simple Queue (Array)
A simple array-based queue uses front and rear pointers to track queue boundaries[34][36]:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure for array-based queue
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};

// Initialize queue
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
// Check if queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}
// Check if queue is full
int isFull(struct Queue* queue) {
return queue->rear == MAX_SIZE - 1;
}

4.2 Enqueue Operation

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}

int isFull(struct Queue* queue) {

return queue->rear == MAX_SIZE - 1;
}
// Enqueue (add element to rear)
void enqueue(struct Queue* queue, int value) {
// Check for queue overflow
if (isFull(queue)) {
printf("Queue Overflow! Cannot enqueue %d\n", value);
return;
}

// If queue is empty, set front to 0

if (isEmpty(queue)) {
queue->front = 0;
}

// Increment rear and add element

queue->rear++;
queue->items[queue->rear] = value;
printf("Enqueued: %d\n", value);

}
int main() {
struct Queue queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

return 0;
}

4.3 Dequeue Operation

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}

int isFull(struct Queue* queue) {

return queue->rear == MAX_SIZE - 1;
}
void enqueue(struct Queue* queue, int value) {
if (isFull(queue)) {
printf("Queue Overflow!\n");
return;
}
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = value;
}
// Dequeue (remove element from front)
int dequeue(struct Queue* queue) {
// Check for queue underflow
if (isEmpty(queue)) {
printf("Queue Underflow! Cannot dequeue from empty queue\n");
return -1;
}

// Get front element

int value = queue->items[queue->front];
 // If this was the last element, reset queue
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
// Move front forward
queue->front++;
}

return value;

int main() {
struct Queue queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

printf("\nDequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

return 0;

4.4 Circular Queue Implementation

A circular queue overcomes the limitation of simple queues by wrapping around to the
beginning when reaching the end[36]:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 5
// Structure for circular queue
struct CircularQueue {
int items[MAX_SIZE];
int front;
int rear;
};
// Initialize circular queue
void initQueue(struct CircularQueue* queue) {
queue->front = -1;
queue->rear = -1;
}

// Check if queue is empty

int isEmpty(struct CircularQueue* queue) {
return queue->front == -1;
}
// Check if queue is full
int isFull(struct CircularQueue* queue) {
return (queue->rear + 1) % MAX_SIZE == queue->front;
}
// Enqueue in circular queue
void enqueue(struct CircularQueue* queue, int value) {
if (isFull(queue)) {
printf("Queue Overflow! Cannot enqueue %d\n", value);
return;
}

// If queue is empty, set front to 0

if (isEmpty(queue)) {
queue->front = 0;
}

// Circular increment of rear

queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->items[queue->rear] = value;
printf("Enqueued: %d\n", value);

}
// Dequeue from circular queue
int dequeue(struct CircularQueue* queue) {
if (isEmpty(queue)) {
printf("Queue Underflow!\n");
return -1;
}
 int value = queue->items[queue->front];

// If this was the last element, reset queue

if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
// Circular increment of front
queue->front = (queue->front + 1) % MAX_SIZE;
}

return value;

// Display circular queue

void display(struct CircularQueue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return;
}

printf("Queue (front to rear): ");

int i = queue->front;

while (1) {
printf("%d ", queue->items[i]);
if (i == queue->rear) {
break;
}
i = (i + 1) % MAX_SIZE;
}
printf("\n");

int main() {
struct CircularQueue queue;
initQueue(&queue);
 enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

display(&queue);

printf("\nDequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

display(&queue);

// Now we can add more elements

enqueue(&queue, 50);
enqueue(&queue, 60);

display(&queue);

return 0;

5. Queue Implementation Using Linked List

5.1 Node Structure for Queue
A linked list-based queue eliminates size constraints and overflow issues[34][37]:

#include <stdio.h>
#include <stdlib.h>
// Node structure for queue
struct Node {
int data;
struct Node* next;
};
// Queue structure with front and rear pointers
struct Queue {
struct Node* front;
struct Node* rear;
};
// Initialize queue
void initQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}
// Check if queue is empty
int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}

5.2 Enqueue Operation (Linked List)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
void initQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}

int isEmpty(struct Queue* queue) {

return queue->front == NULL;
}
// Enqueue element to linked list queue
void enqueue(struct Queue* queue, int value) {
// Allocate memory for new node
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}

// Initialize new node

newNode->data = value;
newNode->next = NULL;
 // If queue is empty, new node is both front and rear
if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
} else {
// Add new node at rear and update rear pointer
queue->rear->next = newNode;
queue->rear = newNode;
}

printf("Enqueued: %d\n", value);

int main() {
struct Queue queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

return 0;

5.3 Dequeue Operation (Linked List)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
void initQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}
int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}

void enqueue(struct Queue* queue, int value) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = NULL;

if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}

// Dequeue element from linked list queue

int dequeue(struct Queue* queue) {
// Check for queue underflow
if (isEmpty(queue)) {
printf("Queue Underflow! Cannot dequeue from empty queue\n");
return -1;
}

// Get front node

struct Node* temp = queue->front;
int value = temp->data;

// Update front to next node

queue->front = queue->front->next;

// If queue becomes empty, update rear to NULL

if (queue->front == NULL) {
queue->rear = NULL;
 }

// Free memory
free(temp);

return value;

int main() {
struct Queue queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

printf("\nDequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

return 0;

5.4 Complete Queue Implementation (Linked List)

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node* front;
struct Node* rear;
};
void initQueue(struct Queue* queue) {
queue->front = NULL;
queue->rear = NULL;
}
int isEmpty(struct Queue* queue) {
return queue->front == NULL;
}
void enqueue(struct Queue* queue, int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
if (newNode == NULL) {
printf("Memory allocation failed!\n");
return;
}
newNode->data = value;
newNode->next = NULL;

if (isEmpty(queue)) {
queue->front = newNode;
queue->rear = newNode;
} else {
queue->rear->next = newNode;
queue->rear = newNode;
}
printf("Enqueued: %d\n", value);

}
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue Underflow!\n");
return -1;
}
struct Node* temp = queue->front;
int value = temp->data;
queue->front = queue->front->next;
if (queue->front == NULL) {
queue->rear = NULL;
}
free(temp);
return value;
}

// Get front element without removing

int getFront(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty!\n");
return -1;
}
return queue->front->data;
}
// Get rear element
int getRear(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty!\n");
return -1;
}
return queue->rear->data;
}
// Display queue
void display(struct Queue* queue) {
if (isEmpty(queue)) {
printf("Queue is empty\n");
return;
}

struct Node* current = queue->front;

printf("Queue (front to rear): ");
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");

}
// Free all nodes in queue
void destroyQueue(struct Queue* queue) {
while (!isEmpty(queue)) {
dequeue(queue);
}
}

int main() {
struct Queue queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);
enqueue(&queue, 50);

display(&queue);
 printf("\nFront element: %d\n", getFront(&queue));
printf("Rear element: %d\n", getRear(&queue));

printf("\nDequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

display(&queue);

// Clean up
destroyQueue(&queue);

return 0;

6. Implementing Stack Using Queue

6.1 Stack Using Two Queues (Push Costly)
In this approach, push operation is O(n) while pop is O(1)[33][37]:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Queue structure
struct Queue {
int items[MAX_SIZE];
int front;
int rear;
};

// Stack using two queues

struct StackUsingQueue {
struct Queue q1;
struct Queue q2;
};
// Initialize queue
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
int isQueueEmpty(struct Queue* queue) {
return queue->front == -1;
}
// Enqueue operation for queue
void enqueue(struct Queue* queue, int value) {
if (isQueueEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = value;
}
// Dequeue operation for queue
int dequeue(struct Queue* queue) {
if (isQueueEmpty(queue)) {
return -1;
}
int value = queue->items[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front++;
}
return value;
}

// Initialize stack
void initStack(struct StackUsingQueue* stack) {
initQueue(&stack->q1);
initQueue(&stack->q2);
}
// Push element onto stack (O(n) operation)
void push(struct StackUsingQueue* stack, int value) {
// Add new element to q2
enqueue(&stack->q2, value);

// Move all elements from q1 to q2

while (!isQueueEmpty(&stack->q1)) {
enqueue(&stack->q2, dequeue(&stack->q1));
}

// Swap q1 and q2
struct Queue temp = stack->q1;
stack->q1 = stack->q2;
stack->q2 = temp;

printf("Pushed: %d\n", value);

}
// Pop element from stack (O(1) operation)
int pop(struct StackUsingQueue* stack) {
if (isQueueEmpty(&stack->q1)) {
printf("Stack Underflow!\n");
return -1;
}
return dequeue(&stack->q1);
}

// Peek at top element

int peek(struct StackUsingQueue* stack) {
if (isQueueEmpty(&stack->q1)) {
printf("Stack is empty!\n");
return -1;
}
return stack->[Link][stack->[Link]];
}
int isEmpty(struct StackUsingQueue* stack) {
return isQueueEmpty(&stack->q1);
}
int main() {
struct StackUsingQueue stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);

printf("\nTop element: %d\n", peek(&stack));

printf("\nPopped: %d\n", pop(&stack));

printf("Popped: %d\n", pop(&stack));

printf("\nTop element: %d\n", peek(&stack));

return 0;

}
6.2 Stack Using Single Queue
This approach uses only one queue with recursion[35]:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Queue {
int items[MAX_SIZE];
int front;
int rear;
int size;
};
// Initialize queue
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
queue->size = 0;
}
int isEmpty(struct Queue* queue) {
return queue->size == 0;
}

// Enqueue operation
void enqueue(struct Queue* queue, int value) {
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear = (queue->rear + 1) % MAX_SIZE;
queue->items[queue->rear] = value;
queue->size++;
}
// Dequeue operation
int dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
return -1;
}
int value = queue->items[queue->front];
queue->front = (queue->front + 1) % MAX_SIZE;
queue->size--;
if (queue->size == 0) {
queue->front = -1;
queue->rear = -1;
}
return value;
}
// Stack using single queue
struct StackUsingSingleQueue {
struct Queue q;
};
void initStack(struct StackUsingSingleQueue* stack) {
initQueue(&stack->q);
}

// Push element (O(n) operation)

void push(struct StackUsingSingleQueue* stack, int value) {
int size = stack->[Link];

// Add new element

enqueue(&stack->q, value);

// Rotate queue to make new element at front

for (int i = 0; i < size; i++) {
enqueue(&stack->q, dequeue(&stack->q));
}

printf("Pushed: %d\n", value);

// Pop element (O(1) operation)

int pop(struct StackUsingSingleQueue* stack) {
if (isEmpty(&stack->q)) {
printf("Stack Underflow!\n");
return -1;
}
return dequeue(&stack->q);
}
// Peek at top element
int peek(struct StackUsingSingleQueue* stack) {
if (isEmpty(&stack->q)) {
printf("Stack is empty!\n");
return -1;
}
return stack->[Link][stack->[Link]];
}
int isStackEmpty(struct StackUsingSingleQueue* stack) {
return isEmpty(&stack->q);
}
int main() {
struct StackUsingSingleQueue stack;
initStack(&stack);

push(&stack, 10);
push(&stack, 20);
push(&stack, 30);
push(&stack, 40);

printf("\nTop element: %d\n", peek(&stack));

printf("\nPopped: %d\n", pop(&stack));

printf("Popped: %d\n", pop(&stack));

printf("\nTop element: %d\n", peek(&stack));

return 0;

7. Implementing Queue Using Stack

7.1 Queue Using Two Stacks (Enqueue Costly)
In this approach, enqueue is O(n) while dequeue is O(1)[37]:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

// Stack structure
struct Stack {
int items[MAX_SIZE];
int top;
};
// Queue using two stacks
struct QueueUsingStack {
struct Stack s1;
struct Stack s2;
};
// Initialize stack
void initStack(struct Stack* stack) {
stack->top = -1;
}
int isStackEmpty(struct Stack* stack) {
return stack->top == -1;
}

// Push to stack
void push(struct Stack* stack, int value) {
stack->top++;
stack->items[stack->top] = value;
}
// Pop from stack
int pop(struct Stack* stack) {
if (isStackEmpty(stack)) {
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}
// Initialize queue
void initQueue(struct QueueUsingStack* queue) {
initStack(&queue->s1);
initStack(&queue->s2);
}

// Enqueue operation (O(n) - costly)

void enqueue(struct QueueUsingStack* queue, int value) {
// Move all elements from s1 to s2
while (!isStackEmpty(&queue->s1)) {
push(&queue->s2, pop(&queue->s1));
}

// Push new element to s1

push(&queue->s1, value);

// Move all elements back from s2 to s1

while (!isStackEmpty(&queue->s2)) {
push(&queue->s1, pop(&queue->s2));
}

printf("Enqueued: %d\n", value);

}
// Dequeue operation (O(1))
int dequeue(struct QueueUsingStack* queue) {
if (isStackEmpty(&queue->s1)) {
printf("Queue Underflow!\n");
return -1;
}
return pop(&queue->s1);
}
// Get front element
int getFront(struct QueueUsingStack* queue) {
if (isStackEmpty(&queue->s1)) {
printf("Queue is empty!\n");
return -1;
}
return queue->[Link][queue->[Link]];
}

int isEmpty(struct QueueUsingStack* queue) {

return isStackEmpty(&queue->s1);
}
int main() {
struct QueueUsingStack queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

printf("\nFront element: %d\n", getFront(&queue));

printf("\nDequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

printf("\nFront element: %d\n", getFront(&queue));

return 0;

}
7.2 Queue Using Two Stacks (Dequeue Costly)
In this approach, enqueue is O(1) while dequeue is O(n)[37]:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

struct Stack {
int items[MAX_SIZE];
int top;
};
struct QueueUsingStack {
struct Stack s1;
struct Stack s2;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}

int isStackEmpty(struct Stack* stack) {

return stack->top == -1;
}
void push(struct Stack* stack, int value) {
stack->top++;
stack->items[stack->top] = value;
}
int pop(struct Stack* stack) {
if (isStackEmpty(stack)) {
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}

void initQueue(struct QueueUsingStack* queue) {

initStack(&queue->s1);
initStack(&queue->s2);
}
// Enqueue operation (O(1))
void enqueue(struct QueueUsingStack* queue, int value) {
push(&queue->s1, value);
printf("Enqueued: %d\n", value);
}
// Dequeue operation (O(n) - costly)
int dequeue(struct QueueUsingStack* queue) {
// If both stacks are empty
if (isStackEmpty(&queue->s1) && isStackEmpty(&queue->s2)) {
printf("Queue Underflow!\n");
return -1;
}

// If s2 is empty, move all elements from s1 to s2

if (isStackEmpty(&queue->s2)) {
while (!isStackEmpty(&queue->s1)) {
push(&queue->s2, pop(&queue->s1));
}
}

// Pop from s2
return pop(&queue->s2);

}
// Get front element
int getFront(struct QueueUsingStack* queue) {
if (isStackEmpty(&queue->s1) && isStackEmpty(&queue->s2)) {
printf("Queue is empty!\n");
return -1;
}

// If s2 is empty, move all elements from s1 to s2

if (isStackEmpty(&queue->s2)) {
while (!isStackEmpty(&queue->s1)) {
push(&queue->s2, pop(&queue->s1));
}
}

return queue->[Link][queue->[Link]];

}
int isEmpty(struct QueueUsingStack* queue) {
return isStackEmpty(&queue->s1) && isStackEmpty(&queue->s2);
}
int main() {
struct QueueUsingStack queue;
initQueue(&queue);

enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
enqueue(&queue, 40);

printf("\nFront element: %d\n", getFront(&queue));

printf("\nDequeued: %d\n", dequeue(&queue));

printf("Dequeued: %d\n", dequeue(&queue));

enqueue(&queue, 50);

printf("\nFront element: %d\n", getFront(&queue));

printf("\nDequeued: %d\n", dequeue(&queue));

return 0;

8. Stack Applications and Problems

8.1 Balanced Parentheses Checker
Checking if parentheses, brackets, and braces are balanced is a classic stack application:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100

struct Stack {
char items[MAX_SIZE];
int top;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, char value) {
stack->top++;
stack->items[stack->top] = value;
}

char pop(struct Stack* stack) {

if (isEmpty(stack)) {
return '\0';
}
char value = stack->items[stack->top];
stack->top--;
return value;
}
char peek(struct Stack* stack) {
if (isEmpty(stack)) {
return '\0';
}
return stack->items[stack->top];
}
// Check if opening bracket
int isOpeningBracket(char ch) {
return ch == '(' || ch == '[' || ch == '{';
}

// Check if closing bracket

int isClosingBracket(char ch) {
return ch == ')' || ch == ']' || ch == '}';
}
// Check if brackets match
int isMatchingPair(char opening, char closing) {
return (opening == '(' && closing == ')') ||
(opening == '[' && closing == ']') ||
(opening == '{' && closing == '}');
}
// Check if expression has balanced brackets
int isBalanced(char* expression) {
struct Stack stack;
initStack(&stack);

for (int i = 0; i < strlen(expression); i++) {

char ch = expression[i];
 // If opening bracket, push to stack
if (isOpeningBracket(ch)) {
push(&stack, ch);
}
// If closing bracket, check if it matches top of stack
else if (isClosingBracket(ch)) {
if (isEmpty(&stack)) {
return 0; // Closing bracket without opening
}
char top = pop(&stack);
if (!isMatchingPair(top, ch)) {
return 0; // Mismatched brackets
}
}
}

// Stack should be empty if balanced

return isEmpty(&stack);

int main() {
char expr1[] = "{[()]}";
char expr2[] = "{[(])}";
char expr3[] = "((a+b)*c)";
char expr4[] = "((a+b)";

printf("Expression: %s - ", expr1);

printf(isBalanced(expr1) ? "Balanced\n" : "Not Balanced\n");

printf("Expression: %s - ", expr2);

printf(isBalanced(expr2) ? "Balanced\n" : "Not Balanced\n");

printf("Expression: %s - ", expr3);

printf(isBalanced(expr3) ? "Balanced\n" : "Not Balanced\n");

printf("Expression: %s - ", expr4);

printf(isBalanced(expr4) ? "Balanced\n" : "Not Balanced\n");
 return 0;

8.2 Infix to Postfix Conversion

Converting infix expressions to postfix notation using operator precedence:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_SIZE 100
struct Stack {
char items[MAX_SIZE];
int top;
};

void initStack(struct Stack* stack) {

stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, char value) {
stack->top++;
stack->items[stack->top] = value;
}

char pop(struct Stack* stack) {

if (isEmpty(stack)) {
return '\0';
}
char value = stack->items[stack->top];
stack->top--;
return value;
}
char peek(struct Stack* stack) {
if (isEmpty(stack)) {
return '\0';
}
return stack->items[stack->top];
}
// Get operator precedence
int getPrecedence(char op) {
if (op == '+' || op == '-') {
return 1;
}
if (op == '*' || op == '/') {
return 2;
}
if (op == '^') {
return 3;
}
return 0;
}
// Check if character is operator
int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
}

// Convert infix to postfix

void infixToPostfix(char* infix, char* postfix) {
struct Stack stack;
initStack(&stack);

int j = 0; // Index for postfix expression

for (int i = 0; i < strlen(infix); i++) {

char ch = infix[i];

// If operand, add to postfix

if (isalnum(ch)) {
postfix[j++] = ch;
}
// If opening parenthesis, push to stack
else if (ch == '(') {
push(&stack, ch);
}
// If closing parenthesis, pop until opening parenthesis
else if (ch == ')') {
while (!isEmpty(&stack) && peek(&stack) != '(') {
postfix[j++] = pop(&stack);
}
pop(&stack); // Remove opening parenthesis
}
// If operator
 else if (isOperator(ch)) {
// Pop operators with higher or equal precedence
while (!isEmpty(&stack) &&
getPrecedence(peek(&stack)) >= getPrecedence(ch)) {
postfix[j++] = pop(&stack);
}
push(&stack, ch);
}
}

// Pop remaining operators

while (!isEmpty(&stack)) {
postfix[j++] = pop(&stack);
}

postfix[j] = '\0';

int main() {
char infix1[] = "a+b*c";
char infix2[] = "(a+b)c";
char infix3[] = "a+bc-d/e";
char postfix[MAX_SIZE];

infixToPostfix(infix1, postfix);
printf("Infix: %s\n", infix1);
printf("Postfix: %s\n\n", postfix);

infixToPostfix(infix2, postfix);
printf("Infix: %s\n", infix2);
printf("Postfix: %s\n\n", postfix);

infixToPostfix(infix3, postfix);
printf("Infix: %s\n", infix3);
printf("Postfix: %s\n", postfix);

return 0;
}

8.3 Postfix Expression Evaluation

Evaluating postfix expressions using a stack:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 100

struct Stack {
int items[MAX_SIZE];
int top;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}

int isEmpty(struct Stack* stack) {

return stack->top == -1;
}
void push(struct Stack* stack, int value) {
stack->top++;
stack->items[stack->top] = value;
}
int pop(struct Stack* stack) {
if (isEmpty(stack)) {
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}

// Check if character is operator

int isOperator(char ch) {
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
// Perform operation
int performOperation(int operand1, int operand2, char op) {
switch (op) {
case '+': return operand1 + operand2;
case '-': return operand1 - operand2;
case '*': return operand1 * operand2;
case '/': return operand1 / operand2;
default: return 0;
}
}
// Evaluate postfix expression
int evaluatePostfix(char* postfix) {
struct Stack stack;
initStack(&stack);

for (int i = 0; i < strlen(postfix); i++) {

char ch = postfix[i];

// If operand, push to stack

if (isdigit(ch)) {
push(&stack, ch - '0'); // Convert char to int
}
// If operator, pop two operands and perform operation
else if (isOperator(ch)) {
int operand2 = pop(&stack);
int operand1 = pop(&stack);
int result = performOperation(operand1, operand2, ch);
push(&stack, result);
}
}

// Result is at top of stack

return pop(&stack);

}
int main() {
char postfix1[] = "235+"; // (23)+5 = 11
char postfix2[] = "234*+"; // 2+(34) = 14
char postfix3[] = "53+82-"; // (5+3)*(8-2) = 48

printf("Postfix: %s\n", postfix1);

printf("Result: %d\n\n", evaluatePostfix(postfix1));

printf("Postfix: %s\n", postfix2);

printf("Result: %d\n\n", evaluatePostfix(postfix2));

printf("Postfix: %s\n", postfix3);

 printf("Result: %d\n", evaluatePostfix(postfix3));

return 0;

8.4 Next Greater Element

Finding the next greater element for each element in an array:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int items[MAX_SIZE];
int top;
};

void initStack(struct Stack* stack) {

stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, int value) {
stack->top++;
stack->items[stack->top] = value;
}

int pop(struct Stack* stack) {

if (isEmpty(stack)) {
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
return -1;
}
return stack->items[stack->top];
}
// Find next greater element for each element
void nextGreaterElement(int arr[], int n, int result[]) {
struct Stack stack;
initStack(&stack);

// Traverse array from right to left

for (int i = n - 1; i >= 0; i--) {
// Pop elements smaller than current
while (!isEmpty(&stack) && peek(&stack) <= arr[i]) {
pop(&stack);
}

// If stack is empty, no greater element

if (isEmpty(&stack)) {
result[i] = -1;
} else {
result[i] = peek(&stack);
}

// Push current element to stack

push(&stack, arr[i]);
}

}
int main() {
int arr[] = {4, 5, 2, 25, 7, 8};
int n = sizeof(arr) / sizeof(arr[0]);
int result[MAX_SIZE];

nextGreaterElement(arr, n, result);

printf("Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");

printf("Next Greater Elements: ");

for (int i = 0; i < n; i++) {
printf("%d ", result[i]);
 }
printf("\n");

return 0;

8.5 Stock Span Problem

Calculate the span of stock prices (number of consecutive days before current day with
price less than or equal to current):

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Stack {
int items[MAX_SIZE];
int top;
};

void initStack(struct Stack* stack) {

stack->top = -1;
}
int isEmpty(struct Stack* stack) {
return stack->top == -1;
}
void push(struct Stack* stack, int value) {
stack->top++;
stack->items[stack->top] = value;
}

int pop(struct Stack* stack) {

if (isEmpty(stack)) {
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}
int peek(struct Stack* stack) {
if (isEmpty(stack)) {
return -1;
}
return stack->items[stack->top];
}
// Calculate stock span
void calculateSpan(int prices[], int n, int span[]) {
struct Stack stack;
initStack(&stack);

// First element's span is always 1

span[0] = 1;
push(&stack, 0);

for (int i = 1; i < n; i++) {

// Pop elements while stack is not empty and
// price at top of stack is smaller than current price
while (!isEmpty(&stack) && prices[peek(&stack)] <= prices[i]) {
pop(&stack);
}

// If stack is empty, all previous prices are smaller

if (isEmpty(&stack)) {
span[i] = i + 1;
} else {
span[i] = i - peek(&stack);
}

// Push current index to stack

push(&stack, i);
}

}
int main() {
int prices[] = {100, 80, 60, 70, 60, 75, 85};
int n = sizeof(prices) / sizeof(prices[0]);
int span[MAX_SIZE];

calculateSpan(prices, n, span);

printf("Day: ");
for (int i = 0; i < n; i++) {
printf("%d ", i + 1);
}
 printf("\n");

printf("Price: ");
for (int i = 0; i < n; i++) {
printf("%d ", prices[i]);
}
printf("\n");

printf("Span: ");
for (int i = 0; i < n; i++) {
printf("%d ", span[i]);
}
printf("\n");

return 0;

8.6 Reverse String Using Stack

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 100

struct Stack {
char items[MAX_SIZE];
int top;
};
void initStack(struct Stack* stack) {
stack->top = -1;
}

int isEmpty(struct Stack* stack) {

return stack->top == -1;
}
void push(struct Stack* stack, char value) {
stack->top++;
stack->items[stack->top] = value;
}
char pop(struct Stack* stack) {
if (isEmpty(stack)) {
return '\0';
}
char value = stack->items[stack->top];
stack->top--;
return value;
}
// Reverse string using stack
void reverseString(char* str) {
struct Stack stack;
initStack(&stack);

// Push all characters to stack

for (int i = 0; i < strlen(str); i++) {
push(&stack, str[i]);
}

// Pop all characters and overwrite string

for (int i = 0; i < strlen(str); i++) {
str[i] = pop(&stack);
}

}
int main() {
char str1[] = "Hello World";
char str2[] = "Stack Operations";

printf("Original: %s\n", str1);

reverseString(str1);
printf("Reversed: %s\n\n", str1);

printf("Original: %s\n", str2);

reverseString(str2);
printf("Reversed: %s\n", str2);

return 0;

}
9. Queue Applications and Problems
9.1 Generate Binary Numbers
Generate binary numbers from 1 to N using a queue:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100

struct Queue {
char items[MAX_SIZE][20];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}

void enqueue(struct Queue* queue, char* value) {

if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
strcpy(queue->items[queue->rear], value);
}
void dequeue(struct Queue* queue, char* result) {
if (isEmpty(queue)) {
result[0] = '\0';
return;
}
strcpy(result, queue->items[queue->front]);
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front++;
}
}
// Generate binary numbers from 1 to n
void generateBinaryNumbers(int n) {
struct Queue queue;
initQueue(&queue);

// Start with "1"

enqueue(&queue, "1");

printf("Binary numbers from 1 to %d:\n", n);

for (int i = 0; i < n; i++) {

char current[20];
char temp1[20], temp2[20];

// Dequeue and print

dequeue(&queue, current);
printf("%s ", current);

// Generate next two binary numbers

strcpy(temp1, current);
strcat(temp1, "0");
enqueue(&queue, temp1);

strcpy(temp2, current);
strcat(temp2, "1");
enqueue(&queue, temp2);
}
printf("\n");

}
int main() {
generateBinaryNumbers(10);
printf("\n");
generateBinaryNumbers(15);

return 0;

}
9.2 First Non-Repeating Character in Stream
Find the first non-repeating character in a stream of characters:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR 256
#define MAX_SIZE 100

struct Queue {
char items[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}
int isEmpty(struct Queue* queue) {
return queue->front == -1;
}

void enqueue(struct Queue* queue, char value) {

if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = value;
}
char dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
return '\0';
}
char value = queue->items[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front++;
}
return value;
}
char getFront(struct Queue* queue) {
if (isEmpty(queue)) {
return '\0';
}
return queue->items[queue->front];
}
// Find first non-repeating character in stream
void firstNonRepeating(char* stream) {
struct Queue queue;
initQueue(&queue);

int charCount[MAX_CHAR] = {0};

printf("Stream: %s\n", stream);

printf("First non-repeating characters:\n");

for (int i = 0; i < strlen(stream); i++) {

char ch = stream[i];

// Increment count
charCount[ch]++;

// Add to queue if first occurrence

if (charCount[ch] == 1) {
enqueue(&queue, ch);
}

// Remove characters from front that are repeating

while (!isEmpty(&queue) && charCount[getFront(&queue)] > 1) {
dequeue(&queue);
}

// Print first non-repeating character

if (isEmpty(&queue)) {
printf("%c -> -1\n", ch);
} else {
printf("%c -> %c\n", ch, getFront(&queue));
}
}

}
int main() {
char stream[] = "aabcddbe";
firstNonRepeating(stream);

return 0;

9.3 Sliding Window Maximum

Find maximum in each sliding window of size k:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

// Deque implementation for sliding window

struct Deque {
int items[MAX_SIZE];
int front;
int rear;
};
void initDeque(struct Deque* deque) {
deque->front = -1;
deque->rear = -1;
}
int isEmpty(struct Deque* deque) {
return deque->front == -1;
}

void insertRear(struct Deque* deque, int value) {

if (isEmpty(deque)) {
deque->front = 0;
deque->rear = 0;
} else {
deque->rear++;
}
deque->items[deque->rear] = value;
}
void deleteFront(struct Deque* deque) {
if (isEmpty(deque)) {
return;
}
if (deque->front == deque->rear) {
deque->front = -1;
deque->rear = -1;
} else {
deque->front++;
}
}
void deleteRear(struct Deque* deque) {
if (isEmpty(deque)) {
return;
}
if (deque->front == deque->rear) {
deque->front = -1;
deque->rear = -1;
} else {
deque->rear--;
}
}

int getFront(struct Deque* deque) {

if (isEmpty(deque)) {
return -1;
}
return deque->items[deque->front];
}
int getRear(struct Deque* deque) {
if (isEmpty(deque)) {
return -1;
}
return deque->items[deque->rear];
}
// Find maximum in each sliding window
void slidingWindowMaximum(int arr[], int n, int k) {
struct Deque deque;
initDeque(&deque);

printf("Array: ");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
printf("Window size: %d\n", k);
printf("Maximums in each window:\n");

// Process first k elements

for (int i = 0; i < k; i++) {
// Remove elements smaller than current from rear
while (!isEmpty(&deque) && arr[getRear(&deque)] <= arr[i]) {
deleteRear(&deque);
 }
insertRear(&deque, i);
}

// Process remaining elements

for (int i = k; i < n; i++) {
// Front of deque is the maximum of previous window
printf("%d ", arr[getFront(&deque)]);

// Remove elements outside current window

while (!isEmpty(&deque) && getFront(&deque) <= i - k) {
deleteFront(&deque);
}

// Remove elements smaller than current from rear

while (!isEmpty(&deque) && arr[getRear(&deque)] <= arr[i]) {
deleteRear(&deque);
}

insertRear(&deque, i);
}

// Print maximum of last window

printf("%d\n", arr[getFront(&deque)]);

int main() {
int arr[] = {1, 3, -1, -3, 5, 3, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;

slidingWindowMaximum(arr, n, k);

return 0;

}
9.4 Level Order Tree Traversal
Perform level order traversal of a binary tree using a queue:
#include <stdio.h>
#include <stdlib.h>
// Tree node structure
struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
};

#define MAX_SIZE 100

// Queue for tree nodes
struct Queue {
struct TreeNode* items[MAX_SIZE];
int front;
int rear;
};
void initQueue(struct Queue* queue) {
queue->front = -1;
queue->rear = -1;
}

int isEmpty(struct Queue* queue) {

return queue->front == -1;
}
void enqueue(struct Queue* queue, struct TreeNode* node) {
if (isEmpty(queue)) {
queue->front = 0;
}
queue->rear++;
queue->items[queue->rear] = node;
}
struct TreeNode* dequeue(struct Queue* queue) {
if (isEmpty(queue)) {
return NULL;
}
struct TreeNode* node = queue->items[queue->front];
if (queue->front == queue->rear) {
queue->front = -1;
queue->rear = -1;
} else {
queue->front++;
}
return node;
}
// Create a new tree node
struct TreeNode* createNode(int value) {
struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// Level order traversal (BFS)
void levelOrderTraversal(struct TreeNode* root) {
if (root == NULL) {
printf("Tree is empty\n");
return;
}

struct Queue queue;

initQueue(&queue);

enqueue(&queue, root);

printf("Level Order Traversal: ");

while (!isEmpty(&queue)) {
struct TreeNode* current = dequeue(&queue);
printf("%d ", current->data);

// Enqueue left child

if (current->left != NULL) {
enqueue(&queue, current->left);
}

// Enqueue right child

if (current->right != NULL) {
enqueue(&queue, current->right);
}
}
printf("\n");

}
int main() {
// Create sample tree:
// 1
// /
// 2 3
// / \
// 4 5 6

struct TreeNode* root = createNode(1);

root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->right = createNode(6);

levelOrderTraversal(root);

// Free memory (simplified - should do proper traversal)

free(root->left->left);
free(root->left->right);
free(root->right->right);
free(root->left);
free(root->right);
free(root);

return 0;

9.5 Circular Tour (Petrol Pump Problem)

Find the starting petrol pump from which a circular tour is possible:
#include <stdio.h>
#include <stdlib.h>
// Structure for petrol pump
struct PetrolPump {
int petrol;
int distance;
};

// Find starting point for circular tour

int findStartingPoint(struct PetrolPump pumps[], int n) {
int start = 0;
int currentPetrol = 0;
int totalPetrol = 0;
int totalDistance = 0;

for (int i = 0; i < n; i++) {

totalPetrol += pumps[i].petrol;
totalDistance += pumps[i].distance;

currentPetrol += pumps[i].petrol - pumps[i].distance;

// If current petrol becomes negative, start from next pump

if (currentPetrol < 0) {
start = i + 1;
currentPetrol = 0;
}
}

// If total petrol is less than total distance, tour not possible

if (totalPetrol < totalDistance) {
return -1;
}

return start;

}
int main() {
struct PetrolPump pumps[] = {
{4, 6}, // Pump 0: 4 units petrol, 6 km to next
{6, 5}, // Pump 1: 6 units petrol, 5 km to next
{7, 3}, // Pump 2: 7 units petrol, 3 km to next
{4, 5} // Pump 3: 4 units petrol, 5 km to next
};

int n = sizeof(pumps) / sizeof(pumps[0]);

printf("Petrol Pumps:\n");
for (int i = 0; i < n; i++) {
printf("Pump %d: Petrol=%d, Distance=%d\n",
i, pumps[i].petrol, pumps[i].distance);
}
 int start = findStartingPoint(pumps, n);

if (start == -1) {
printf("\nCircular tour not possible\n");
} else {
printf("\nStart circular tour from pump: %d\n", start);
}

return 0;

10. Advanced Stack and Queue Concepts

10.1 Minimum Stack
Design a stack that supports push, pop, and retrieving the minimum element in O(1)
time[41]:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Stack that tracks minimum
struct MinStack {
int items[MAX_SIZE];
int minItems[MAX_SIZE]; // Parallel stack to track minimum
int top;
};

void initStack(struct MinStack* stack) {

stack->top = -1;
}
int isEmpty(struct MinStack* stack) {
return stack->top == -1;
}
// Push element
void push(struct MinStack* stack, int value) {
if (stack->top == MAX_SIZE - 1) {
printf("Stack Overflow!\n");
return;
}
 stack->top++;
stack->items[stack->top] = value;

// Update minimum
if (stack->top == 0) {
stack->minItems[stack->top] = value;
} else {
int currentMin = stack->minItems[stack->top - 1];
stack->minItems[stack->top] = (value < currentMin) ? value : currentMin;
}

printf("Pushed: %d (min: %d)\n", value, stack->minItems[stack->top]);

// Pop element
int pop(struct MinStack* stack) {
if (isEmpty(stack)) {
printf("Stack Underflow!\n");
return -1;
}
int value = stack->items[stack->top];
stack->top--;
return value;
}
// Get minimum element in O(1)
int getMin(struct MinStack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return -1;
}
return stack->minItems[stack->top];
}
int main() {
struct MinStack stack;
initStack(&stack);

push(&stack, 5);
push(&stack, 3);
push(&stack, 7);
push(&stack, 2);
push(&stack, 9);
 printf("\nCurrent minimum: %d\n", getMin(&stack));

printf("\nPopped: %d\n", pop(&stack));

printf("Current minimum: %d\n", getMin(&stack));

printf("\nPopped: %d\n", pop(&stack));

printf("Current minimum: %d\n", getMin(&stack));

return 0;

10.2 Priority Queue (Simple Implementation)

A priority queue where elements are dequeued based on priority:

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// Structure for priority queue element
struct Element {
int data;
int priority;
};

struct PriorityQueue {
struct Element items[MAX_SIZE];
int size;
};
void initQueue(struct PriorityQueue* pq) {
pq->size = 0;
}
int isEmpty(struct PriorityQueue* pq) {
return pq->size == 0;
}

// Enqueue with priority

void enqueue(struct PriorityQueue* pq, int data, int priority) {
if (pq->size == MAX_SIZE) {
printf("Priority Queue Overflow!\n");
return;
}
 // Add element at end
pq->items[pq->size].data = data;
pq->items[pq->size].priority = priority;
pq->size++;

printf("Enqueued: %d (priority: %d)\n", data, priority);

// Dequeue highest priority element

int dequeue(struct PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority Queue Underflow!\n");
return -1;
}

// Find element with highest priority (smallest priority value)

int highestPriorityIndex = 0;
for (int i = 1; i < pq->size; i++) {
if (pq->items[i].priority < pq->items[highestPriorityIndex].priority) {
highestPriorityIndex = i;
}
}

int data = pq->items[highestPriorityIndex].data;

// Shift elements
for (int i = highestPriorityIndex; i < pq->size - 1; i++) {
pq->items[i] = pq->items[i + 1];
}
pq->size--;

return data;

// Display priority queue

void display(struct PriorityQueue* pq) {
if (isEmpty(pq)) {
printf("Priority Queue is empty\n");
return;
}

printf("Priority Queue:\n");
for (int i = 0; i < pq->size; i++) {
printf("Data: %d, Priority: %d\n",
pq->items[i].data, pq->items[i].priority);
}

}
int main() {
struct PriorityQueue pq;
initQueue(&pq);

enqueue(&pq, 100, 2);

enqueue(&pq, 200, 1);
enqueue(&pq, 300, 3);
enqueue(&pq, 400, 1);

printf("\n");
display(&pq);

printf("\nDequeued: %d\n", dequeue(&pq));

printf("Dequeued: %d\n", dequeue(&pq));

printf("\n");
display(&pq);

return 0;

10.3 Double-Ended Queue (Deque)

A deque allows insertion and deletion at both ends:
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
struct Deque {
int items[MAX_SIZE];
int front;
int rear;
int size;
};
void initDeque(struct Deque* deque) {
deque->front = -1;
deque->rear = -1;
deque->size = 0;
}

int isEmpty(struct Deque* deque) {

return deque->size == 0;
}
int isFull(struct Deque* deque) {
return deque->size == MAX_SIZE;
}
// Insert at front
void insertFront(struct Deque* deque, int value) {
if (isFull(deque)) {
printf("Deque Overflow!\n");
return;
}

if (isEmpty(deque)) {
deque->front = 0;
deque->rear = 0;
} else {
deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE;
}

deque->items[deque->front] = value;
deque->size++;
printf("Inserted at front: %d\n", value);

}
// Insert at rear
void insertRear(struct Deque* deque, int value) {
if (isFull(deque)) {
printf("Deque Overflow!\n");
return;
}
 if (isEmpty(deque)) {
deque->front = 0;
deque->rear = 0;
} else {
deque->rear = (deque->rear + 1) % MAX_SIZE;
}

deque->items[deque->rear] = value;
deque->size++;
printf("Inserted at rear: %d\n", value);

// Delete from front

int deleteFront(struct Deque* deque) {
if (isEmpty(deque)) {
printf("Deque Underflow!\n");
return -1;
}

int value = deque->items[deque->front];

if (deque->front == deque->rear) {
deque->front = -1;
deque->rear = -1;
} else {
deque->front = (deque->front + 1) % MAX_SIZE;
}

deque->size--;
return value;

// Delete from rear

int deleteRear(struct Deque* deque) {
if (isEmpty(deque)) {
printf("Deque Underflow!\n");
return -1;
}
 int value = deque->items[deque->rear];

if (deque->front == deque->rear) {
deque->front = -1;
deque->rear = -1;
} else {
deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE;
}

deque->size--;
return value;

// Display deque
void display(struct Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty\n");
return;
}

printf("Deque: ");
int i = deque->front;
int count = 0;

while (count < deque->size) {

printf("%d ", deque->items[i]);
i = (i + 1) % MAX_SIZE;
count++;
}
printf("\n");

int main() {
struct Deque deque;
initDeque(&deque);

insertRear(&deque, 10);
insertRear(&deque, 20);
 insertFront(&deque, 5);
insertFront(&deque, 2);

display(&deque);

printf("\nDeleted from front: %d\n", deleteFront(&deque));

printf("Deleted from rear: %d\n", deleteRear(&deque));

display(&deque);

return 0;

11. Performance Analysis and Best Practices

11.1 Time Complexity Comparison
Array Linked Array Linked
Operation
Stack Stack Queue Queue
Push/Enqueue O(1) O(1) O(1) O(1)
Pop/Dequeue O(1) O(1) O(1) O(1)
Peek/Front O(1) O(1) O(1) O(1)
isEmpty O(1) O(1) O(1) O(1)
isFull O(1) N/A O(1) N/A

Table 2: Time complexity of stack and queue operations[34][39]

11.2 Space Complexity

• Array-based: O(n) - Fixed size allocated upfront, may waste memory
• Linked list-based: O(n) - Dynamic allocation, extra memory for pointers but no
waste
• Circular Queue: O(n) - Efficient use of array space

11.3 Array vs Linked List Implementation

 Array Linked List
Aspect
Implementation Implementation
Size Fixed Dynamic
Memory Contiguous Non-contiguous
Overflow Possible Only if heap full
Memory Overhead Lower Higher (pointers)
Cache
Better Worse
Performance
Implementation Simpler More complex
Memory Waste Possible Minimal

Table 3: Comparison of implementation approaches[34][37]

11.4 Best Practices

• Always Check Overflow/Underflow: Validate conditions before push/pop and
enqueue/dequeue operations[34]
• Use Circular Queues: For array-based queues, circular implementation prevents
wasted space
• Choose Appropriate Implementation: Use arrays for fixed-size needs, linked lists
for dynamic requirements
• Free Memory Properly: For linked implementations, ensure all nodes are freed to
prevent memory leaks
• Initialize Structures: Always initialize top, front, and rear pointers correctly
• Handle Edge Cases: Empty and single-element conditions require special attention
• Consider Thread Safety: In concurrent environments, implement synchronization
mechanisms
• Use Sentinel Values Wisely: Choose appropriate sentinel values that won't conflict
with valid data

11.5 Common Pitfalls

• Forgetting Overflow Checks: Pushing to full array-based stack causes undefined
behavior
• Memory Leaks: Not freeing nodes in linked list implementations
• Incorrect Pointer Updates: Failing to update front/rear correctly in queue
operations
• Off-by-One Errors: Miscalculating indices in circular queue wrap-around
• Lost Data: Overwriting queue elements in simple array implementation
• NULL Pointer Dereference: Not checking for empty conditions before accessing
elements
• Stack Overflow in Recursion: Deep recursion exhausts call stack memory
11.6 When to Use Stacks vs Queues
Use Stacks when:
Need LIFO behavior (undo operations, backtracking)
Managing function calls and recursion
Parsing nested structures (parentheses, expressions)
Reversing sequences
Implementing depth-first search
Use Queues when:

Need FIFO behavior (fair scheduling, buffering)

Managing resources in order of arrival
Implementing breadth-first search
Handling asynchronous data (IO buffers)
Simulation of real-world waiting scenarios

12. Conclusion
Stacks and queues are fundamental abstract data types that provide specialized access
patterns essential for numerous algorithms and applications in computer science[33][34]
[38]. The LIFO principle of stacks and FIFO principle of queues offer powerful abstractions
that simplify complex problem-solving by enforcing specific element access orders.
Through this comprehensive guide, we have explored their implementation using both
arrays and linked lists, examined essential operations with detailed code examples, and
investigated advanced applications ranging from expression evaluation to graph traversal
algorithms.
Understanding the trade-offs between array-based and linked list-based implementations
enables informed design decisions. Array implementations offer better cache locality and
simpler code at the cost of fixed capacity, while linked list implementations provide
dynamic sizing and eliminate overflow conditions at the expense of pointer overhead.
Circular queues elegantly solve the space inefficiency of simple array queues,
demonstrating how algorithmic thinking can optimize data structure performance.

The practical applications covered—balanced parentheses checking, infix-to-postfix

conversion, binary number generation, level-order traversal, and sliding window problems
—illustrate the versatility of stacks and queues in solving real-world computational
challenges[38][39]. The ability to implement one structure using the other demonstrates the
theoretical equivalence and practical interchangeability of these data structures when
efficiency considerations are secondary to conceptual understanding.
Mastery of stacks and queues forms the foundation for understanding more sophisticated
data structures like priority queues, deques, and complex graph algorithms. The over 40
code examples with explanatory comments provided in this guide enable hands-on
practice essential for technical interviews, competitive programming, and professional
software development. By understanding these fundamental patterns—from basic
operations to advanced problem-solving techniques—programmers develop the
algorithmic intuition necessary for tackling increasingly complex computational problems
across diverse domains of computer science and software engineering.
References
[33] Implementation of Stack Using a Queue in C, C++, and Java. (2024, November 25). CCBP.
[Link]
[34] Stacks and Queues in C – Master the Concepts of LIFO & FIFO. (2022, December 29).
DataFlair. [Link]

[35] Implementation of Queues using Stack in C. (2025, March 19). PrepInsta. [Link]
[Link]/c-program/implementation-of-queues-using-stack/
[36] Queue Data Structure and Implementation in Java, Python and C/C++. (2024, October
31). Programiz. [Link]
[37] How to Create a Queue in C (With Code Examples). (2025, May 1). DigitalOcean. https://
[Link]/community/tutorials/queue-in-c

[38] Stacks and Queues: Implementation, Operations and Applications. (2025, March 16).
EICTA. [Link]
mplementation-operations-and-applications
[39] Top 20 Stack and Queue Data Structure Interview Questions. (2025, July 2).
JavaRevisited. [Link]
[Link]
[40] Stack and Queue Implementation in C. (2025, September 3). Scribd. [Link]
om/document/363875570/C-Program-to-Implement-a-Stack-and-Queue-Using-a-Linked-List

[41] Minimum Stack / Minimum Queue. (2025, August 8). CP-Algorithms. [Link]
[Link]/data_structures/stack_queue_modification.html
[42] 50+ stacks and queues questions with solutions. (2021, September 12). IGotAnOffer. http
s://[Link]/blogs/tech/stacks-and-queues-interview-questions