[SOLVED] CS python

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

Thats 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 dictionarys 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 youre
NOT allowed to modify the type contract of any of the given methods and
attributes. Youre 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