- What is a Data Structure & Types of Data Structures
- What is an Algorithm & It's Characteristics
- Asymptotic Notations
- What is Space Complexity
- Array in Data Structure
- Algorithm for Insertion in Array
- Sparse Matrix
- Introduction to a Linked List
- Algorithm to Insert a Node at the End of the Linked list
- Algorithm to Insert a Node at the Front of the Linked List
- Algorithm to Delete a Node from Linked list
- Circular Linked List
- Algorithm to Insert a Node in the Circular Linked list
- Algorithm to Delete a Node from the Circular Linked list
- Doubly Linked List
- Algorithm to Insert a Node at the End of the Doubly Linked list
- Algorithm to Delete a Node from the Doubly Linked List
- Stack Data Structure
- Algorithm to convert Infix to Postfix
- Queue Data Structure
- Circular Queue in Data Structure
Stack Data Structure
STACK
Stack is a
linear data structure which follows a LIFO(Last in First Out) or FILO(First in
Last Out) order to operate.
Real-life examples of a stack are a deck of cards, piles of
books, piles of money, and many more.
This example allows you to
perform operations from one end only, like when you insert and remove new
element from the top of the stack. It means insertion and deletion in the stack
data structure can be done only from one end i.e. the top of the stack. You can
access only the top element of the stack at any given point in time.
·
Inserting
a new element in the stack is termed a push.
·
Removing
or deleting elements from the stack is termed pop.
Working of Stack:
Suppose
we want to store the elements in a stack and let's assume that stack is empty.
We have taken the stack of size 5 as shown below in which we are pushing the
elements one by one until the stack becomes full.
When we perform the delete operation on the stack in the
above case, the element 1 is entered first, so it will be removed only after
the deletion of all the other elements.
Operations
1.
Push: Insert an item in the stack
2.
Pop: Remove an item from the
stack
3.
Peek or Top: Returns
the top element of the stack.
4.
isEmpty: Returns true if the
stack is empty, else false
- isFull(): It determines whether
the stack is full or not.'
Algorithm for Push and Pop operations:
Push Operation:
The process of inserting a new element onto a stack
is known as a push Operation. Push operation involves the following steps −
·
Step 1 − Check
if the stack is full.
·
Step 2 −
If the stack is full, then return.
·
Step 3 −
If the stack is not full, increment the top by 1.
·
Step 4 −
insert a new element to the top of the stack.
·
Step 5 −
Returns success.
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
Pop Operations:
The
process of deleting an element from a stack is known as a pop operation.
The pop
operation involves the following steps −
A Pop operation may
involve the following steps −
·
Step 1 − Checks if the stack is
empty.
·
Step 2 − If the stack is empty, then
return
·
Step 3 − If the stack is not empty,
access the top element.
·
Step 4 − Decreases the value of top
by 1.
·
Step 5 − Returns success.
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Stack Applications:
- UNDO and REDO operations in
a text editor
- Infix to postfix conversion
- Infix to prefix conversion
- Evaluation of postfix
expression
- Recursion
- Reversal of a string
- Tower of Hanoi problem
- Function calls management
- Evaluation of arithmetic
expressions
- Syntax checking of
expressions in a programming environment
- Parenthesis matching
- Backtracking.
- Used in depth first search.
- Operating System functions
Analysis of Stack Operations
Below mentioned are the time
complexities for various operations that can be performed on the Stack data
structure.
- Push Operation : O(1)
- Pop Operation : O(1)
- Top Operation : O(1)
- Search Operation : O(n)
The time complexities
for push() and pop() functions are O(1) because
we always have to insert or remove the data from the top of
the stack, which is a one step process.
Implementation of stack using C
programming:
#include
<stdio.h>
int
stack[100], n=100, top=-1;
void
push();
void
pop();
void
display();
int
main()
{
int choice, ele;
printf("**************************\n");
printf("1. Push element into the
stack\n");
printf("2. Pop element from the
stack\n");
printf("3. Display stack
elements\n");
printf("4. Exit\n");
do
{
printf("\n Enter your
choice\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
{
printf("Enter the element
which you want to be pushed:\n");
scanf("\n%d",&ele);
push(ele);
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exit");
break;
}
default:
{
printf("Invalid Choice");
}
}
}while(choice!=4);
return 0;
}
void
push(int ele)
{
if(top>=n-1)
printf("Stack Overflow");
else
{
top++;
stack[top]=ele;
}
}
void
pop() {
if(top<=0)
printf("Stack Underflow");
else
{
printf("The popped element is
%d",stack[top]);
top--;
}
}
void
display()
{
if(top>=0)
{
printf("Stack elements are\n");
for(int i=top; i>=0; i--)
printf("\n %d",stack[i]);
}
else
printf("Stack is empty"); }