When multiple stacks need to function as separate queues within a single memory array, a strategic implementation is required. This can be done using fixed partitioning or dynamic partitioning methods.
Here’s a detailed explanation and implementation:
1. Concept of Multiple Stacks as Queues
To implement multiple queues using stacks:
- Each queue uses two stacks.
- Stack 1 (Input Stack): Used for enqueue operations (pushing elements).
- Stack 2 (Output Stack): Used for dequeue operations (retrieving elements).
- Queues are managed independently.
2. Operations in Each Queue
- Enqueue:
- Push the element into Stack 1.
- Dequeue:
- If Stack 2 is empty, transfer all elements from Stack 1 to Stack 2.
- Pop the top element from Stack 2.
3. Implementation of Two Queues Using Stacks
Here is a C implementation of two independent queues managed by stacks.
Code
#include <stdio.h>
#include <stdlib.h>
#define MAX 10
// Structure to represent a stack
typedef struct {
int arr[MAX];
int top;
} Stack;
// Function to initialize a stack
void initStack(Stack *s) {
s->top = -1;
}
// Function to check if a stack is full
int isFull(Stack *s) {
return s->top == MAX – 1;
}
// Function to check if a stack is empty
int isEmpty(Stack *s) {
return s->top == -1;
}
// Function to push an element onto a stack
void push(Stack *s, int value) {
if (isFull(s)) {
printf(“Stack Overflow\n”);
} else {
s->arr[++(s->top)] = value;
}
}
// Function to pop an element from a stack
int pop(Stack *s) {
if (isEmpty(s)) {
printf(“Stack Underflow\n”);
return -1;
} else {
return s->arr[(s->top)–];
}
}
// Function to get the top element of a stack
int peek(Stack *s) {
if (isEmpty(s)) {
printf(“Stack is empty\n”);
return -1;
} else {
return s->arr[s->top];
}
}
// Structure to represent a queue using two stacks
typedef struct {
Stack stack1;
Stack stack2;
} Queue;
// Initialize the queue
void initQueue(Queue *q) {
initStack(&(q->stack1));
initStack(&(q->stack2));
}
// Enqueue operation
void enqueue(Queue *q, int value) {
push(&(q->stack1), value);
printf(“Enqueued: %d\n”, value);
}
// Dequeue operation
int dequeue(Queue *q) {
if (isEmpty(&(q->stack2))) {
while (!isEmpty(&(q->stack1))) {
push(&(q->stack2), pop(&(q->stack1)));
}
}
return pop(&(q->stack2));
}
// Display elements in the queue
void displayQueue(Queue *q) {
// Transfer elements from stack1 to stack2 for printing
while (!isEmpty(&(q->stack1))) {
push(&(q->stack2), pop(&(q->stack1)));
}
printf(“Queue elements: “);
while (!isEmpty(&(q->stack2))) {
int value = pop(&(q->stack2));
printf(“%d “, value);
push(&(q->stack1), value);
}
printf(“\n”);
}
// Main function to demonstrate the working of multiple queues
int main() {
Queue queue1, queue2;
initQueue(&queue1);
initQueue(&queue2);
// Enqueue and dequeue operations for Queue 1
enqueue(&queue1, 10);
enqueue(&queue1, 20);
enqueue(&queue1, 30);
printf(“Dequeued from Queue 1: %d\n”, dequeue(&queue1));
displayQueue(&queue1);
// Enqueue and dequeue operations for Queue 2
enqueue(&queue2, 40);
enqueue(&queue2, 50);
printf(“Dequeued from Queue 2: %d\n”, dequeue(&queue2));
displayQueue(&queue2);
return 0;
}
4. Explanation of the Code
- Stack Management:
- Each queue uses two stacks (stack1 and stack2).
- push and pop functions manage stack operations.
- Queue Operations:
- enqueue: Pushes the element onto stack1.
- dequeue:
- Transfers all elements from stack1 to stack2 if stack2 is empty.
- Pops the top element from stack2.
- Multiple Queues:
- Two queues (queue1 and queue2) are implemented independently, using separate stack pairs.
5. Sample Output
Enqueued: 10
Enqueued: 20
Enqueued: 30
Dequeued from Queue 1: 10
Queue elements: 20 30
Enqueued: 40
Enqueued: 50
Dequeued from Queue 2: 40
Queue elements: 50
6. Advantages of This Approach
- Efficient use of memory for multiple queues.
- Separation of queue logic using stacks simplifies debugging.
- Suitable for scenarios where the queue size grows dynamically.
7. Applications of Multiple Stacks as Queues
- Process Scheduling: Managing independent task queues.
- Simulation: Modeling scenarios requiring FIFO behavior.
- Communication Systems: Handling multiple message queues in parallel.
This implementation provides a robust framework to manage multiple stack-based queues within a shared memory space.