“””
QUESTION 3: ADT
6 marks, ~15 minutes
In this question, we want to implement an ADT called QStack, which stores a
collection of integers and supports the following operations.
– push(): push a new item onto the QStack
– pop(): pop and return the newest item from the QStack
– dequeue(): remove and return the oldest item from the QStack
That’s right: we want QStack to behave like both Stack and Queue. Furthermore,
ALL above operations must have O(1) time complexity, i.e., constant time.
You are required to use a Python dictionary (_items) to implement this class.
You may assume that Python dictionary’s lookup and insert operations both have
O(1) complexity, i.e., they take constant time.
TODO: Complete the implementation of the QStack below.
You may add new instance variables or helper methods if necessary, but you’re
NOT allowed to modify the type contract of any of the given methods and
attributes. You’re NOT allowed to add any import.
Documentation are not required for the marking of this question; however, it may
help the TAs understand your code better.
“””
from typing import Dict, Optional
class QStack:
“””
An ADT that supports both Stack and Queue operations.
“””
_items: Dict[int, int]
def __init__(self) -> None:
“””
Initialize an empty QStack
“””
self._items = dict()
def push(self, item: int) -> None:
“””
push a new item onto the QStack
“””
pass
def pop(self) -> Optional[int]:
“””
pop and return the newest item in the QStack
return None if the QStack is empty
“””
pass
def dequeue(self) -> Optional[int]:
“””
remove and return the oldest item in the QStack
return None if the QStack is empty
“””
pass