Skip to content

Instantly share code, notes, and snippets.

@theeluwin

theeluwin/queue_with_two_stacks.py

Created November 25, 2025 08:20
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save theeluwin/e3a144555d259676ef50cfd9564d0f06 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save theeluwin/e3a144555d259676ef50cfd9564d0f06 to your computer and use it in GitHub Desktop.
Download ZIP
Queue with two stacks
Raw
queue_with_two_stacks.py
from typing import (
Any,
Optional,
)
class Node:
def __init__(self, value: Any) -> None:
self.value = value
self.prev: Optional[Node] = None
self.next: Optional[Node] = None
class DoublyLinkedList:
def __init__(self) -> None:
self._head: Optional[Node] = None
self._tail: Optional[Node] = None
self._size = 0
def is_empty(self) -> bool:
return self._size == 0
def push_back(self, value: Any) -> None:
node = Node(value)
if self._head is None:
self._head = node
if self._tail is None:
self._tail = node
else:
node.prev = self._tail
self._tail.next = node
self._tail = node
self._size = self._size + 1
def pop_back(self) -> Any:
if self._tail is None:
raise IndexError
node = self._tail
value = node.value
if node.prev is not None:
self._tail = node.prev
self._tail.next = None
else:
self._tail = None
self._head = None
del node
self._size = self._size - 1
return value
def push_front(self, value: Any) -> None:
node = Node(value)
if self._tail is None:
self._tail = node
if self._head is None:
self._head = node
else:
node.next = self._head
self._head.prev = node
self._head = node
self._size = self._size + 1
def pop_front(self) -> Any:
if self._head is None:
raise IndexError
node = self._head
value = node.value
if node.next is not None:
self._head = node.next
self._head.prev = None
else:
self._head = None
self._tail = None
del node
self._size = self._size - 1
return value
def __iter__(self):
node = self._head
while node is not None:
yield node.value
node = node.next
def __len__(self):
return self._size
def print(self) -> None:
print(f"({self._size})", end='')
print('[ ', end='')
for value in self:
print(value, end=' ')
print(']')
class Stack:
def __init__(self):
self._dll = DoublyLinkedList()
def is_empty(self) -> bool:
return self._dll.is_empty()
def push(self, value: Any) -> None:
self._dll.push_back(value)
def pop(self) -> Any:
return self._dll.pop_back()
def __iter__(self):
for value in self._dll:
yield value
def __len__(self):
return len(self._dll)
def print(self) -> None:
self._dll.print()
class Queue:
"""
say: [1, 2, 3], []
pop(): [], [3, 2, 1] -> [], [3, 2, 1] -> [], [3, 2] (1)
push(4): [], [3, 2] -> [2, 3], [] -> [2, 3, 4], []
push(5): [2, 3, 4], [] -> [2, 3, 4, 5], []
pop(): [2, 3, 4, 5], [] -> [], [5, 4, 3, 2] -> [], [5, 4, 3] (2)
pop(): [], [5, 4, 3] -> [], [5, 4] (3)
"""
def __init__(self):
self._push_stack = Stack()
self._pop_stack = Stack()
self._is_push_mode = True
def _pour(self) -> None:
if self._is_push_mode is True:
from_stack = self._push_stack
to_stack = self._pop_stack
else:
from_stack = self._pop_stack
to_stack = self._push_stack
while True:
try:
value = from_stack.pop()
except IndexError:
break
to_stack.push(value)
self._is_push_mode = not self._is_push_mode
def push(self, value: Any) -> None:
if not self._is_push_mode:
self._pour()
self._push_stack.push(value)
def pop(self) -> Any:
if self._is_push_mode:
self._pour()
return self._pop_stack.pop()
def __len__(self):
return len(self._push_stack) + len(self._pop_stack)
def print(self):
self._push_stack.print()
self._pop_stack.print()
if __name__ == '__main__':
print("DLL test")
print()
dll = DoublyLinkedList()
dll.print()
print()
print("push back 1")
dll.push_back(1)
dll.print()
print()
print("push back 2")
dll.push_back(2)
dll.print()
print()
print("push back 3")
dll.push_back(3)
dll.print()
print()
print("pop back")
print(dll.pop_back())
dll.print()
print()
print("pop back")
print(dll.pop_back())
dll.print()
print()
print("pop back")
print(dll.pop_back())
dll.print()
print()
print("push front 1")
dll.push_front(1)
dll.print()
print()
print("push front 2")
dll.push_front(2)
dll.print()
print()
print("push front 3")
dll.push_front(3)
dll.print()
print()
print("pop front")
print(dll.pop_front())
dll.print()
print()
print("pop front")
print(dll.pop_front())
dll.print()
print()
print("pop front")
print(dll.pop_front())
dll.print()
print()
print()
print("Queue test")
print()
queue = Queue()
print("push 1")
queue.push(1)
queue.print()
print()
print("push 2")
queue.push(2)
queue.print()
print()
print("push 3")
queue.push(3)
queue.print()
print()
print("pop")
print(queue.pop())
queue.print()
print()
print("push 4")
queue.push(4)
queue.print()
print()
print("pop")
print(queue.pop())
queue.print()
print()
print("push 5")
queue.push(5)
queue.print()
print()
print("pop")
print(queue.pop())
queue.print()
print()
print("pop")
print(queue.pop())
queue.print()
print()
print("pop")
print(queue.pop())
queue.print()
print()
print()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment