#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
/*
Queue implemented using two stacks in C.
Concept:
- stack_in : receives new elements (enqueue)
- stack_out : serves elements in correct queue order (dequeue)
When stack_out is empty and we need to dequeue or peek:
- Move all elements from stack_in to stack_out
This reverses the order, making the oldest element accessible.
This design provides amortized O(1) operations and keeps the code simple.
*/
/* -------------------- Stack Implementation -------------------- */
typedef struct {
int *data; // dynamic array
size_t size; // current number of elements
size_t capacity;// allocated capacity
} Stack;
// Create a new stack
Stack *stack_create(size_t initial_capacity) {
Stack *s = malloc(sizeof(Stack));
if (!s) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
s->data = malloc(initial_capacity * sizeof(int));
if (!s->data) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
s->size = 0;
s->capacity = initial_capacity;
return s;
}
// Push a value onto the stack
void stack_push(Stack *s, int value) {
if (s->size == s->capacity) {
// grow capacity
s->capacity *= 2;
s->data = realloc(s->data, s->capacity * sizeof(int));
if (!s->data) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
}
s->data[s->size++] = value;
}
// Pop a value from the stack
int stack_pop(Stack *s) {
if (s->size == 0) {
fprintf(stderr, "Stack underflow\n");
exit(EXIT_FAILURE);
}
return s->data[--s->size];
}
// Peek at the top value
int stack_top(const Stack *s) {
if (s->size == 0) {
fprintf(stderr, "Stack is empty\n");
exit(EXIT_FAILURE);
}
return s->data[s->size - 1];
}
// Check if stack is empty
bool stack_empty(const Stack *s) {
return s->size == 0;
}
// Destroy stack
void stack_destroy(Stack *s) {
free(s->data);
free(s);
}
/* -------------------- Queue Using Two Stacks -------------------- */
typedef struct {
Stack *stack_in; // receives new elements
Stack *stack_out; // serves elements in queue order
} Queue;
// Create queue
Queue *queue_create(void) {
Queue *q = malloc(sizeof(Queue));
if (!q) {
fprintf(stderr, "Memory allocation failed\n");
exit(EXIT_FAILURE);
}
q->stack_in = stack_create(4);
q->stack_out = stack_create(4);
return q;
}
// Move elements from stack_in to stack_out when needed
void transfer_if_needed(Queue *q) {
if (stack_empty(q->stack_out)) {
while (!stack_empty(q->stack_in)) {
int value = stack_pop(q->stack_in);
stack_push(q->stack_out, value);
}
}
}
// Enqueue
void enqueue(Queue *q, int value) {
stack_push(q->stack_in, value);
}
// Dequeue
int dequeue(Queue *q) {
transfer_if_needed(q);
if (stack_empty(q->stack_out)) {
fprintf(stderr, "Queue is empty\n");
exit(EXIT_FAILURE);
}
return stack_pop(q->stack_out);
}
// Front
int front(Queue *q) {
transfer_if_needed(q);
if (stack_empty(q->stack_out)) {
fprintf(stderr, "Queue is empty\n");
exit(EXIT_FAILURE);
}
return stack_top(q->stack_out);
}
// Check if queue is empty
bool queue_empty(Queue *q) {
return stack_empty(q->stack_in) && stack_empty(q->stack_out);
}
// Destroy queue
void queue_destroy(Queue *q) {
stack_destroy(q->stack_in);
stack_destroy(q->stack_out);
free(q);
}
/* -------------------- Demonstration -------------------- */
int main(void) {
Queue *q = queue_create();
// stack_in
enqueue(q, 10);
enqueue(q, 20);
enqueue(q, 30);
printf("Front element: %d\n", front(q)); // 10 // stack_out
printf("Dequeued: %d\n", dequeue(q)); // 10 // stack_out
printf("Dequeued: %d\n", dequeue(q)); // 20
enqueue(q, 40);
printf("Front element: %d\n", front(q)); // 30
printf("Dequeued: %d\n", dequeue(q)); // 30
printf("Dequeued: %d\n", dequeue(q)); // 40
printf("Queue empty: %s\n", queue_empty(q) ? "true" : "false");
queue_destroy(q);
return 0;
}
/*
run:
Front element: 10
Dequeued: 10
Dequeued: 20
Front element: 30
Dequeued: 30
Dequeued: 40
Queue empty: true
*/
