Queue is abstract data types (ADT)
Queue is a FIFO data structure. First-in-first-out.
We can implement Queue in two ways
- Arrays
- Linked lists
Basic operations on Queue:
- enqueue(element): Add element to the end of the queue
- dequeue() Returns the element from the front of the queue, removing it
- isEmpty() Returns true if queue empty
- isFull() Returns true if queue full
Applications of Queues :
- Waiting lists
- Access to shared resources (e.g., printer)
- Multiprogramming
-----------------------------------------------------------------------------------
Implementation of Queue by using LinkedList
#include<stdio.h>
#include<malloc.h>
# define MAX 10
struct Queue
{
int data;
struct Queue *next;
};
int Count(struct Queue *head)
{
int no = 0;
while(head != NULL)
{
++no;
head = head -> next;
}
return no;
}
int IsQueueEmpty(struct Queue *head)
{
if(head == NULL)
{
return 1;
}
else
{
return 0;
}
}
int IsQueueFull(struct Queue *head)
{
if(Count(head) == MAX)
{
return 1;
}
else
{
return 0;
}
}
void Display( struct Queue *head )
{
if(head == NULL)
{
return;
}
while(head)
{
printf(" -> |%d| ", head->data);
head = head -> next;
}
}
int dequeue(struct Queue **head)
{
int no;
struct Queue *temp;
temp = ( *head );
if(IsQueueEmpty(*head))
{
return -1;
}
else
{
(*head) = temp->next;
no = temp -> data;
free(temp);
}
return no;
}
void enqueue(struct Queue **head, int no)
{
struct Queue *temp;
struct Queue *newn = (struct Queue*)malloc(sizeof(struct Queue));
newn -> data = no;
temp = (*head);
if(IsQueueFull(*head))
{
free(newn);
return;
}
if(*head == NULL)
{
newn -> next = NULL;
(*head) = newn;
}
else
{
while(temp -> next != NULL)
{
temp = temp -> next;
}
temp -> next = newn;
newn -> next = NULL;
}
}
int main(int argc, char *argv[])
{
struct Queue * first = NULL;
enqueue(&first,10);
enqueue(&first,20);
enqueue(&first,30);
enqueue(&first,40);
Display(first);
printf("%d",dequeue(&first));
printf("%d",dequeue(&first));
Display(first);
return 0;
}
-----------------------------------------------------------------------------------
Implementation of Queue by using Array
#include<stdio.h>
#include<malloc.h>
# define MAX 10
int front = 0;
int rare = -1;
int Queue[MAX];
int IsQueueEmpty()
{
if(rare == -1)
{
return 1;
}
else
{
return 0;
}
}
int IsQueueFull()
{
if(rare == MAX )
{
return 1;
}
else
{
return 0;
}
}
void Display()
{
int i = 0;
for(i = front; i != rare + 1; i++)
{
printf("%d",Queue[i]);
}
}
int dequeue()
{
int no = 0;
if(IsQueueEmpty())
{
return -1;
}
else
{
return Queue[front++];
}
}
void enqueue(int no)
{
if(IsQueueFull( ))
{
return;
}
Queue[++rare] = no;
}
int main(int argc, char *argv[])
{
enqueue(10);
enqueue(20);
enqueue(30);
enqueue(40);
Display();
printf("\n%d\n",dequeue());
printf("\n%d\n",dequeue());
Display();
return 0;
}
-----------------------------------------------------------------------------------
Important points about implementaion of Queue by using Array or LinkedList
Array
• Simple and efficient
• Assume a fixed capacity for array
• If capacity is too small, can reallocate, but expensive
• If capacity is too large, space waste
Linked Lists
• No size limitation
• Extra space per element
When know the maximum number of element, use arrays
No comments:
Post a Comment