Linked Lists, Queues and other nightmares (Part II - Queues)
16 July 2014 By Bhavyanshu Parasher
This is in continuation to Part I in which I showed the use of pointers in implementing stack. I also talked about various concepts on pointers. Now we can move further.
Unlike stacks, queue follows the rule of FIFO (first in first out). So our job is to construct a program that keeps track of the head which is nothing but the first element and the tail which will represent the empty space next to the last element. Why so? Because when we need to add a new element to the end of queue, we need an empty space. Say for example our queue is | 4 | 5 | 2 | 3 | _ | _ |. So our head should point to 4 and tail should point to the empty space next to 3. The queue has two operations : Enqueue & Dequeue Enqueue: When we want to add a new element. Dequeue: When we want to remove an element. Keep in mind that the first element must be removed and the position of head must be moved to next element.
NOTE I will not write the complete code for queue here as most of it is similar to stack. I will just write the initialization of the variables and pointers and functions of enqueue and dequeue. For complete code visit this repository.
Concept : In stack we only required top to represent top of stack. In queue we need two things, head and a tail.
So our stucture would have
After this in
main() we use:
The two important functions are
We need to send the limit as parameter as well because we need to check if the tail has reached the limit or not.
That’s it. This is the code snippet to implement queue using arrays and pointers concept. There is one more type of queue. It is called circular queue but that requires the concept of linked lists. So we must first take a look at linked lists.
blog comments powered by Disqus