Blog - Full Content with Sidebar

Queue using array program blueprint

October 11, 2012

Declare an array to implement queue
int queue[MAX] (MAX is the size of the array / queue)

Declare and initialize front and rear to -1
int front = -1;
int rear = -1;Create functions

void insert()                (to insert elements into the queue)
int pop()                     ( to delete elements from the queue)
void display()             (to display elements of the queue)
Insert elements into the queue
In the insert function first check if the queue is full because in case the queue is full then we will not be able to insert any elements into the queue.

void insert(int element)
{
           
if(rear==MAX-1)
{
       printf("nQueue is Fulln");
       return;            
}
           
if(front==-1) 
{
       front = 0; 
}
rear=rear+1;
queue[rear]=element;
}

If the queue is full then queue is full will be printed and with the help of that return statement we will come of of the insert function or in other words the insert function will terminate.

If the queue is not full then the following statements will be executed.
if(front==-1)
{
front = 0;
}
rear=rear+1;
queue[rear]=element;

This if statement, if(front==-1) will be true only during the first insertion.
First time when an element is inserted into the queue then the value of front from -1 will become equal to zero with the help of this if statement in
the insert function.

if(front==-1)
{
front = 0;
}rear=rear+1; Value of rear will be incremented by 1 and a new element will be inserted
into the queue with the help of this statement
queue[rear]=element;

int del()
{
    int element;
    if(front==-1 || front==rear+1)
    {
                 printf("Queue is Emptyn");
                 return;
    }
    element = queue[front];
    front = front + 1;
    printf("%d has been deletedn", element);
    return element;
}

If the queue is full then queue is full will be printed and that return statement will terminate the del function.

If the queue is not full the the following statements will be executed.
element = queue[front];
front = front + 1;
printf(“%d has been deletedn”, element);
return element;

Variable element will store the value that will be deleted from the queue.

An Element in the queue is deleted by incrementing the value of front by 1 which is done using this statement.
front = front + 1;

printf(“%d has been deletedn”, element); This print statement prints the value that has been deleted from the queue.

No Comments

Queue using array

October 11, 2012

Queue is a linear data structure in which elements can be inserted only from the rear end of the queue and can be deleted only from the front end of the queue.Queue can be implemented by using an array or a linked list.
This tutorial is about implementing queue using an array.

In the figure above you can see an array which can store up to 6 elements. To implement queue using an array we have to make this array behave like a queue and we can do this by following a property of a queue and the property of a queue is, elements can only be inserted from the rear and can only be deleted from the front end of the queue.

To implement queue using an array first we need to declare an array.
int queue[6];
or
int queue[MAX] | Here MAX is the size of the array / queue, so if we declare MAX = 6 then it means the size of the array/queue is 6.

Initially the queue will be empty, there will be no elements in the queue as you can see in fig. 1.
Always remember that when the value of front = -1 then it means that the queue is empty.

When an element is inserted into the queue then first the value of rear is incremented by 1 and then the new element gets inserted into the queue from the rear.
These two statements are used to do this.
rear = rear + 1 (Increments the value of rear by 1)
queue[rear] = element
(New element gets inserted into the queue from the rear.
Element is the variable which stores the value to be inserted into the queue)
Initially the value of front and rear is equal to -1 as you can see in fig. 1.

(see figure 2)
Insert 5:
First the value of rear is incremented by 1 using this statement:
rear = rear + 1
-1 + 1 = 0
Rear becomes equal to 0 and 5 gets inserted into the queue from the rear with the help of this statement, queue[rear] = element
First time when an element is inserted into the queue then the value of front from -1 becomes equal to 0 that’s why the value of front is equal to 0. This only happens during the first insertion.

Insert 10:

First the value of rear is incremented by 1 (rear = rear + 1).
0 + 1 = 1
Rear becomes equal to 1 and 10 gets inserted into the queue from the rear (queue[rear]=element).

Delete:
Elements of the queue are always deleted from the front.
To delete an element from the queue the value of front is incremented by 1 using this statement
front = front + 1
You can see in fig. 2 the value of front is equal to 0.
0 + 1 = 1
After incrementing the value, front becomes equal to 1 and 5 gets deleted from the queue.

Delete:

Again the value of front is decremented by 1.
The value of front is equal to 1 so
1 + 1 = 2.
From becomes equal to 2 and 10 gets deleted from the queue.

Now there are no elements in the queue, the queue has become empty. The value of front = 2 and the value of rear = 1 which means front = rear + 1.
So if the value of front = rear + 1 then that means, the queue is empty.

