Queue Using Stack

A queue can be implemented using two stacks in C. The basic idea is to use one stack for enqueue operations and another for dequeue operations. When an element is enqueued, it is pushed onto the enqueue stack. When an element is dequeued, it is popped from the dequeue stack. If the dequeue stack is empty, all the elements from the enqueue stack are popped and pushed onto the dequeue stack, effectively reversing the order of the elements.

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

// Define the stack data structure

struct stack {

int data[MAX_SIZE];

int top;

};

// Initialize a stack

void init stack(struct stack *s) {

s->top = -1;

}

// Check if the stack is empty

int is empty(struct stack *s) {

return s->top == -1;

}

// Check if the stack is full

int is full(struct stack *s) {

return s->top == MAX_SIZE - 1;

}

// Push an element onto the stack

void push(struct stack *s, int element) {

if (is full(s)) {

printf("Error: Stack is full\n");

exit(EXIT_FAILURE);

}

s->top++;

s->data[s->top] = element;

}

// Pop an element from the stack

int pop(struct stack *s) {

if (is empty(s)) {

printf("Error: Stack is empty\n");

exit(EXIT_FAILURE);

}

int element = s->data[s->top];

s->top--;

return element;

}

// Define the queue data structure

struct queue {

struct stack enqueue stack;

struct stack dequeue stack;

};

// Initialize a queue

void init queue(struct queue *q) {

init stack(&q->enqueue stack);

init stack(&q->dequeue stack);

}

// Enqueue an element

void enqueue(struct queue *q, int element) {

push(&q->enqueue stack, element);

}

// Dequeue an element

int dequeue(struct queue *q) {

if (is empty(&q->dequeue stack)) {

while (!is empty(&q->enqueue stack)) {

int element = pop(&q->enqueue stack);

push(&q->dequeue stack, element);

}

}

return pop(&q->dequeue stack);

}

// Main function to test the queue

int main() {

struct queue q;

init queue(&q);

enqueue(&q, 1);

enqueue(&q, 2);

enqueue(&q, 3);

printf("%d\n", dequeue(&q));

printf("%d\n", dequeue(&q));

printf("%d\n", dequeue(&q));

return 0;

}

In this implementation, the stack struct represents a stack and the queue struct represents a queue. The enqueue_stack is used to push elements onto the queue, and the dequeue_stack is used to pop elements from the queue. When an element is dequeued, the implementation checks if the dequeue_stack is empty. If it is, it pops all the elements from the enqueue_stack and pushes them onto the dequeue_stack in reverse order, effectively reversing the order of the elements. The implementation uses the push() and pop() functions to push and pop elements onto and from the stacks.