Stack
Ø Stack is linear data structure. In stack addition of new data item and deletion of already existing data item is done from only one end, known as top. Working of stack on the basis of Last-in-First-out (LIFO) principal, it means last entered item remove first.
Real life example of stack
Ø A most popular example of stack is plates in marriage party. Fresh plates are pushed onto to the top and popped from the top.
When we have required using Stack data structure
§ If you want to add an element and remove an element in a particular order where Every time an element is added, it goes on the top of the stack and the only element that can be removed is the element that is at the top of the stack then we have required using of stack data structure.
Basic features of Stack
§
Stack
is an ordered list of similar data type.
§
Stack
follows LIFO (Last in First out) principle or we can say Stack follows FILO
(First in Last out) Principle.
§ In Such a way we can say that the stack is a memory in which one end is open and one end is closed .i.e. means that any operation in the stack can be done with only one end.
§ The end points from which the insertion will take place will be deletion by the same end points.
§ In the stack, we will assume a top variable which will always point to the element that will be present in the top most of the stack.
§ When we add a new element to the stack, it is called the push operation of stack.
§ When we delete a new element in the stack, it is called pop operation of stack.
§ Both insertion and removal are allowed at only one end of Stack called Top.
§ If the stack is full and then we insert a new element, then it is called stack overflow condition. This means that we cannot insert new element from the stack at this time because the stack is full.
§ If the stack is empty and then we want to delete a new element, then it is called the stack Underflow condition. This means that we cannot delete the element from the stack at this time because the stack is empty.
Stack
Operation
In stack data structure mainly perform two operations; push and pop
Push:
§
Inserting a new element in the
top of stack. If the stack is full, then it is said to be an Overflow
condition.
Algorithm for PUSH operation
§ Check if the stack is full or not.
§ If the stack is full, then display "overflow" message and exit the program.
§ If the stack is not full, then increment the top and add the element.
Pop: Removes an item from the top stack.
Algorithm for POP operation
§ Check if the stack is empty or not.
§ If the stack is empty, then display "underflow" message and exit the program.
§
If the stack is not empty, then print
the element at the top and decrement the top.
·
Peek or
Top: Returns top element of stack.
· isEmpty: Returns true if stack is empty, else false.
Stack Implementation Using Array
import java.util.Scanner
public class Stack
static Scanner sc=new Scanner(System.in);
static int stack[],top=-1, size;;
static
{
Stack.create();
}
public static void main(String[] args)
{
int ch=0;
int item;
while(true)
{
System.out.println("1.Push");
System.out.println("2.Pop");
System.out.println("3.Peek");
System.out.println("4.traverse");
System.out.println("5.Quit");
System.out.println("Enter your choice");
ch=sc.nextInt();
switch(ch)
{
case 1:
System.out.println("Enter Element: ");
item=sc.nextInt();
Stack.push(item);
break;
case 2:
item=Stack.pop();
if(item==0)
{
System.out.println("Stack is underflow..");
}
else
{
System.out.println("popped element "+item);
}
break;
case 3:
item=Stack.peek();
if(item==0)
{
System.out.println("Stack is underflow..");
}
else
{
System.out.println("peeked element "+item);
}
break;
case 4:Stack.traverse();break;
case 5:System.exit(1);
default:
System.out.println("Invalid choice");
}
}
}
static void create()
{
System.out.println("plz enter stack size");
size=Stack.sc.nextInt();
Stack.stack=new int[size];
System.out.println("Stack Created with Size : "+size);
}
// function to insert data into stack
static void push(int item)
{
if(Stack.isFull())
{
System.out.println("Stack is overflow!!..");
}
else
{
stack[++top]=item;
}
}
static boolean isFull()
{
if(top==size-1)
{
return true;
}
else
{
return false;
}
}
// function to remove data from the top of the stack
static int pop()
{
if(Stack.isEmpty())
{
return 0;
}
else
{
return stack[top--];
}
}
static int peek()
{
if(Stack.isEmpty())
{
return 0;
}
else
{
return stack[top];
}
}
//function to check if stack is empty
static boolean isEmpty()
{
if(top==-1)
return true;
else
return false;
}
static void traverse()
{
if(Stack.isEmpty())
{
System.out.println("Stack is empty..");
}
else
{
System.out.println("Element of Stack...");
for(int i=top;i>=0;i--)
{
System.out.print(stack[i]+" ");
}
}
}
}
Stack Implementation Using Python
class Stack:def __init__(self,size):
self.__maxSize=size
self.__stackList=[0]*size self.__top=-1
#Check whether Stack is Empty or not
def isEmpty(self):
return self.__top == -1;
#Check whether Stack is Full or not
def isFull(self):
return self.__top == self.__maxSize;
def push(self,value):
if (self.isFull()):
print("Stack is full..");
return;
self.__top+=1
self.__stackList[self.__top] = value;
#Return and remove top element
def pop(self):
if (not self.isEmpty()):
topValue=self.__stackList[self.__top]
self.__top-=1
return topValue
else:
print("Stack is empty...");
return -1;
#Return top element
def peek(self):
if (not self.isEmpty()):
return self.__stackList[self.__top];
else:
print("Stack is empty...");
return -1;
#Creating a Stack
stack=Stack(10)
#pushing first 10 values into stack
for i in range(1,11):
stack.push(i)
for i in range(1,11):
print(stack.pop(),end=" ");