So the queue will be empty in two situations.

Situation 1- when the value of front = -1
Situation 2- when the value of front = rear + 1

So in the program we can check if the queue is empty by using this if statement

if(front == -1 || front == rear+1)
{

printf(“Queue is empty”);

}

Insert 15:
Value of rear is incremented by 1.
1 + 1 = 2
Rear becomes equal to 2 and 15 gets inserted into the queue.

Insert 20:
Value of rear is incremented by 1.
2 + 1 =3
Rear becomes equal to 3 and 20 gets inserted into the queue.

Insert 25:
Value of rear is incremented by 1.
3 + 1= 4
Rear becomes equal to 4 and 25 gets inserted into the queue.

(see fig. 3)

Insert 30:

Value of rear is incremented by 1.

4 + 1 = 5

Rear becomes equal to 5 and 30 gets inserted into the queue.

Now the queue is full because the value of Rear is equal to 5. Rear is at the last position of the queue so now we cannot insert any new element into the queue.

So when rear = MAX – 1 then it means that the queue is full.

MAX-1 means last position of the queue because the value of MAX in this case is 6 and 6-1 is equal to 5.

In the program we can check if the queue is full by using this if statement.

if(rear==MAX-1)

{
printf(“Queue is full”);
}

No Comments

C Program to implement stack using array

October 10, 2012

/*************** BY Marxtudor 
www.marxtudor.com/ ***************/

#include
#define MAX 5

void push(int);
int pop();
void display();

int top = -1;
int stk[MAX];

main()
{
      int choice;
      int num;
      while(1)
      {
printf("nEnter your choicen");
printf("1. Pushn");
printf("2. Popn");  
printf("3. Displayn");
scanf("%d",&choice);
  switch(choice)
  {
               case 1:
                    scanf("%d",&num);
                    push(num);        /*function call*/
                    break;
               case 2:
                    pop();            /*function call*/
                    break;
               case 3:
                    display();        /*function call*/
                    break;
               default:
                    printf("nInvalid Inputn");
                    
       }   /*end of switch*/
  }        /*end of while*/
}          /*end of main*/


void push(int element)
{
     if(top==MAX-1)
     {
               printf("nOverflown");
               return;
     }

     top = top+1;
     stk[top]=element;
}


int pop()
{
    int element;
    if(top==-1)
    {
               printf("nUnderflown");
               return;
    }
    
    element = stk[top];
    top = top-1;
    printf("%d  deleted ", element);
    return element;
}


void display()
{
          if(top==-1)
     {
               printf("nUnderflown");
               return;
     }
     
     int i;
     printf("nn");
     for(i=top; i>=0; i--)
     printf("%d n", stk[i]);
}

Stack using array Program blueprint

October 10, 2012

Declare array to implement stack:
int stk[MAX]; | MAX is the size of the stackDeclare and Initialize top:
int top = -1;
Stack should initially be empty and if the value of top is -1, it means stack is empty.

We need to create 3 functions:

void push()                   – for inserting element into the stack
int pop()                      – for deleting element from the stack
void display()              – to display elements of the stack

Pushing element into the stack:
First check for stack overflow because in case the stack is full then we will not be able to insert any elements into the stack.

