Skip to main content

STACK in C Language

  • It’s special data structure based on LIFO (Last In First Out Concept).
  • It can be implemented using One dimensional Array as well as Singly linked list.
  • TOP  is the external pointer points to last node element pushed.
  • There are two operation which is performed on stack i.e., Push (Insertion) and Pop (Deletion).
  • Push and Pop operation is performed through TOP end.( means insertion and deletion is restricted through one end i.e., TOP end)

Write an algorithm to perform push operation.

PUSH(TOP)
[ PUSH is the name of algorithm and TOP is the external pointer points to last inserted node. ]
NEW<--FREE
FREE <--  FREE --> NEXT
If NEW=NULL Then:
    Write : ‘ Memory allocation errot’
     Exit
[ End of If]
Read : NEW-->INFO
NEW -->  NEXT <-- TOP
TOP <--NEW
END

Write an algorithm to perform pop operation.

POP(TOP)
[ POP is the name of algorithm]
If TOP = NULL Then:
   Write: ‘ Stack is empty’
   Exit
[ End of If]

I <-- TOP --> INFO
Write: ‘Poped element is’, TOP -->  INFO
TOP <-- TOP --> NEXT
END

Write the program to perform PUSH and POP operation:

#include<stdio.h>
#include<conio.h>

struct node
{
   int info;
      struct node *next;
};
struct node *top=NULL;

void push(int i);
{
 struct node *new;
 if(new==NULL)
{
    printf(“Memory allocation error\n”);
    exit(0);
 }
new->info=i;
new->next=top;
top=new;
}

void pop(void)
{
  if(top==NULL)
  {
    printf(“Stack is empty”);
    exit(0);
  }
  printf(“%d->”,top->info);
  top=top->next;
}

void main()
{
  int i;
 char ch;
  clrscr();
  do
  {
     printf(“Enter your choice\n”);
     printf(“1. PUSH\n”);
     printf(“2. POP\n”);
     scanf(“%d”,&choice);
     switch(choice)
     {
  case 1:
printf(“Enter the value to push in stack\n”);
scanf(“%d”,&i);
push(i);
break;
case 2:
pop();
break;
default:
printf(“Invalid choice try again\n”);
    }
   printf(“Do you want to continue press ‘Y’\n);
  ch=getche();
    }while(ch==’Y’);
getch();
}

Algorithm to Push an element on  Stack using One dimensional Array:

PUSH( S, TOP, N, ITEM )
[S is the name of Array , TOP is the current index of a STACK , N is the size of an Array, ITEM is the element to be inserted]

If TOP==N Then:
   Write: ‘Overflow’
   Exit
[ End of If]
TOP <--TOP+1
S[TOP]=ITEM
END

Algorithm to Pop the Stack using One dimensional Array:

POP(S, TOP)
[ S is the name of an array and TOP is the current index]

If TOP=-1 Then:
   Write: ‘Underflow’
    Exit
[ End of If]
I <-- S[TOP]
TOP <-- TOP-1
Return I
END

WACP to perform Push and Pop operation on Stack using One dimensional Array:

/* Function to perform push operation */
void push(int s[], int n, int *top, int i)
{
  if (top==n)
    {
        printf(“Over flow”);
        exit(0);
    }
s[++top]=i;
}
/* Functio to perform pop operation */
int pop( int s, int *top)
{
  int i;
  if( top==-1)
   {
      printf(“Underflow”);
      exit(0);
   }
i=s[top--];
return i;
}
main( )
{
 int s[8],top,item,choice;
char ch;
do
{
   printf(“Enter your choice\n”);   
   printf(“1.Push Operation\n”);
   printf(“2. Pop operation\n”);
   scanf(“%d”,&choice);
   switch(choice)
   {
      case 1: printf(“Enter the element to push\n”);
scanf(“%d”,&item);
push(s, 8,&top,item);
break;
case 2: printf(“Poped element=%d”,pop(s, &top));
break;
default: printf(“Invalid choice\n”);
}
printf(“Do you want to continue press ‘Y’\n”);
ch=getche();
}while(ch==’Y’);
getch(); }

Polish Notation:

Infix expression takes much time and scanning to evaluate in computer due to operator hierarchy and 
parenthesis. so to overcome this problem French Mathematician Polish has given parenthesis free 
notation. i.e., Postfix and Prefix notation. 
In Postfix notation operator is placed after the operand. 
And in Prefix notation operator is placed before operand.

Conversion of Infix expression into prefix and postfix notation:
Infix exp: 5*9^2/3

First place parenthesis according to operator hierarchy
((5*(9^2))/3)
Postfix Conversion:
Step 1: Conversion done from higher order operator and place the operator at the place of left parenthesis. Remove the both of parenthesis.
((5*^92)/3)
Step 2: Place the operator again at the left of parenthesis and remove according to operator hierarchy.
(*5^92/3)
Step 3:
/5*92^3

Prefix Converesion:

Step 1: Conversion done from higher order operator and place the operator at the place of right parenthesis. Remove the both of parenthesis.
((5*92^)/3)
Step 2: Place the operator again at the Right of parenthesis and remove according to operator hierarchy.
(592^*/3)
Step 3:
592^*3/

