Problem Statement: Implement a stack using a linked list with it's functions like push, pop, peek, isEmpty.
What is a Stack?
A Stack is a linear data structure, where the elements are stored in a particular order. It follows the LIFO(Last In First Out) order in which the operations are performed.
Test Cases:
- Push
- Push on an empty stack
- Push on a non-empty stack
- Peek
- Peek on an empty stack --> None.
- Peek on a non-empty stack --> value.
- Pop
- Pop from an empty stack --> None.
- Pop from a non-empty stack --> value
- isEmpty
- isEmpty on an empty stack --> True
- isEmpty on a non-empty stack --> False
Algorithm:
- Push
- Create a new node with data
- Set next of new node to top
- Set top to node
- Peek
- if stack is empty,
- return None
- else,
- return value of top
- if stack is empty,
- Pop
- if stack is empty,
- return None
- else,
- save value of top in a temporary variable
- set top to next of top
- return temporary variable
- if stack is empty,
- isEmpty
- if top has value,
- return false
- else,
- return true
- if top has value,
Time and Space Complexity:
- Push
- Time: O(1)
- Space: O(1)
- Pop
- Time: O(1)
- Space: O(1)
- Peek
- Time: O(1)
- Space: O(1)
- isEmpty
- Time: O(1)
- Space: O(1)
- Length
- Time: O(n)
- Space: O(1)
Code
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
class Stack(object):
def __init__(self, top=None):
self.top = top
def __len__(self):
curr = self.top
counter = 0
while curr is not None:
counter += 1
curr = curr.next
return counter
def pop(self):
if self.top is None:
return None
data = self.top.data
self.top = self.top.next
return data
def push(self, data):
self.top = Node(data, self.top)
def peek(self):
return self.top.data if self.top is not None else None
def isEmpty(self):
return self.peek() is None
Unit Tests
import unittest
from stack import Stack, Node
class TestStack(unittest.TestCase):
def test_end_to_end(self):
print('Test: Empty stack')
stack = Stack()
self.assertAlmostEqual(len(stack), 0)
self.assertEqual(stack.peek(), None)
self.assertEqual(stack.pop(), None)
print('Test: One element')
top = Node(5)
stack = Stack(top)
self.assertEqual(len(stack), 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(len(stack), 3)
self.assertEqual(stack.pop(), 3)
self.assertEqual(len(stack), 2)
self.assertEqual(stack.peek(), 2)
self.assertEqual(stack.pop(), 2)
self.assertEqual(len(stack), 1)
self.assertEqual(stack.peek(), 1)
self.assertEqual(stack.isEmpty(), False)
self.assertEqual(stack.pop(), 1)
self.assertEqual(len(stack), 0)
self.assertEqual(stack.peek(), None)
self.assertEqual(stack.isEmpty(), True)
print('Success: test_end_to_end')
def main():
test = TestStack()
test.test_end_to_end()
if __name__ == '__main__':
main()
Happy coding !! 🌟
Top comments (0)