Featured

    Featured Posts

Stack Data Structure

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=" ");

 





































www.CodeNirvana.in

Powered by Blogger.

About

Site Links

Popular Posts

Translate

Total Pageviews