Change Website notification

We are moved from blogger to website   https://balututorial.com/

Queue

Queue introduction
                 Queue is a linear Data structure which allows operations in a particular order i.e. rear or front end only. The order of queue is First In First Out (FIFO) or First Come First serve (FCFS).
                 A good example of queue is any queue of consumers for a resource where the consumer that came first is served first.
                  The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

Operations on Queue:- Mainly the following three basic operations are performed on queue:

1. Qinsert
2. Qdelete
3. Qdisplay

Qinsert (Enqueue):- Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
Qdelete (Dequeue):- Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
Qdisplay :- Displaying all elements without deletion 

Types of Queue:- Queue can be of four types:

1. Linear/Simple Queue
2. Priority Queue
3. Circular Queue
4. Dequeue (Double Ended queue)

Linear/Simple Queue:- In linear queue all items are arranged in linear fashion. 

Priority Queue:-In this queue all elements are process according to key value called priority, Witch element having high priority that one will process first. 

Circular Queue:- As in a circle after last element, first element occurs.

Double Ended queue:- Dequeue is also called double ended queue, as the name implies we can add or delete the element from both sides. Dequeue can be of two types

1. Input restricted:- in input restricted dequeue, elements can be added from only one end but we can delete the element from both sides.
2. Output restricted:- in output restricted dequeue element can be added from both ends but deletion is allowed only at one end.

STACK  INTRODUCTION:

                                       Stack is a linear data structure which allows any kind of operations on only top of the stack.Stack fallows particular order only i.e LIFO(Last In First Out) or FILO(First In Last Out).

• Mainly the following three basic operations are performed in the stack:

• Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition.

• Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.

• Peek: Get the item from stack with out pop.

How to understand a stack practically?

• There are many real life examples of stack. Consider the simple example of plates stacked over one another in canteen. The plate which is at the top is the first one to be removed, i.e. the plate which has been placed at the bottom most position remains in the stack for the longest period of time. So, it can be simply seen to follow LIFO/FILO order.

Implementation:
                          There are two ways to implement a stack:

1. Using array
2. Using linked list

Stack Infix to Postfix Notation

ALGORITHM : Infix to Postfix 

• 
  

  STEP 1 : Read the given infix expression into string called infix.

• 
  

  
  

  STEP 2 : Read one character at a time and perform the following operations :
• If the character is an operand, then add the operand to the postfix string.

• If the character is not an operand, then check, 
  If the stack is not empty and precedence of the top of the 
  stack operator is higher than the read operator,
  then pop the operator from stack and add this 
  operator to the postfix string.
  Else push the operator onto the stack.

• 
  

  STEP 4 : If stack is not empty, then pop the operator from stack and add this operator to the postfix string.

• 
  

  
  

  STEP 5 : Repeat STEP 4 till all the operators are popped from the stack.

• 
  

  
  

  STEP 6 : Display the result of given infix expression or resultant postfix expression stored in a string called postfix from this algorithm.

Source code:-

1:  #include <stdio.h>  
2:  #include <dos.h>  
3:  #include <string.h>  
4:  #define operand(x) (x>='a'&&x<='z'||x>='A'&& x<='Z'||x>='0'&& x<='9')  
5:  char infix[30];  
6:  char postfix[30];  
7:  char stack[30];  
8:  int top,i=0;  
9:  void init()  
10:  {  
11:   top=-1;  
12:  }  
13:  void push(char x)  
14:  {  
15:   stack[++top]=x;  
16:  }  
17:  char pop()  
18:  {  
19:   return (stack[top--]);  
20:  }  
21:  int isp(char x)  
22:  {  
23:       int y;  
24:   y=(x=='('?0:x=='^'?4:x=='*'?2:x=='/'?2:x=='+'?1:x=='-'?1:x==')'?6:-1);  
25:       return y;  
26:  }  
27:  int icp(char x)  
28:  {  
29:       int y;  
30:       y=(x=='('?4:x=='^'?4:x=='*'?2:x=='/'?2:x=='+'?1:x=='-'?1:x==')'?6:-1);  
31:       return y;  
32:  }  
33:  void infixtopostfix()  
34:  {  
35:   int j,l=0;  
36:   char x,y;  
37:   stack[++top]='\0';  
38:   for(j=0; (x=infix[i++])!='\0'; j--)  
39:   {  
40:     if(operand(x))  
41:        postfix[l++]=x;  
42:     else  
43:     {  
44:       if(x==')')  
45:      {  
46:        while((y=pop())!='(')  
47:         postfix[l++]=y;  
48:      }  
49:       else  
50:       {  
51:        while (isp(stack[top])>=icp(x))  
52:         postfix[l++]=pop();  
53:        push(x);  
54:       }  
55:     }  
56:    }  
57:    while(top>=0)  
58:     postfix[l++]=pop();  
59:  }  
60:  int main()  
61:  {  
62:    init();  
63:    printf("Enter an infix Expression:");  
64:    scanf("%s",infix);  
65:    infixtopostfix();  
66:    printf("The Resulting postfix exp is:%s",postfix);  
67:    return 0;  
68:  }   

Priority queue implementation

1:  #include <stdio.h>  
2:  #include <stdlib.h>  
3:  #include <dos.h>  
4:  #include <malloc.h>  
5:  struct pqueue  
6:  {  
7:       int key;  
8:       int data;  
9:       struct pqueue*next;  
10:  };