Implement Queue Using Stacks

Let's start by understanding the problem statement of implementing queue using stack.

The problem to solve is that you are given a stack data structure with operations such as push and pop, and your task is to create a queue from this operation.

Hint:

For a queue one may think that it uses a FIFO rule so how to use it by using the principles of a stack that uses a LIFO rule, the idea is very simple one may use two stacks for popping out the data elements from one stack and putting it into another stack and then popping it out from the second stack as in the second stack the very first element will be the last element and there is no change in the property of queue, hence the queue is successfully implemented with its basic principles i.e., FIFO rule.

Quick Think:

For implementing a queue using a stack, we need to ponder over the following points:-

1. While maintaining two different stacks we need to take care of the situation where the first stack is empty and the second stack is full, so we need to check this condition while popping out the values, we need to push the elements to the other stack until and unless the other stack is not fully empty and then pop out the first element from the other stack.
2. When both the stacks are empty then there are no elements to be popped out and this is the condition of the underflow.
3. While popping out the values we need to check a condition when the stack is fully empty, this is the condition for the underflow for any single stack.
4. While pushing the elements into the stack one needs to check that the node returned is NULL then this is the condition of overflow.

Algorithm:

We will create four functions, namely:-

1. The push function: This function will take care of the data values to be pushed into the stack.
2. The pop function: This function will take care of popping out the values from the stack.
3. The enqueue function: This function takes care of the enquing operation, whose base will be the push operation taking place with a stack.
4. The dequeue function: This function takes care of removing the data elements from the queue whose base operation is the pop function which is responsible for popping out the elements from one stack and putting it to the other one and popping them again from the other stack to finally pop out the first element.

Now, the basic properties of these functions will be as follows:-

1. The push function: In the push function we will allocate memory to the node and push the data into it and initialize the pushed node as the top node of the current stack 1 before pushing an after-memory allocation we need to check whether the value of the node is NULL or not, if not then push the node else print overflow and exit the operation.
2. The pop function: In the pop function we need to check whether the top pointer to the node is not NULL if it is NULL then print stack underflow and exit the operation else we will define a temporary node and store the first node from stack 1 increment the pop pointer by one and delete the top node and return the data value of the top node.
3. The enqueue function: This function will call the push function with the arguments as the pointer to the top node and the data value to be inserted into the queue.
4. The dequeue function: This function will check if both the stacks i.e., stack 1 and stack 2 are empty the print stack underflow and end the operation else check if stack 2 is empty or not if ‘yes’ then we need to pop all the data elements out from the stack 1 to pop out the last element from the stack 1, else just pop out the first data element from the stack 2 and print its value.

Implementation Of The Above Algorithm:

Now let's see the implementation of the above algorithm.

/*Program to implement a queue using two stacks */ 
#include <stdio.h>
#include <stdlib.h>

/*structure of a stack node */
struct stack_node
{
	int data;
	struct stack_node * next;
};

/*Function to push an item to stack*/
void push(struct stack_node **top_ref, int data)
{
	/*allocate node */
	struct stack_node *node = (struct stack_node *) malloc(sizeof(struct stack_node));
	if (node == NULL)
	{
		printf("Stack overflow \n");
		getchar();
		exit(0);
	}

	/*put in the data */
	node->data = data;

	/*link the old list off the new node */
	node->next = (*top_ref);

	/*move the head to point to the new node */
	(*top_ref) = node;
}

/*Function to pop an item from stack*/
int pop(struct stack_node **top_ref)
{
	int res;
	struct stack_node * top;

	/*If stack is empty then error */
	if (*top_ref == NULL)
	{
		printf("Stack underflow \n");
		getchar();
		exit(0);
	}
	else
	{
		top = *top_ref;
		res = top->data;
		*top_ref = top->next;
		free(top);
		return res;
	}
}

/*structure of queue having two stacks */
struct queue_node
{
	struct stack_node * stack1;
	struct stack_node * stack2;
};

/*Function to enqueue an item to queue */
void enqueue(struct queue_node *q, int x)
{
	push(&q->stack1, x);
}

/*Function to dequeue an item from queue */
int dequeue(struct queue_node *q)
{
	int x;
	/*If both stacks are empty then error */
	if (q->stack1 == NULL && q->stack2 == NULL)
	{
		printf("Q is empty");
		getchar();
		exit(0);
	}

	/*Move elements from stack1 to stack 2 only if
	stack2 is empty */
	if (q->stack2 == NULL)
	{
		while (q->stack1 != NULL)
		{
			x = pop(&q->stack1);
			push(&q->stack2, x);
		}
	}

	x = pop(&q->stack2);
	return x;
}

/*Driver function to test the above algorithm */
int main()
{
	/*Create a queue with items 1 2 3*/
	struct queue_node *q = (struct queue_node *) malloc(sizeof(struct queue_node));
	q->stack1 = NULL;
	q->stack2 = NULL;
	enqueue(q, 10);
	enqueue(q, 21);
	enqueue(q, 34);

	enqueue(q, 50);

	/*Dequeue items */
	printf("%d ", dequeue(q));
	printf("%d ", dequeue(q));
	printf("%d ", dequeue(q));

	getchar();
}

The time complexity of the above algorithm: O(n^2).
The output of the above algorithm will be: 10 21 34.

Explanation Of The Above Algorithm:

Let us consider a queue where the data elements 10, 21, 34 and 50 will be inserted as shown in the above program.

We can achieve the following operation with a stack as well in the following ways as described below:-

• enqueue function is called with the argument of the queue structure and the data element, here as 10.
• Here in the enqueue function, the data element is pushed into the stack by calling another function push where the address of the stack1 with the data element to be pushed is passed as an argument.

• During insertion into the stack, a node is created, and since this created node is not NULL so the node with data 10 is pushed into the stack structure as shown in the above diagram.

• Now similarly the other nodes with data 21 34 and 50 are pushed into the stack as a node with data 10 is pushed as shown in the diagram above.
• Now the function dequeue is called with the argument as the structure of the queue.

• Now in the dequeue function, we have the stack 2 is NULL but the stack 1 is not NULL and hence the stack is not underflow, so we check now that the stack 2 is NULL or not, since here we see that stack 2 is NULL, so the condition is ‘True’ and we now pop all the data elements from stack 1 to stack 2 until stack 1 is empty and when stack 1 becomes empty as shown in the above diagram.

• Now we pop the first element from stack 2 and return its value, and we get our first output as 10 as shown in the above diagram.

• Now similarly the dequeue function is called two more times and hence the program gets terminated, and we get our final output as shown in the above diagram.