Stacks using Single Linked Lists - Python Implementation

August 15, 2018 2 min read Python Single Linked List Stacks

Stacks implementation in Python using Single Linked List :-

# Stack ADT implementation using Lists
# S.push(e)    : Add element 'e' to the top of Stack S
# S.pop()      : Remove element from the top of Stack S and return the removed element, error if empty
# S.top()      : Return the reference of the top element of S without removing it, error if empty
# S.isEmpty() : Return True if stack is empty
# len(S)       : Return number of elements in Stack S

class EmptyStackException(Exception):
    pass

class Node(object):
    __slot__ = "data", "next"
    def __init__(self,data,next):
        self.data = data
        self.next = next

class Stack(object):
    def __init__(self):
        self.head = None
        self.size = 0
    
    def __len__(self):
        return self.size

    def isEmpty(self):
        return self.size == 0
    
    def push(self,elem):
        self.head = Node(elem,self.head)
        self.size += 1

    def pop(self):
        if self.isEmpty():
            raise EmptyStackException("No Elements in Stack")
        retNodeData= self.head.data
        self.head = self.head.next
        self.size -= 1
        return retNodeData

    def top(self):
        if self.isEmpty():
            raise EmptyStackException("No Elements in Stack")
        retNodeData= self.head.data
        return retNodeData
import unittest
from single_linked_lists_stacks import *

class TestStacks(unittest.TestCase):
    def setUp(self):
        self.S = Stack()
  
    def test_emptyStack(self):
        self.assertEqual(len(self.S),0)
        self.assertTrue(self.S.isEmpty())
        with self.assertRaises(EmptyStackException) as cm:
            self.S.pop()
        expected_msg = "No Elements in Stack"
        self.assertEquals(cm.exception.message, expected_msg)
        with self.assertRaises(EmptyStackException) as cm:
            self.S.top()
        expected_msg = "No Elements in Stack"
        self.assertEquals(cm.exception.message, expected_msg)

    def test_push_pop_top_len(self):
        self.S.push('A')
        self.S.push('B')
        self.assertEqual(len(self.S),2)
        self.assertFalse(self.S.isEmpty())
        self.assertEqual(self.S.top(),'B')
        self.assertEqual(len(self.S),2)
        self.assertEqual(self.S.pop(),'B')
        self.assertEqual(len(self.S),1)
        self.S.push('C')
        self.assertEqual(self.S.pop(),'C')
        self.assertEqual(self.S.pop(),'A')
        self.assertEqual(len(self.S),0)


if __name__ == '__main__':
    unittest.main(verbosity=2)

Comments