void push()
{

if(top == MAX - 1}
{
printf("Stack Overflow");
return;

/*** with the help of  return statement program control will come out of the push function .
If the condition (top == MAX-1 becomes true then 
we should come out of the push function ****/

}

top = top + 1;
stk[top] = element;

If the stack is full then stack overflow will be printed
If the stack is not full then the condition if(top == MAX – 1) will become false and the following two statements will get executed.
top = top + 1;

stk[top] = element;
Here element is the value inputted by the user using scanf(); function, this value will be pushed into the stack.

Popping element from the stack:
First you need to check for underflow condition because if the stack is empty or if the stack contains no elements then we cannot delete anything.

int pop()
{
int element;

*if value of top is -1 it means stack is empty*/
if(top == -1) 
{                                              
printf("Stack is empty");
return;
}

element = stk[top];  
top = top - 1;    /**** decrement the value of top by 1 ***/
return element;       
}

if(top == -1) If the stack is empty then this condition will become true and if this condition becomes true then stack is empty will be printed and because of that return statement the pop function will terminate.
If the stack is not empty then the condition if(top == -1) will be false and the following three statements will get executed.
element = stk[top];
top = top – 1;
printf(“%d has been deleted”, element);
return element;

element = stk[top];
In a stack element is always deleted from the top so stk[top] will be the element to be deleted and by writing element = stk[top];
we are assigning element the value that will be deleted from the stack.

printf(“%d has been deleted”, element); will print the number which has been deleted from the stack.

No Comments

Stack using array

October 10, 2012

Stack is a linear data structure in which elements can be inserted and deleted only from the top of the stack.
Stack can be implemented by using:

Array
Linked List

Inserting element into the stack is called Push and deleting element from the stack is called Pop.
In this tutorial we are going to implement stack using an array.

fig. 1

In the figure above you can see an array which can store up to 5 elements. We have to make this array behave like a stack but how are we going to make this array behave like a stack ?
We are going to do this by following the property of a stack and the property of a stack is that elements can only be inserted and deleted from one end called the top end of the stack. That’s the reason why we say implement stack using an array because we are using an array to create a stack.

To implement stack using array first we need to declare an array.
int stk[5];
or
int stk[MAX]; | Here MAX is the maximum size of the stack, so if MAX = 5 then the size of the stack will be 5.

Initially the stack will be empty ie; there will be no elements in the stack as you can see in fig.1.
Always remember when the stack is empty the value of top is equal to -1.
When the stack is empty then this condition is known as underflow. So top = -1 means stack is empty and it is an underflow condition.

fig. 2

In figure 2 you can see first we pushed / inserted 5 into the stack. First the value of top is increased by 1 so from -1 the value of top becomes 0 (-1 + 1 = 0) and and element 5 is inserted.

Push 10
The value of top was 0, we incremented the value of top by 1 and top becomes 1 ( 0 + 1) = 1. Then the new element 10 gets inserted.

Push 16
The value of top was 1, we incremented the value of top by 1 so top becomes 2 (1 + 1 = 2) and the element 16 gets inserted.

Push 20
The value of top was 2, we incremented the vale of top by 1. Top becomes 3 (2 + 1 = 3) and the element 20 gets inserted.

To insert element into the stack we use this code in the program:
First we increment the value of top by 1.
top = top + 1;
Then we insert the element at the top position.
stk[top] = element; | variable element stores the value to be inserted into the stack from the top.
So one property of stack is fulfilled which is, elements can only be inserted from the top.

fig. 3

Push 50
The value of top was 3 now we insert another element into the stack.
top = top + 1
top = 3 + 1 = 4
Top becomes 4 and the new element 50 is inserted at the top position which is the 4th index/position of the array / stack.
In figure 3 you can see that stack is full, there is no space left in the stack to accommodate a new element. Now we cannot insert any more elements into the stack because it is full.
When the stack is full then this condition is also known as overflow condition also called stack overflow.

So in the program we can check if the stack is full by using the following code:
if(top == MAX – 1)
{
printf(“overflow”);
}

If the value of top = MAX – 1 then this means, stack is full. MAX is the maximum size of the stack/array so if MAX = 5 then stack/array can store up to 5 elements.
top = (MAX – 1)
top = (5 – 1) is 4
So top = 4 and when top is 4 it means stack is full when the maximum size of stack is 5.

fig. 4

Pop 50
To delete an element from the stack we first decrement / decrease the value of top by 1.
The value of top before deletion was 4 (see fig. 3). After decrementing value of top by 1 (4-1 = 3) the value of top becomes 3 and 50 gets deleted from the stack.

Pop 20
The value of top was 3. Decrement value of top by 1 so top becomes 2 (3-1=2).

Pop 16
The value of top before deleting 16 was 2. So after decrementing top by 1 top becomes 1 (2-1=1)

Pop 10
The value of top was 1 then we decrement top by 1 the value of top becomes 0 (1-1=0).

If we pop 5 then the value of top from 0 will become -1 (0 – 1 = -1) and the stack will become empty.

The following code is used in the program to pop an element from the stack:
top = top – 1;

No Comments

Circular Queue implementation using array- video

October 10, 2012

You will learn:
What is a Circular Queue and how is it different from a normal queue.
How to insert elements into a circular queue.
How to check if a circular queue is full.
How to delete elements from a circular queue.
How to check if a circular queue is empty.
How to display elements of a circular queue.

No Comments

Queue implementation using array – video

October 10, 2012

What is a Queue and how does it work

Program to implement queue using array

You will learn:
How to create the main function.
How to insert elements into a queue.
How to delete elements form a queue.
How to check if a queue is empty.
How to display elements of a queue.