Problem Statement: Implement stack with push, pop, peek, isEmpty, size methods using a List.
Test Cases
-
Push
- Push on empty stack.
- Push on non-empty stack
-
Pop
- Pop on empty stack —> None.
- Pop on non-empty stack. —> value
-
Peek
- Peek on empty stack —> None.
- Peek on non empty stack. —> value
-
isEmpty
- isEmpty on empty stack —> True
- isEmpty on non-empty stack —> False.
-
Size
- size on empty stack —> None.
- size on non empty stack. —> value
Algorithm
-
Push
- Append new value to end of the list.
-
Pop
- If stack is empty,
- return None
- Else,
- Pop element from the end of list.
- return the element.
-
Peek
- If stack is empty,
- return None
- Else,
- return the last element of the list.
-
isEmpty
- If stack is empty,
- return True
- Else,
- return False
-
Size
- Return the length of the list.
Time and Space complexity
-
Push
- Time complexity: O(1)
- Space complexity: O(1)
-
Pop
- Time complexity: O(1)
- Space complexity: O(1)
-
Peek
- Time complexity: O(1)
- Space complexity: O(1)
-
isEmpty
- Time complexity: O(1)
- Space complexity: O(1)
-
Size
- Time complexity: O(1)
- Space complexity: O(1)
Code
class Stack(object):
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, data):
self.items.append(data)
def pop(self):
if self.isEmpty():
return None
return self.items.pop()
def peek(self):
if self.isEmpty():
return None
return self.items[-1]
def size(self):
return len(self.items)Unit Test
import unittest
from stackLists import Stack
class TestStackLists(unittest.TestCase):
def test_end_to_end(self):
print('Test: Empty stack')
stack = Stack()
self.assertEqual(stack.peek(), None)
self.assertEqual(stack.pop(), None)
print('Test: One element')
stack = Stack()
stack.push(5)
self.assertEqual(stack.size(), 1)
self.assertEqual(stack.pop(), 5)
self.assertEqual(stack.peek(), None)
print('Test: More than one element')
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
self.assertEqual(stack.size(), 3)
self.assertEqual(stack.pop(), 3)
self.assertEqual(stack.peek(), 2)
self.assertEqual(stack.pop(), 2)
self.assertEqual(stack.peek(), 1)
self.assertEqual(stack.isEmpty(), False)
self.assertEqual(stack.pop(), 1)
self.assertEqual(stack.peek(), None)
self.assertEqual(stack.isEmpty(), True)
print('Success: test_end_to_end')
def main():
test = TestStackLists()
test.test_end_to_end()
if __name__ == '__main__':
main()