I have this problem with my interview. I was asked to implement a stack using a linked list.
#!python
from linkedlist import LinkedList
# Implement LinkedStack below, then change the assignment at the bottom
# to use this Stack implementation to verify it passes all tests
class LinkedStack(object):
def __init__(self, iterable=None):
"""Initialize this stack and push the given items, if any."""
# Initialize a new linked list to store the items
self.list = LinkedList()
if iterable is not None:
for item in iterable:
self.push(item)
def __repr__(self):
"""Return a string representation of this stack."""
return 'Stack({} items, top={})'.format(self.length(), self.peek())
def is_empty(self):
"""Return True if this stack is empty, or False otherwise."""
return self.list.is_empty()
# TODO: Check if empty
def length(self):
"""Return the number of items in this stack."""
return self.list.size
# TODO: Count number of items
def push(self, item):
"""Insert the given item on the top of this stack.
Running time: O(1) – Just does an append, which is O(1)"""
self.list.append(item)
def peek(self):
"""Return the item on the top of this stack without removing it,
or None if this stack is empty."""
if self.is_empty():
return
return self.list.get_at_index(self.length() - 1)
def pop(self):
"""Remove and return the item on the top of this stack,
or raise ValueError if this stack is empty.
Running time: O(n) – It will always loop through whole list before
finding the item at the end"""
if self.is_empty():
raise ValueError("Cannot pop from an empty stack")
item = self.peek()
self.list.delete(item)
return item
My code passed the following 6 tests. I make sure that my code works a pretty comprehensive following unit test cases, and it passed against all test cases, so the code seems to be working fine.
#!python
from LLstack import Stack
import unittest
class StackTest(unittest.TestCase):
def test_init(self):
s = Stack()
assert s.peek() is None
assert s.length() == 0
assert s.is_empty() is True
def test_init_with_list(self):
s = Stack(['A', 'B', 'C'])
assert s.peek() == 'C'
assert s.length() == 3
assert s.is_empty() is False
def test_length(self):
s = Stack()
assert s.length() == 0
s.push('A')
assert s.length() == 1
s.push('B')
assert s.length() == 2
s.pop()
assert s.length() == 1
s.pop()
assert s.length() == 0
def test_push(self):
s = Stack()
s.push('A')
assert s.peek() == 'A'
assert s.length() == 1
s.push('B')
assert s.peek() == 'B'
assert s.length() == 2
s.push('C')
assert s.peek() == 'C'
assert s.length() == 3
assert s.is_empty() is False
def test_peek(self):
s = Stack()
assert s.peek() is None
s.push('A')
assert s.peek() == 'A'
s.push('B')
assert s.peek() == 'B'
s.pop()
assert s.peek() == 'A'
s.pop()
assert s.peek() is None
def test_pop(self):
s = Stack(['A', 'B', 'C'])
assert s.pop() == 'C'
assert s.length() == 2
assert s.pop() == 'B'
assert s.length() == 1
assert s.pop() == 'A'
assert s.length() == 0
assert s.is_empty() is True
with self.assertRaises(ValueError):
s.pop()
if __name__ == '__main__':
unittest.main()
