STACK Implementation using Static Array

One of the most important linear data structure is stack.

A stack is defined as an ordered collection of data items in which insertion and deletion takes place from one end of the stack called as “top”.

Stack is also known as restricted list.

Stack maintains a pointer called TOP, which keeps a track of topmost elements of the stack.

Any insertion or deletion should be based on the value of top.

In stack the elements are removed in the reverse order of that in which they were added to the stack i.e., last element inserted is to be deleted first. So, it is called LIFO(Last In First Out).

Example: The way the books are arranged on a table.

Consider an array of 6 elements A,B,C,D,E,F.

F

E

D

C

B

A

1. It represents stack of 6 elements.

2. The top most element in the stack is ‘F’.

3. If we want to delete ‘C’, only F,E and D has to be deleted because it is LIFO.

BASIC  OPERATIONS:

The basic operations are insertion,deletion,display.But in stack special terms are given for insert and delete. 

i.e., push is for insert

Pop is for delete

PUSH: Inserting or adding elements into stack is called “push”.

POP: Deleting or removing elements from the stack is called “pop”.

Working of Stack

Stack works on the LIFO pattern.

PUSH operation

The steps involved in the PUSH operation is given below:

Before inserting an element in a stack, we check whether the stack is full.

If we try to insert the element in a stack, and the stack is full, then the overflow condition occurs.

When we initialize a stack, we set the value of top as -1 to check that the stack is empty.

When the new element is pushed in a stack, first, the value of the top gets incremented, i.e., top=top+1, and the element will be placed at the new position of the top.

The elements will be inserted until we reach the max size of the stack.

POP operation

The steps involved in the POP operation is given below:

Before deleting the element from the stack, we check whether the stack is empty.

If we try to delete the element from the empty stack, then the underflow condition occurs.

If the stack is not empty, we first access the element which is pointed by the top

Once the pop operation is performed, the top is decremented by 1, i.e., top=top-1.

ANIMATION VIDEO LINK OF STACK :

https://www.youtube.com/watch?v=-KQpk-dIA8s

IMPLEMENTING STACK USING ARRAY:

Since stack is a collection of same type of elements so we can take array of implementing stack. But in arrays any element can be added or deleted at a place and we want to push or pop the elements from top of stack only. So, we can take the variable top which keeps the position of top element in an array.

          It may be possible that a condition arises when there is no place for adding (push) the elements in the array, this is called “overflow”. So, 1^st we check the value of top with the size of the array.

          When there is no element for deleting (pop) from stack then the value of top will be decremented by 1. So, we check the value of top before deleting the elements of stack

import java.util.Scanner;
class rkstack
{
  static int[] a;
  static int i,n,item,top=-1,ch;
  static Scanner s=new Scanner(System.in);
  public static void main(String xp[])
  { 
   System.out.printf("\nEnter the length of the stack :\n");
   n=s.nextInt();
   a=new int[n];
   while(true)
   {
    System.out.printf("\n    MENU \n\n");
    System.out.printf("  1.push    \n");
    System.out.printf("  2.pop    \n");
    System.out.printf("  3.Display   \n");
    System.out.printf("  4.Quit      \n ");
    System.out.printf("Enter ur choice: ");
    ch=s.nextInt();
    switch(ch)
    {
       case 1:  push();break;
       case 2:  pop(); break;
       case 3:  display();break;
       case 4:  System.exit(1);break;
       default:
    System.out.printf("u have entered wrong choice");break;
    }
   System.out.printf("\n");
  }
}

  static int push()
   {
    if(top==n-1)
     {
     System.out.printf("\n stack overflow\n");
     return top;
     }
     System.out.printf("\nEnter the item to be pushed in stack\n");
     item=s.nextInt();
     top++;
     a[top]=item;
     return top;
   }


  static int pop()
   {
   if(top==-1)
     {
     System.out.printf("\n stack underflow\n");
     return top;
     }
     item=a[top];
     System.out.println(item);
     top--;
     return top;
   }

  static int display()
   {
    if(top==-1)
    {
    System.out.printf("\n stack empty ");
    return top;
    }
    System.out.printf("stack  elements are:\n");
    for(i=top;i>=0;i--)
      System.out.print(a[i] + "  ");
    return top;
   }
}


output: