Implement a Stack Using Single Queue

Last Updated on December 14, 2022 by Prepbytes

Problem statement:

We have to build a stack with a single queue.

What is a Stack?

Stack is a linear data structure in which a user can insert and delete an element from the same end which is known as a top.
Stack data structure follows LIFO property i.e. (Last in First out).
In LIFO, the element which was inserted last will be the element which was removed first.
In stack, the process of insertion is called push operation and the process of deletion of the element from the stack is known as pop.
And, we can easily keep track of the last element using a pointer called top.

What is a Queue?

A Queue is a linear data structure in which a user can insert and delete an element on the different end.
The process of insertion in the queue is known as enqueue and the element will be added on the rear end of the queue. The process of deletion in the queue is known as dequeue and the element will be deleted from the front end.

How to implement the Stack using a Single Queue?

The Stack can be easily implemented by making the insertion operation costly. For the push operation i.e. the insertion operation, we will store the count of the elements (n) present in the stack. Then, the new element is inserted at the rear end. After that, we will iterate n times and on each iteration we will remove the first element from the stack and insert it at the rear end of the stack. This will make the insertion (push) operation costly, but will make the deletion (pop) efficient with O(1) time complexity as we are using a queue in which deletion of elements is done from the front end. And on the front end, the newly added element is there. So, on deletion the element which is added atlast will be deleted.

Below are the complete steps:

// Let new_element be the element to be pushed and st be the stack
push(st, new_element)

1. Let the size of the queue be s.
2. Enqueue new_element to queue.
3. One by one dequeue s items from the queue and enqueue them.

// Removes an element from the queue
pop(st)
Dequeue an element from the queue.

#include<bits/stdc++.h>
using namespace std;

class Stack
{
	queue<int>q;
public:
	void push(int val);
	void pop();
	int top();
	bool empty();
};

void Stack::push(int val)
{
	int s = q.size();

	q.push(val);

	for (int i=0; i<s; i++)
	{
		q.push(q.front());

		q.pop();
	}
}

void Stack::pop()
{
	if (q.empty())
		cout << "Queue is Empty!!!\n";
	else
		q.pop();
}

int Stack::top()
{
	return (q.empty())? -1 : q.front();
}

bool Stack::empty()
{
	return (q.empty());
}

int main()
{
	Stack s;
	s.push(5);
	s.push(10);
	cout << s.top() << endl;
	s.pop();
	s.push(15);
	s.pop();
	cout << s.top() << endl;
	return 0;
}

import java.util.LinkedList;
import java.util.Queue;

public class stack
{
	Queue<Integer> q = new LinkedList<Integer>();
	
	void push(int val)
	{
		int size = q.size();
		
		q.add(val);
		
		for (int i = 0; i < size; i++)
		{
			int x = q.remove();
			q.add(x);
		}
	}
	
	int pop()
	{
		if (q.isEmpty())
		{
			System.out.println("No elements");
			return -1;
		}
		int x = q.remove();
		return x;
	}
	
	int top()
	{
		if (q.isEmpty())
			return -1;
		return q.peek();
	}
	
	boolean isEmpty()
	{
		return q.isEmpty();
	}

	public static void main(String[] args)
	{
		stack s = new stack();
		s.push(5);
		s.push(10);
		System.out.println("Top element :" + s.top());
		s.pop();
		s.push(15);
		s.pop();
		System.out.println("Top element :" + s.top());
	}
}

q = []

def append(val):

	size = len(q)

	q.append(val);

	for i in range(size):

		x = q.pop(0);
		q.append(x);

def pop():

	if (len(q) == 0):

		print("Queue is Empty!!!");
		return -1;
	
	x = q.pop(0);
	return x;

def top():

	if(len(q) == 0):
		return -1;
	return q[-1]

def isEmpty():

	return len(q)==0;

if __name__=='__main__':

	s = []

	s.append(5)
	s.append(10)
	print("Top element :", s[-1])
	s.pop()
	s.append(15)
	s.pop()
	print("Top element :", s[-1])

This article tried to discuss implementing a stack using a single queue. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes.