The following is my implementation of a stack using a linked list.
class EmptyStackError(Exception):
def __init__(self):
super().__init__("Stack is empty: Invalid Operation!")
class LinkedList:
class _Node:
def __init__(self, data, next_node=None):
self.data = data
self.next_node = next_node
def __init__(self):
self._head = None
self._tail = None
def add_first(self, data):
""" Add data to the beginning of the linked list"""
node = self._Node(data)
if not self._head and not self._head:
self._head = self._tail = node
return
node.next_node = self._head
self._head = node
def add_last(self, data):
""" Add data to the end of the linked list """
node = self._Node(data)
if not self._head and not self._tail:
self._head = self._tail = node
return
self._tail.next_node = node
self._tail = node
def remove_last(self):
""" Remove the last element in the linked list """
if not self._head and not self._tail: # if linked list is empty
raise EmptyStackError
elif self._head is self._tail: # if only one element
data = self._head.data # or data of tail
self._head = self._tail = None
return data
data = self._tail.data
current = self._head
while current.next_node.next_node:
current = current.next_node
current.next_node = None
self._tail = current
return data
def remove_first(self):
""" Remove the first element in the linked list """
if not self._head and not self._tail: # if linked list is empty
raise EmptyStackError
elif self._head is self._tail: # if only one element
data = self._head.data
self._head = self._tail = None
return data
data = self._head.data
self._head = self._head.next_node
return data
def __str__(self):
if not self._head and not self._tail:
return "Stack is empty!!"
items = []
current = self._head
while current:
items.append(current.data)
current = current.next_node
return " ".join([str(i) for i in items])
class Stack:
""" A stack implementation using a linked list
Note: The reason add_first and remove_first are using for push and pop respectively is to keep them O(1).
If adding and removing last were used, then remove last would O(n).
This is because deleting the tail would require the traversal of the linked list to delete the last element.
"""
def __init__(self):
self.items = LinkedList()
def push(self, data):
self.items.add_first(data)
def pop(self):
data = self.items.remove_first()
return data
def peek(self):
data = self.items.remove_first()
self.items.add_first(data)
return data
def __str__(self):
string = self.items.__str__()
return string
Is there anything I need to improve? whether it's style or logic.
Can you find any bugs? Whether in the linked list or the stack.
My basic tests:
import pytest
def test_push():
""" This is depending on another method """
stack = Stack()
stack.push(5)
assert stack.peek() == 5
def test_pop():
stack = Stack()
stack.push(5)
data = stack.pop()
assert data == 5
def test_empty_pop():
stack = Stack()
with pytest.raises(EmptyStackError):
stack.pop()
def test_peek():
stack = Stack()
stack.push(5)
assert stack.peek() == 5
def test_empty_peek():
stack = Stack()
with pytest.raises(EmptyStackError):
stack.peek()
test_push()
test_pop()
test_empty_pop()
test_peek()
test_empty_peek()