Linear Queues in Data Structures
A queue is an ordered list in which items may be added only at one end called the “rear” and items may be removed only at the other end called “front”.
- A line of passengers waiting to buy tickets in a reservation counter. Each new passenger gets in line at the “rear”; the passenger at the front of the lines is reserved.
- A linear queue can be found in a time-sharing computer system where many users share the system simultaneously.
- The first element, which is added into the queue will be the first one to be removed. Thus queues are also called First-in First-Out lists (FIFO) or Last-In-Last-Out lists (LILO).
- Queues may be represented in the computer memory by means of linear arrays or linked list.
- There are two pointer variables namely FRONT and REAR.
- The FRONT denotes the location of the first element of the queue.
- The rear describes the location of the rear element of the queue.
- When the queue is empty, the values of front and rear are-1 and -1 respectively.
- The “max size “represent the maximum capacity of the linear queue.
- The following is the condition to test the queue is full or not. (Rear== max size-1)
- To insert the first element both pointers should be altered to ‘0’ Front =0 rear=0.
- Whenever an item is added to the queue, the value of REAR is incremented by 1. REAR =REAR+1;
- The following is the condition to test the queue is empty or not. Front==-1
- Whenever an “Item” is deleted from the queue, the value if front is incremented by 1 Front=Front+1;
- To delete the last element, both pointers should be altered.
Implementation of linear queues using arrays .
# include <studio.h>
#define maxsize 5
void Insertion ()
printf(“Queue is overflow \n”);
printf(“Enter an element:”);
void deletion ()
printf(“Queue is under flow\n”);
printf(“ Deleted element is: %d \n”, Queue [Front]);
void display ()
if (Front ==-1)
printf(“Queue is under flow \n”);
for(i= Front; i<= Rear; i++)
printf(“Enter your choice:”);
case1: insertion (); break;
case2: deletion (); break;
case3: Display(); break;
while (choice <=4)
1). Initial State:
2). After inserting element 10
3). After inserting elements 20, 30, 40, 50:
4). Inserting element 60
Queue is over flow
5).After deleting elements 10,20,30,40:
6). After inserting elements 20, 30, 40, 50:
Applications of queue:
- A queue can be used to store a lift of interrupts t=in the operating system, which would get processed in the order in which they were generated.
- A queue can be found in a time-sharing computer system where many users share the system simultaneously.
- In a computer network, messages from one to another computer are generally create asynchronously. These messages therefore need to be buffered until the receiving computer is ready for id .These communication buffers make extensive use queues by staring these messages in a queue. Also the messages need to be sent to receiving computer in the same order in which they are created, i.e. FIFO order.