In: Computer Science
Program Description:
Following program uses user-defined linked list to represent a stack. A linked list contains connected nodes which can be traversed sequentially. A node or element or item in linked list contains link to the next node. To create a stack using linked list, a new node is always inserted at front or begining of the linked list. The item in stack is inserted at top or removed from the top only. Initially the stack is empty. Items are pushed on the stack using push method. to remove an item from the top of the stack pop method is used. peek method just returns the data or value from the top of the stack, it doesn't remove the item from the top of the stack.
CODE (PLEASE REFER THE SCREENSHOT FOR CODE INDENTATION):
# Program uses user-defined linked list for demonstrating Stack
# Define Node class
class Node:
# Node class constructor
def __init__(self, value):
self.data = value # data part of the Node
self.next = None # pointer to the next Node, initially pointing to
None
# Define stack class utilizing the Node class
class Stack:
# Stack class constructor to initialize
def __init__(self):
# topOfStack is initialized with dummy node
self.topOfStack = None
self.size = 0 # keeps track of the stack size
# returns stack as string
def __str__(self):
# take a temporary variable to point to topOfStack
cur = self.topOfStack
# out is a string representation of the stack
out = ""
# loop until cur is pointing to valid Node
while cur:
# append the data in the out string
out += str(cur.data) + "->"
# move cur to next node in the list
cur = cur.next
# return the string representation after removing last occurence of
"->"
return out[:-2]
# returns True if stack is empty, otherwise False
def isEmpty(self):
return self.size == 0
# push a value on stack
def push(self, value):
# create a new node
node = Node(value)
# make node's next to point to topOfStack
node.next = self.topOfStack
# reset the topOfStack to newly created node
self.topOfStack = node
# increment the size of the stack
self.size += 1
# return the data of the top node in the stack
def peek(self):
# make sure stack is not empty, if empty raise an exception
if self.isEmpty():
raise Exception("No items in the stack.")
# here means stack is not empty, so return the value from top
node
return self.topOfStack.data
# remove and return value from the stack
def pop(self):
# if stack is empty, cannot delete, raise an exception
if self.isEmpty():
raise Exception("No items in the stack")
# get the topOfStack in a variable to delete/remove
remove = self.topOfStack
# set the topOfStack to next node in the stack
self.topOfStack = self.topOfStack.next
# decrease the size of the stack
self.size -= 1
# return the data part of the removed node
return remove.data
# driver Code to test stack
if __name__ == "__main__":
# a) create an object of Stack class
stack = Stack()
# b) push items on stack
stack.push(5)
stack.push(10)
stack.push(15)
stack.push(20)
stack.push(25)
# c) display the stack contents
print(f"Stack: {stack}")
# d) remove an item from the stack
remove = stack.pop()
# e) display removed item data
print(f"Pop: {remove}")
# f) display the new stack contents
print(f"Stack: {stack}")
OUTPUT: