Python Program to Implement a Stack using Linked List
Description:
We have to implement Stack using Linked List, In order to do that first we need to implement Linked List after that in the linked list we have to define two method push() and pop(). To implement a linked list you may prefer Python Program to Create a Linked List & Display the Elements in the List.
In the push() method we add a new node with push data at the beginning of the linked list.
In the pop() method we remove the node from the beginning of the linked list and return the data of the removed node. If there is no node then return 'None' and print 'Stack is empty'. Otherwise, just return the data of the removed node.
Finally, we have implemented the stack using a linked list with pop and push functionality.
For better understanding prefer Python3 Program:
class Node:
def __init__(self,data):
self.data = data
self.next = None
class Stack:
def __init__(self):
self.head = None
def display(self):
temp = self.head
print('Element of Stack is:[', end='')
while temp:
print(temp.data, end=", ")
temp = temp.next
print(']')
def push(self, data):
if self.head is None:
self.head = Node(data)
else:
temp = Node(data)
temp.next=self.head
self.head=temp
self.display()
def pop(self):
if self.head is None:
print('Stack is Empty')
return None
else:
popped=self.head.data
self.head=self.head.next
return popped
def main():
l = Stack()
print('1.push\n2.pop\n3.exit')
while 1:
choice=input('Enter your option:')
if choice is '1':
d=int(input('Enter data:'))
l.push(d)
elif choice is '2':
print('poped element is:',l.pop())
l.display()
else:
break
if __name__ == '__main__':
main()
Output:
1.push
2.pop
3.exit
Enter your option:1
Enter data:5
Element of Stack is:[5, ]
Enter your option:1
Enter data:6
Element of Stack is:[6, 5, ]
Enter your option:1
Enter data:7
Element of Stack is:[7, 6, 5, ]
Enter your option:1
Enter data:8
Element of Stack is:[8, 7, 6, 5, ]
Enter your option:1
Enter data:9
Element of Stack is:[9, 8, 7, 6, 5, ]
Enter your option:2
poped element is: 9
Element of Stack is:[8, 7, 6, 5, ]
Enter your option:2
poped element is: 8
Element of Stack is:[7, 6, 5, ]
Enter your option:2
poped element is: 7
Element of Stack is:[6, 5, ]
Enter your option:2
poped element is: 6
Element of Stack is:[5, ]
Enter your option:2
poped element is: 5
Element of Stack is:[]
Enter your option:2
Stack is Empty
poped element is: None
Element of Stack is:[]
Enter your option:3
Time complexity to perform push and pop operation is O(1).
Comments