Stacks
STACK
Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
STACK(Using Array)
A stack is one of the most commonly used data structures. A stack is also known as Last-In-First-Out (LIFO) system. In which insertions and deletions can take place only at one end called the top. In the stack terminology the insertion and deletion operation are known as push and pop operations. For Example
Stack can be implemented in following two ways:-
- Stack (Using Array)
- Stack (Using Linked List)
Operations on Stack (Using Array)
- Create stack: – To create an empty stack
- Push:-To push (add or insert) a new element onto the stack
- Pop:-To access and remove the top element of the stack
- Peek:-To access the top element of the stack without removing it
- Isfull: – To check whether the stack is full.
- Isempty: – To check whether the stack empty.
Practice Assignment 1: Python program for implementation of stack
# import maxsize from sys module
from sys import maxsize
# Function to create a stack. It initializes size of stack as 0
def Stack():
mystack = []
return mystack
# Stack is empty when stack size is 0
def isEmpty(mystack):
return len(mystack) == 0
# Function to add an item to stack. It increases size by 1
def push(stack, item):
stack.append(item)
print(item + ” pushed to stack “)
# Function to remove an item from stack. It decreases size by 1
def pop(mystack):
if (isEmpty(mystack)):
return str(-maxsize -1) # return minus infinite
return mystack.pop()
# Function to return the top from stack without removing it
def peek(mystack):
if (isEmpty(mystack)):
return str(-maxsize -1) # return minus infinite
return mystack[len(mystack) – 1]
# Main program
stack = Stack()
push(mystack, str(10))
push(mystack, str(20))
print(pop(mystack) + ” popped from stack”)
STACK(Using Linked List)
A stack is one of the most commonly used data structures. A stack is also known as Last-In-First-Out (LIFO) system. In which insertions and deletions can take place only at one end called the top. In the stack terminology the insertion and deletion operation are known as push and popoperations. A stack represented using Linked List is also known as Linked Stack. The array based representation of stack suffers from the following limitations:-
- Size of array must be known in advance
- Stack, which is an abstract data type, can not be full. It is always possible to push an element onto stack. Therefore, representing stack as an array prohibits the growth of stack beyond the finite number of elements
Operations on Stack (Using Linked List):
The following operations can be performed on stack:-
- Createstack: – To create an empty stack
- Push:-To push (add or insert) a new element onto the stack
- Pop:-To access and remove the top element of the stack
- Peek:-To access the top element of the stack without removing it
- Isempty: – To check whether the stack empty.
- Dispose:- To dispose a stack
Practice Assignment 2: Python program for linked list implementation of stack
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.head = None
def isEmpty(self):
return True if self.head is None else False
def push(self, data):
new_Node = StackNode(data)
new_Node.next = self.head
self.head = new_Node
print “% d pushed to stack” %(data)
def pop(self):
if (self.isEmpty()):
return float(“-inf”)
temp = self.head
self.head = self.head.next
popItem = temp.data
return popItem
def peek(self):
if self.isEmpty():
return float(“-inf”)
return self.head.data
# Main program
stack = Stack()
stack.push(10)
stack.push(20)
print “% d popped from stack” %(stack.pop())
print “Top element is % d ” %(stack.peek())