Question

Implement the stack class (called Stack2) using queue, meaning that the only operations that can be used are the ones defined in the Queue class.

class Queue:
def __init__(self):
self.items = []

def isEmpty(self):
return self.items == []

def enqueue(self, item):
self.items.insert(0, item)

def dequeue(self):
return self.items.pop()

def size(self):
return len(self.items)

The codes to fill:

"""
1. Stack2 class
Implement stack data structure using queue
"""
class Stack2:
def __init__(self):
# Write your definition for __init__ here

def isEmpty(self):
# Write your definition for isEmpty here

def push(self, item):
# Write your definition for push here

def pop(self):
# Write your definition for pop here

def peek(self):
# Write your definition for peek here

def size(self):
# Write your definition for size here

Answer 1

A stack can be implemented using two queues. One main queue will store the elements and other helper queue will help to maintain the ordering. Here, there are two choices: Either to make push costly or pop costly. In this particular program, push is costly while pop is just O(1). Program is given at the end.

Working of given Queue:

The Queue class given in the question inserts elements at the beginning of the queue while deletes elements from the end. Since pop should be O(1), the queue should be maintained in such a way that last inserted element is always at the end. By maintaining this property, pop simply requires to call the dequeue of the main queue.

Different methods implementation:

1. __init__(self) : Since it is a constructor, two queues are initialized: q1 and q2. q1 is the main queue and q2 is the helper queue.

2. push(self, item): This is the main function as this is the function in which the above stated property will be maintained. Suppose that q1 contains the elements in the required order before inserting item. If item is inserted into q1 directly, then item will be at the front of q1 while it must be at the end for pop to work. To resolve this issue, item is first inserted into empty queue q2. Then one by one ,elements from q1 are deleted and inserted into q2. This way the relative ordering is maintained but the elements are now in queue q2 while it is required that they must be in q1. To resolve this, q1 and q2 are swapped.

3. pop(self): Check if q1 is not empty. Then dequeue an element from q1.

4. peek(self): This function returns the last inserted element but does not remove it. Since the Queue class does not contain any method to get an element from some location, (and only Queue operations can be used) there is a roundabout. First dequeue an element from q1. Store it in x. Push it again in the Stack2. Return x. This way the contents of stack2 do not change while the last inserted element(x) can be returnd.

5. size(self): return the size of q1.

Example:

Suppose 1,2 and 3 are inserted in stack2:

Push 1: q1 = [1], q2 = []

Push 2: q1 = [1,2], q2 = [] [2 is inserted into q2 first, then element of q1 (1) is inserted into q2. After that q1 and q2 are swapped]

Push 3: q1 = [1,2,3], q2 = [] [Similar to the above]

Pop: q1 = [1,2] , q2=[] [Dequeue from q1]

Program in Python:

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

"""
1. Stack2 class
Implement stack data structure using queue
"""
# A stack can be implemented using two queues
class Stack2:
    def __init__(self):
        self.q1 = Queue()
        self.q2 = Queue()

    def isEmpty(self):
        return self.q1.isEmpty()

    def push(self, item):
        self.q2.enqueue(item)
        while not self.q1.isEmpty():
            self.q2.enqueue(self.q1.dequeue())
        self.q1, self.q2 = self.q2, self.q1

    def pop(self):
        if self.q1.isEmpty():
            return
        return self.q1.dequeue()

    def peek(self):
        if self.q1.isEmpty():
            return
        x = self.q1.dequeue()
        # Same as pushing x
        # Alternatively can us 'self.push(x)'
        self.q2.enqueue(x)
        while not self.q1.isEmpty():
            self.q2.enqueue(self.q1.dequeue())
        self.q1, self.q2 = self.q2, self.q1
        return x

    def size(self):
        return this.q1.size()

#Testing
st = Stack2()
st.push(0)
st.push(1)
st.push(2)
st.push(3)
print(st.peek())
print(st.pop())
print(st.pop())
print(st.pop())
print(st.pop())

Output:

3
3
2
1
0