Data Structures - Stack ADT
Stack is a data structure in which addition and deletion of element can be performed in only one position - end or top of the list
- It support two operations that are
- PUSH - insert an element into top of the stack.
- POP - delete an element from top of the stack.
- In Addition to that, it has another operation TOP which returns most recently inserted element.
- Therefore, PUSH is the input operation and POP and TOP are the output operations.
- Both POP and TOP cannot be used on empty stack.
- PUSH cannot be performed on full stack.
- It follows the principles of LIFO (Last in First out) or FILO (First In Last Out)
Examples
- Arranging books on the table: you can add a new book only on the top and you can also remove a book only on top.
- Another example is to arrange the plates on the shelf: you can add or remove the plate only on top.
Implementation of Stack
Stack can be implemented in two ways, either using array or using linked list. This tutorial explains the array implementation of stack. Basic operations that can be performed on the stack:
- push() - adding new data onto the stack
- pop() - deleting a data from stack
- top() - returning the top value but not removing
- isFull() - check if the stack is full
- isEmpty() - check if the stack is empty
If we are using an array implementation, we need to declare the size of an array. Usually the index of an array starts from 0. Here each stack is associated with top of the stack which is -1 for an empty stack.
peek() or top()
Following code is the implementation of top() function:
int top()
{
return stack[top];
}
isFull()
This function used to check if stack is full.Following code is the implementation of isFull() function:
int isFull()
{
if(top==SIZE)
retuen 1;
else
return 0;
}
isEmpty()
Used to check if stack is empty.Following code is the implementation of isEmpty() function:
int isEmpty()
{
if(top==-1)
return 1;
else
return 0;
}
push()
This function is used to push new data onto the stack. In order to push some element X onto the stack, we first ckeck if the stack is full because we cannot perform push operation on full stack. If the stack is full, we generate overflow message. If the stack is not full, we increment the top value of the stack and set Stack[top]=X.
Following code is the implementation of push() function:
void push(int data)
{
if(isFull())
cout<<"stack is full";
else
{ top=top+1;
stack[top]=data;
}
}
pop()
This function is used to remove data from the stack. This operation cannot be performed on an empty stack. To pop some element from stack, first check whether the stack is empty or not. If the stack is not empty, access the data and decrement the top value.
Following code is the implementation of pop() function:
void pop()
{
int data;
if(isEmpty())
cout<<"Stack is empty";
else
{
data=stack[top];
top=top-1;
cout<<"the removed value is "<< data;
}
}