| Article Index |
|---|
| LINEAR QUEUE IMPLEMENTATION USING ADT |
| Introduction |
| Source Code |
| Documentation |
| All Pages |
LINEAR QUEUE IMPLEMENTATION USING ARRAY
Introduction :
The linear queue is a data structure characterised by the fact that additions are made at the end, or tail, of the queue while removals are made from the front, or head, of the queue. For this reason, a queue is referred to as a FIFO structure (First-In First-Out).
The most formal way of implementing queue is through ADT.
The Data Type will contain a set of operations to perform.
In the program we will use those operation to perform our task. The code inside those operations will be abstracted(will not be visible to the user).
Technical Terms In Queue :
1.Enqueue - Inserting an item in the queue.
2.Dequeue - Deleting an item in the queue.
3.Front - It refers to the first element that present in that queue.
4.Rear – It refers to the last element that present in that queue.
Main Features of ADT :
Structure :
The structure is the user defined data type. This can have different data type together. The structure definition will not occupy any bytes in the memory. But the structure variable will occupy the some space in the memory. In our program the q is the structure variable. The
structure members are array, front , rear and capacity. The structure member cannot be accessed independently. It can be accessed only through the structure variable.
- If the structure variable is not a pointer then we have to access the members through dot operator.
- If the structure variable is a pointer then we have to access the members through arrow operator.
Typedef :
The typedef is the predefined function in c language. The function of typedef is to make the user defined data types. Even we can give different name for the primitive data types like integer, float and character. The syntax is as follows
So after declaring like this we can replace int by rollnumber.
malloc :
The malloc is the also predefined function in c. This function is used to allocate the memory in runtime. Some information will be available only during the runtime. In those cases this malloc function will be very useful.The return type of the malloc function is a pointer. We have to pass only one parameter(size) to this function. The syntax of this function is as follows.
Model Of Queue(ADT) :
Array in the Queue ADT :
The elements are stored in the array as shown above. 0,1,2,3,4 above the blocks represent the array index. Then the 1674 is the starting address of the array since the array stores the integer it occupies 2 bytes. Therefore the next block will have the address 1676 and final address of the array is 1682.
Initially The Appearance Of Queue In ADT :
The main will use the memory as per user's requirement from the static allocation. So initially the block will me empty. The front and rear pointer will points to the array index zero(first block). If the maximum size of queue is five main will create an array as follows:
Enqueue :
If we insert(enqueue) an element into the queue the “rear” pointer will move one step forward i.e. Rear pointer incremented to next position after inserting an element in its current position. For example if we insert an element, the queue looks as follows:
Overflow :
If we insert(enqueue) elements, say 2,3,4,8 the above procedure will take place. The queue will looks as follows:
If we attempt to insert(enqueue) an element in the above queue, the “overflow” occur. The condition for overflow is “rear>max-1”. In the above example the maximum elements in the queue is 5(max=5) and the rear points to the index 5. So the condition “5>(5-1)” satisfied. Therefore an overflow occurs in the queue.
Dequeue :
If we delete(dequeue) an element from the queue, the front pointer will move one step forward i.e. Incremented to the next position in the array. The deletion will not actually delete the element but just move the front pointer .
Underflow:
Delete(dequeue) all elements in the queue. The queue will looks as follows:
| < Prev | Next > |
|---|