Algorithm to Convert  an INFIX expression to POSTFIX expression using stack:

INFIX_TO_POSTFIX(I)
[ I is the INFIX expression]

STEP 1: Add  ‘) ‘ at the end of I. and push ‘ ( ‘ on to the stack.
STEP 2: Repeat scanning the characters of I from left to right while stack is not empty
  STEP 2(a):    If the scanned character is an operand Then:
  Add it to P (PostFix expression)
[ End of If]
  STEP 2(b):    If the scanned character is ‘(‘ Then:
Push it on the stack
[End of If]
STEP 2(c):    If the scanned character is’)’ Then:
Repeatedly POP the stack till ‘(‘ , add the poped operators to P
 and remove ‘(‘ from the stack 
[End of If]
STEP 2(d):    If the scanned character is operator Then:
Check the top of stack repeatedly for higher or same hierarchy of operators till lower hierarchy. if any pop them and add to P
and push the scanned character onto Stack
[End of If]

 [ End of While]
STEP 3: Write: P
STEP 4: EXIT

Convert the Infix exp. I: (A+B) / ( C-D ) ^ E + F * G 

Add ) to I at the end, PUSH ( on to the stack.
S. NO.
 Scanned Character
STACK
POSTFIX exp P
1.
(
(

2.
(
((

3.
A

A
4.
+
((+
A
5.
B
((+
A B
6.
)
(
A B +
7.
/
( /
A B +
8.
(
( / (
A B +
9.
C
( / (
A B + C
10.
-
( / ( -
A B + C
11.
D
( / ( -
A B + C D
12.
)
( /
A B + C D -
13.
^
( / ^
A B + C D -
14.
E
( / ^
A B + C D – E
15.
+
( +
A B + C D – E ^ /
16.
F
( +
A B + C D – E ^ / F
17.
*
( + *
A B + C D – E ^ / F
18.
G

A B + C D – E ^ / F * +

Evaluation of POSTFIX expression using STACK.

POSTFIXEVAL(P)

[ P is a POSTFIX expression]
Repeat Scanning P from left to right While Scanned Character != #
  If  Scanned character = operand Then:
      STACK[TOP] <-- operand
      TOPßTOP+1
  Else
      B<-- STACK[TOP], TOP<--TOP-1
      A<-- STACK[TOP], TOP<--TOP-1
      RES<--A operator B
      STACK[TOP] <--RES
  [ End of If]
[End of While]
VAL <-- STACK[TOP]
Write: ‘ Value of postfix expression’, VAL
END

Example: Evaluate the Postfix exp 5 6 * 3 + 5 – 

Soln : Add # at the end of Postfix expression
Start scanning the exp. from left to right.
S.NO.
Scanned Character
STACK
1.
5
5
2.
6
5, 6
3.
*
30   // (5*6)
4.
3
30, 3
5.
+
33   // (30+3)
6.
5
33, 5
7.
-
28  // (33-5)

Comments

Popular posts from this blog

difference between structure and union in C Language

In c language article we will see the difference between union and structure. Both are the user define datatype in c language. See the table which is mentioned below: ASP.NET Video Tutorial Series Structure Union1.The keywordstruct is used to define a structure 1. The keyword union is used to define a union. 2. When a variable is associated with a structure, the compiler allocates the memory for each member. The size of structure is greater than or equal to the sum ofsizes of its members. The smaller members may end with unused slack bytes. 2. When a variable is associated with a union, thecompiler allocates thememory by considering the size of the largest memory. So, size of union is equal to the size of largest member. 3. Each member within a structure is assigned unique storage area of location. 3. Memory allocated is shared by individual members of union. 4. The address of each member will be in ascending order This indicates that memory for each member will start at different offset v…

Difference between Linear search and Binary Search in c language

SQL Video Channel : Download all SQL Video



Binary Search Linear Search Works only on sorted items. such as  1,2,3,4,5,6  etc
Works on sorted as well as unsorted items. 12,4,5,3,2,1 etc Very efficient if the items are sorted Very efficient if the items are less and present in the beginning of the list. such as Suppose your list items are : 12,3,4,5,1 and you want to search 12 number then you get beginning in the list. Works well with arrays and not on linked lists. Works with arrays and linked lists.
Number of comparisons are less More number of comparisons are required if the items are present in the later part of the array or its elements are more.

Memory representation of Linked List Data Structures in C Language

Memory representation of Linked List

             In memory the linked list is stored in scattered cells (locations).The memory for each node is allocated dynamically means as and when required. So the Linked List can increase as per the user wish and the size is not fixed, it can vary.

               Suppose first node of linked list is allocated with an address 1008. Its graphical representation looks like the figure shown below:


      Suppose next node is allocated at an address 506, so the list becomes,



  Suppose next node is allocated with an address with an address 10,s the list become,


The other way to represent the linked list is as shown below:




 In the above representation the data stored in the linked list is “INDIA”, the information part of each node contains one character. The external pointer root points to first node’s address 1005. The link part of the node containing information I contains 1007, the address of next node. The last node …