A stack is an abstract data type ADT, commonly used in most programming languages. It is named
stack as it behaves like a real-world stack, for example − deck of cards or pile of plates etc.
A real-world stack allows operations at one end only. For example, we can place or remove a card
or plate from top of the stack only. Likewise, Stack ADT allows all data operations at one end only.
At any given time, We can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which
is placed insertedoradded last, is accessed first. In stack terminology, insertion operation is called
PUSH operation and removal operation is called POP operation.
Basic Operations
Stack operations may involve initializing the stack, using it and then de-initializing it. Apart from
these basic stuffs, a stack is used for the following two primary operations −
- push − pushing storing an element on the stack.
- pop − removing accessing an element from the stack.
To use a stack efficiently we need to check status of stack as well. For the same purpose, the following functionality is added to stacks −
- peek − get the top data element of the stack, without removing it.
- isFull − check if stack is full.
- isEmpty − check if stack is empty.
Implementing the Push & Pop
operations:
Algorithms:
Push: This procedure inserts an element item to the top of the
stack which is represented by an arrays & variable top denoting the top
element in the stack.
Push(S, Size, item)
Step 1: check for overflow condition
if top>= Size -1
Print ”Stack
overflow”;
return;
Step 2: increment top
top=top+1
Step 3: insert the element
S[top]=item
Step 4: return
Pop: This procedure deletes the top element of the stack and assigns
it to the variable item.
Pop(S,item)
Step 1: check for stack underflow
if(top==-1)
Print
”Stack underflow”
return
Step 2: assign top element to x
item=S[top];
Step 3: decrement top
top=top-1
Step 4: return
Peek: Returns the topmost element of the Stack but doesn't remove it
peek(S,top)
Step 1: return S [top]
Isfull: used to check whether the Stack is full or not
isFull(S,MAX, top)
Step 1: if top equals to MAXSIZE then return true
Step 2: return false
IsEmpty: used to check whether the stack is full or not
isEmpty(S,xtop)
Step 1: if top less than or equals to -1 then return true
Step 2: return false
Java Implementation of Stack using arrays
/Lab-1:Program to implement Stack
operations using Arrays
//ProjName :- StackApp //ClassName
:- StackApp
import
java.util.*;
class MyStack
{
long
stk[];
int top;
public
MyStack(int size)
{
stk=new long[size];
top=-1;
}
public
boolean isFull()
{
return
(top>=stk.length-1);
}
public
boolean isEmpty()
{
return
(top==-1);
}
public
void push(long item)
{
if(isFull())
{
System.out.println("Stack is Full");
return;
}
stk[++top]=item;
}
public
void pop()
{
if(isEmpty())
{
System.out.println("Stack is empty");
return;
}
long
item=stk[top--];
System.out.println("Popped
element from Stack is :"+item);
}
public
void display()
{
System.out.print("Stack
:[ ");
for(int i=top;i>=0;i--)
System.out.print(stk[i]+" ");
System.out.println("]");
}
}
public class StackApp
{
public
static void main(String[] args)
{
Scanner s=new Scanner(System.in);
MyStack
ST=new MyStack(5);
long
item;
while(true)
{
System.out.println("********** MENU **********");
System.out.println("1. Push\n2. Pop\n3. Display\n4. Exit");
System.out.println("Please enter your option:");
int choice =s.nextInt();
switch(choice)
{
case 1:
System.out.println("Enter an element into the Stack:");
item=s.nextLong();
ST.push(item);
break;
case 2:
ST.pop();
break;
case 3:
ST.display();
break;
case 4:
System.exit(0);
default:
System.out.println("Wrong option");
}
}
}
}
No comments:
Post a Comment