Implementing Stack using Queues in C Programming

Stack using Queues in C Programming

A stack is an important data structure that follows the Last In, First Out (LIFO) principle, where the last element added to the stack is the first one to be removed. Stacks are commonly used for implementing functions like push, pop, peek, etc., in computer programs. However, stacks can be implemented using other data structures such as queues. In this article, we will explore how to implement a stack using two queues in C programming.

Queue Data Structure in C

Before diving into the stack implementation using queues, let's first understand the basics of a queue data structure in C. A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where the first element added to the queue is the first one to be removed. A queue can be implemented using an array or a linked list.

In C, we can implement a queue using an array or a linked list. Here's an example of how to implement a queue using an array:

#include <stdio.h>
#define MAX_SIZE 10

int queue[MAX_SIZE];
int front = -1;
int rear = -1;

void enqueue(int x) {
    if (rear == MAX_SIZE - 1) {
        printf("Queue is full\n");
        return;
    }
    if (front == -1) {
        front = 0;
    }
    queue[rear] = x;
    rear++;
}

int dequeue() {
    if (front == -1 || front > rear) {
        printf("Queue is empty\n");
        return -1;
    }
    int x = queue[front];
    front++;
    if (front > rear) {
        front = rear = -1;
    }
    return x;
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    printf("%d dequeued from queue\n", dequeue());
    printf("%d dequeued from queue\n", dequeue());
    printf("%d dequeued from queue\n", dequeue());
    return 0;
}

In this example, we have defined an array queue of size MAX_SIZE to store the elements of the queue. We have also defined two pointers front and rear to keep track of the front and rear positions of the queue.

The enqueue function is used to add an element to the rear of the queue. If the queue is full, it returns an error message. The dequeue function is used to remove an element from the front of the queue. If the queue is empty, it returns an error message.

Implementing a Stack using Two Queues in C

Now that we have understood the basics of a queue, let's see how we can implement a stack using two queues in C. This technique is called the "queue-with-two-stacks" technique.

We will implement two queues queue1 and queue2. The queue1 will be used as the main queue, and queue2 will be used as an auxiliary queue. We will perform all the stack operations like push, pop, peek, etc., on queue1. Whenever we want to perform a push operation on queue1, we will first move all the elements from queue1 to queue2. Then, we will add the new element to queue1. Finally, we will move all the elements from queue2 back to queue1. This process may seem time-consuming, but it works correctly and follows the LIFO principle.

Here's an example of how to implement a stack using two queues in C:

#include <stdio.h>
#define MAX_SIZE 10

int queue1[MAX_SIZE];
int queue2[MAX_SIZE];
int front1 = -1;
int rear1 = -1;
int front2 = -1;
int rear2 = -1;

void push(int x) {
    if (rear1 == MAX_SIZE - 1) {
        printf("Stack is full\n");
        return;
    }
    if (front1 == -1) {
        front1 = 0;
    }
    queue1[rear1] = x;
    rear1++;
}

int pop() {
    if (front1 == -1) {
        printf("Stack is empty\n");
        return -1;
    }
    int x = queue1[front1];
    front1++;
    if (front1 > rear1) {
        front1 = rear1 = -1;
    }
    return x;
}

void peek() {
    if (front1 == -1) {
        printf("Stack is empty\n");
        return;
    }
    printf("Top element is %d\n", queue1[front1]);
}

void move_queue(int *q1, int *q2, int *front1, int *rear1, int *front2, int *rear2) {
    while (*front1 != -1) {
        *q2[*rear2] = *q1[*front1];
        (*rear2)++;
        (*front1)++;
    }
    *front1 = *rear1 = -1;
    *front2 = 0;
    *rear2 = 0;
}

int main() {
    push(1);
    push(2);
    push(3);
    peek();
    pop();
    peek();
    pop();
    pop();
    return 0;
}

In this example, we have defined two queues queue1 and queue2 of size MAX_SIZE to store the elements of the stack. We have also defined four pointers front1, rear1, front2, and rear2 to keep track of the front and rear positions of the queues.

The push function is used to add an element to the top of the stack. It first checks if the stack is full and then adds the element to queue1. The pop function is used to remove an element from the top of the stack. It first checks if the stack is empty and then removes the element from `