mlasfen.blogg.se - Queue data structure

#Queue data structure how to#

The enqueue operation inserts an item at the tail of the queue. Additionally, you might find it useful to have the peek and length operations. The queue supports 2 main operations: enqueue and dequeue. The traveler who has just entered the queue is at the tail.įrom a higher-point of view, the queue is the data structure that lets you process items, one at a time, in the same order they come in. Recalling the airport example, the traveler at the check-in desk is the head of the queue. The earliest enqueued item in the queue is at the head, while the latest enqueued item is at the tail of the queue. The first enqueued item (input) is the first to dequeue (output).Ī queue has 2 pointers: head and tail. The queue is a type of First Input-First Output (FIFO) data structure.

This is the real-world example of a queue - and the queue data structure works the same way. Another traveler that has just passed the check-in process at the desk is dequeued from the queue.

If there are a lot of travelers willing to check-in, naturally a queue of people is formed at the check-in desk.Ī traveler who's just entered the airport and wants to check-in is going to enqueue into the queue. If you enjoy traveling (like I do), most likely you passed the check-in process at the airport. In this post, I'm going to describe the queue data structure, what operations it has, as well as present you with a queue implementation in JavaScript. That's where the data structures come into play.

#Queue data structure how to#

However, on top of knowing the programming language, you also have to understand how to organize data to easily and effectively manipulate data depending on the task. If you're reading this post, most likely you use JavaScript. The first requirement is to know the programming language of your choice. The result is a circular queue.Being a good developer requires knowledge from multiple disciplines. To avoid the problem of not being able to insert more items into the queue even when it’s not full, the Front and Rear arrows wrap around to the beginning of the array. Even if there are empty cells at the beginning of the array, because you have removed them with dequeue, you still can’t insert a new item because Rear can’t go any further. The problem with this arrangement is that pretty soon the rear of the queue is at the end of the array. When you remove an item, Rear also moves upward. When you insert a new item in the queue in the Queue, the Front arrow moves upward, toward higher numbers in the array. The element dequeued is always the one at the front of the queue, like the customer at the head of the line who has waited the longest. We always enqueue an element at the rear of the queue, just as a newly arriving customer takes a place at the end of the line. Queue maintain indices to the first (front) and last (rear) elements in the array. Queues are little more difficult to implement than stacks, because action happens at both ends.

Empty(): Test whether the more items can be dequeued from the Queue.

Full(): Test whether the more items can be enqueued to the Queue.

peek(): Return the front item of queue.

Dequeue(): Return (and remove) the front item from queue.

Enqueue(x): Insert item x at the back of queue.

A producer is anything that stores data in a queue, while a consumer is anything that retrieves data from a queue. Queues are often described in terms of producers and consumers. We use Queue when order of retrieval should be the same as the order of insertion. The FIFO property of a queue makes it similar like a line of customers waiting to get the tickets. Queues maintain first-in, first-out order (FIFO). This is always a fair practice which we follow in our real life. You must have seen people line up in a bank to be served by a teller or at a Train ticket counter to get the ticket. ↞↞Previous ↞Stack Data Structure What is Queue?