Implement a stack using single queue
Last Updated :
31 Jul, 2022
We are given queue data structure, the task is to implement stack using only given queue data structure.
We have discussed a solution that uses two queues. In this article, a new solution is discussed that uses only one queue. This solution assumes that we can find size of queue at any point. The idea is to keep newly inserted element always at front of queue, keeping order of previous elements same.
Below are complete steps.
// x is the element to be pushed and s is stack
push(s, x)
1) Let size of q be s.
1) Enqueue x to q
2) One by one Dequeue s items from queue and enqueue them.
// Removes an item from stack
pop(s)
1) Dequeue an item from q
Below is implementation of the idea.
C++
#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 << "No elements\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(10);
s.push(20);
cout << s.top() << endl;
s.pop();
s.push(30);
s.pop();
cout << s.top() << endl;
return 0;
}
|
Java
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(10);
s.push(20);
System.out.println("Top element :" + s.top());
s.pop();
s.push(30);
s.pop();
System.out.println("Top element :" + s.top());
}
}
|
Python3
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("No elements");
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(10);
s.append(20);
print("Top element :" + str(s[-1]));
s.pop();
s.append(30);
s.pop();
print("Top element :" + str(s[-1]));
|
C#
using System;
using System.Collections.Generic;
public class stack
{
Queue<int> q = new Queue<int>();
void push(int val)
{
int size = q.Count;
q.Enqueue(val);
for (int i = 0; i < size; i++)
{
int x = q.Dequeue();
q.Enqueue(x);
}
}
int pop()
{
if (q.Count == 0)
{
Console.WriteLine("No elements");
return -1;
}
int x = q.Dequeue();
return x;
}
int top()
{
if (q.Count == 0)
return -1;
return q.Peek();
}
bool isEmpty()
{
if(q.Count == 0)
return true;
return false;
}
public static void Main(String[] args)
{
stack s = new stack();
s.push(10);
s.push(20);
Console.WriteLine("Top element :" + s.top());
s.pop();
s.push(30);
s.pop();
Console.WriteLine("Top element :" + s.top());
}
}
|
Javascript
<script>
let q = [];
function Push(val)
{
let Size = q.length;
q.push(val);
for (let i = 0; i < Size; i++)
{
let x = q[0];
q.shift();
q.push(x);
}
}
function Pop()
{
if (isEmpty())
{
document.write("No elements" + "</br>");
return -1;
}
let x = q[0];
q.shift();
return x;
}
function Top()
{
if (isEmpty())
return -1;
return q[0];
}
function isEmpty()
{
if(q.length == 0)
return true;
return false;
}
Push(10);
Push(20);
document.write(Top() + "</br>");
Pop();
Push(30);
Pop();
document.write(Top() + "</br>");
</script>
|
Time complexity: O(N) where N is size of stack
Auxiliary Space: O(N)
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...