This is a Python program to implement a stack using a single queue.
Problem Description
The program creates a stack using a single queue and allows the user to perform push and pop operations on it.
Problem Solution
1. Create a class Queue.
2. Define methods enqueue, dequeue, is_empty and get_size inside the class Queue.
3. Create a class Stack with instance variable q initialized to an empty queue.
4. Pushing is done by enqueuing data to the queue.
5. To pop, the queue is dequeued and enqueued with the dequeued element n – 1 times where n is the size of the queue. This causes the the last element added to the queue to reach the rear of the queue. The queue is dequeued one more time to get the item to be returned.
6. The method is_empty returns True iff the queue is empty.
Program/Source Code
Here is the source code of a Python program to implement a stack using a single queue. The program output is shown below.
class Stack:
def __init__(self):
self.q = Queue()
def is_empty(self):
return self.q.is_empty()
def push(self, data):
self.q.enqueue(data)
def pop(self):
for _ in range(self.q.get_size() – 1):
dequeued = self.q.dequeue()
self.q.enqueue(dequeued)
return self.q.dequeue()
class Queue:
def __init__(self):
self.items = []
self.size = 0
def is_empty(self):
return self.items == []
def enqueue(self, data):
self.size += 1
self.items.append(data)
def dequeue(self):
self.size -= 1
return self.items.pop(0)
def get_size(self):
return self.size
s = Stack()
print(‘Menu’)
print(‘push
print(‘pop’)
print(‘quit’)
while True:
do = input(‘What would you like to do? ‘).split()
operation = do[0].strip().lower()
if operation == ‘push’:
s.push(int(do[1]))
elif operation == ‘pop’:
if s.is_empty():
print(‘Stack is empty.’)
else:
print(‘Popped value: ‘, s.pop())
elif operation == ‘quit’:
break
Runtime Test Cases
Case 1:
Menu
push
pop
quit
What would you like to do? push 3
What would you like to do? push 5
What would you like to do? pop
Popped value: 5
What would you like to do? pop
Popped value: 3
What would you like to do? pop
Stack is empty.
Case 2:
Menu
push
pop
quit
What would you like to do? push 1
What would you like to do? push 2
What would you like to do? push 3
What would you like to do? push 4
What would you like to do? pop
Popped value: 4
What would you like to do? pop
Popped value: 3
What would you like to do? pop
Popped value: 2
What would you like to do? pop
Popped value: 1
What would you like to do? pop
Stack is empty.
What would you like to do? quit