Stack Using Queue

A stack can be implemented using two queues in C. The basic idea is to use one queue for enqueue operations and another for dequeue operations. When an element is pushed onto the stack, it is enqueued into the enqueue queue. When an element is popped from the stack, it is dequeued from the dequeue queue along with all other elements, except the last one, and enqueued back into the enqueue queue in reverse order. The last element is then dequeued from the dequeue queue and returned.

#include <stdio.h>

#include <stdlib.h>

#define MAX_SIZE 100

// Define the queue data structure

struct queue {

int data[MAX_SIZE];

int front;

int rear;

};

// Initialize a queue

void init_queue(struct queue *q) {

q->front = -1;

q->rear = -1;

}

// Check if the queue is empty

int is_empty(struct queue *q) {

return q->front == -1;

}

// Check if the queue is full

int is_full(struct queue *q) {

return (q->rear + 1) % MAX_SIZE == q->front;

}

// Enqueue an element

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

if (is_full(q)) {

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

exit(EXIT_FAILURE);

}

if (is_empty(q)) {

q->front = 0;

}

q->rear = (q->rear + 1) % MAX_SIZE;

q->data[q->rear] = element;

}

// Dequeue an element

int dequeue(struct queue *q) {

if (is_empty(q)) {

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

exit(EXIT_FAILURE);

}

int element = q->data[q->front];

if (q->front == q->rear) {

q->front = -1;

q->rear = -1;

} else {

q->front = (q->front + 1) % MAX_SIZE;

}

return element;

}

// Define the stack data structure

struct stack {

struct queue enqueue_queue;

struct queue dequeue_queue;

};

// Initialize a stack

void init_stack(struct stack *s) {

init_queue(&s->enqueue_queue);

init_queue(&s->dequeue_queue);

}

// Push an element onto the stack

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

enqueue(&s->enqueue_queue, element);

}

// Pop an element from the stack

int pop(struct stack *s) {

if (is_empty(&s->enqueue_queue)) {

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

exit(EXIT_FAILURE);

}

while (!is_empty(&s->enqueue_queue) && s->enqueue_queue.front != s->enqueue_queue.rear) {

int element = dequeue(&s->enqueue_queue);

enqueue(&s->dequeue_queue, element);

}

int element = dequeue(&s->enqueue_queue);

struct queue temp = s->enqueue_queue;

s->enqueue_queue = s->dequeue_queue;

s->dequeue_queue = temp;

return element;

}

// Main function to test the stack

int main() {

struct stack s;

init_stack(&s);

push(&s, 1);

push(&s, 2);

push(&s, 3);

printf("%d\n", pop(&s));

printf("%d\n", pop(&s));

printf("%d\n", pop(&s));

return 0;

}

In this implementation, the queue struct represents a queue and the stack struct represents a stack. The push_queue is used to enqueue elements onto the stack, and the pop_queue is used to dequeue elements from the stack. When an element is popped, the implementation checks if the pop_queue is empty. If it is, it dequeues all the elements except the last one from the push_queue and enqueues them onto the pop_queue. The last element is then dequeued from the push_queue and returned as the popped element. The implementation uses the enqueue() and dequeue() functions to enqueue and dequeue elements onto and from the queues.