Skip to content

Instantly share code, notes, and snippets.

@ibeauregard
Last active March 10, 2022 12:38
Show Gist options
  • Save ibeauregard/f6e1679e30c693dd1a45e7aa1d248d6f to your computer and use it in GitHub Desktop.
Save ibeauregard/f6e1679e30c693dd1a45e7aa1d248d6f to your computer and use it in GitHub Desktop.
A queue implementation using only two stacks and whose methods only use standard stack operations (push, pop, peek, size)
import functools
class StackQueue:
def __init__(self):
self.main = []
self.aux = []
def __repr__(self):
return f'StackQueue(self.main={self.main}, self.aux={self.aux})'
def prepare_dequeue(method):
@functools.wraps(method)
def wrapper(self, *args, **kwargs):
if not self.aux:
while self.main:
self.aux.append(self.main.pop())
return method(self, *args, **kwargs)
return wrapper
def enqueue(self, x):
self.main.append(x)
@prepare_dequeue
def dequeue(self):
try:
return self.aux.pop()
except IndexError as exc:
raise Exception('Cannot dequeue from empty queue') from exc
@prepare_dequeue
def peek(self):
try:
return self.aux[-1]
except IndexError as exc:
raise Exception('Cannot peek at empty queue') from exc
def is_empty(self):
return not self.main and not self.aux
del prepare_dequeue
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment