DSA using C Tutorial
Selected Reading
- DSA using C - Discussion
- DSA using C - Useful Resources
- DSA using C - Quick Guide
- DSA using C - Recursion
- DSA using C - Sorting techniques
- DSA using C - Search techniques
- DSA using C - Graph
- DSA using C - Heap
- DSA using C - Hash Table
- DSA using C - Tree
- DSA using C - Priority Queue
- DSA using C - Queue
- DSA using C - Parsing Expressions
- DSA using C - Stack
- DSA using C - Circular Linked List
- DSA using C - Doubly Linked List
- DSA using C - Linked List
- DSA using C - Array
- DSA using C - Concepts
- DSA using C - Algorithms
- DSA using C - Environment
- DSA using C - Overview
- DSA using C - Home
Selected Reading
- Who is Who
- Computer Glossary
- HR Interview Questions
- Effective Resume Writing
- Questions and Answers
- UPSC IAS Exams Notes
DSA using C - Queue
DSA using C - Queue
Overview
Queue is kind of data structure similar to stack with primary difference that the first item inserted is the first item to be removed (FIFO - First In First Out) where stack is based on LIFO, Last In First Out principal.
Queue Representation
Basic Operations
insert / enqueue − add an item to the rear of the queue.
remove / dequeue − remove an item from the front of the queue.
We re going to implement Queue using array in this article. There is few more operations supported by queue which are following.
Peek − get the element at front of the queue.
isFull − check if queue is full.
isEmpty − check if queue is empty.
Insert / Enqueue Operation
Whenever an element is inserted into queue, queue increments the rear index for later use and stores that element at the rear end of the storage. If rear end reaches to the last index and it is wrapped to the bottom location. Such an arrangement is called wrap around and such queue is circular queue. This method is also termed as enqueue operation.
void insert(int data){
if(!isFull()){
if(rear == MAX-1){
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element using front index and increments the front index. As a wrap around arrangement, if front index is more than array s max index, it is set to 0.
int removeData(){
int data = intArray[front++];
if(front == MAX){
front = 0;
}
itemCount--;
return data;
}
Example
QueueDemo.c
#include <stdio.h>
#include <string.h>
#include <stdpb.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
if(!isFull()){
if(rear == MAX-1){
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX){
front = 0;
}
itemCount--;
return data;
}
int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
// front : 0
// rear : 4
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 3 5 9 1 12
insert(15);
// front : 0
// rear : 5
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 3 5 9 1 12 15
if(isFull()){
printf("Queue is full!
");
}
// remove one item
int num = removeData();
printf("Element removed: %d
",num);
// front : 1
// rear : 5
// -------------------
// index : 1 2 3 4 5
// -------------------
// queue : 5 9 1 12 15
// insert more items
insert(16);
// front : 1
// rear : -1
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
// As queue is full, elements will not be inserted.
insert(17);
insert(18);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
printf("Element at front: %d
",peek());
printf("----------------------
");
printf("index : 5 4 3 2 1 0
");
printf("----------------------
");
printf("Queue: ");
while(!isEmpty()){
int n = removeData();
printf("%d ",n);
}
}
Output
If we compile and run the above program then it would produce following output −
Queue is full! Element removed: 3 Element at front: 5 ---------------------- index : 5 4 3 2 1 0 ---------------------- Queue: 5 9 1 12 15 16Advertisements