Stack is an abstract data type (ADT) which follows the approach of Last In First Out (LIFO). LIFO simply means that the first element inserted into stack will be the last to come out. For example if we say that we have n numbers from 1 to n and we start pushing them onto stack one by one than the first element to be poped will be n and last will be 1.
besides the array implementation, a stack can also be implemented using a linked list. to achieve this we first define the node data structure, or in this case a ‘StackNode’ which is similar to the node of a singly linked list .
when the ‘Stack’ class is instantiated, its top is set to null . every time we push a value onto the stack, a new node is created , we set the next field of this newly created node to point to the top and then after that we set this new node as the new top of the stack .
when pop function is called , we set the new top as the node next to top, thus removing the old top .
to check whether the stack is empty or not , we simply check if the top is ‘None’ or not , if yes we return true.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
# Python program for linked list implementation of stack
from sys import maxsize
# Class to represent a node
class StackNode:
# Constructor to initialize a node
def __init__(self, data):
self.data = data
self.next = None
class Stack:
# Constructor to initialize the root of linked list
def __init__(self):
self.top = None
def isEmpty(self):
return True if self.top is None elseFalse
def push(self, data):
newNode = StackNode(data)
newNode.next = self.top
self.top = newNode
print(“%d pushed to stack”%(data))
def pop(self):
if (self.isEmpty()):
return str(–maxsize –1) #return minus infinite
temp = self.top
self.top = self.top.next
popped = temp.data
return popped
def peek(self):
if self.isEmpty():
return str(–maxsize –1) #return minus infinite
return self.top.data
if __name__ == ‘__main__’:
# Driver program to test above class
stack = Stack()
stack.push(71)
stack.push(82)
stack.push(31)
print(“%d popped from stack” %(stack.pop()))
print(“Top element is %d “ %(stack.peek()))
|
Output:
pushed to stack 71
pushed to stack 82
pushed to stack 31
31 popped from stack