![]() ![]() For example, if we enqueue elements A, B, and C (in that order) on a stack, the next element to be dequeued is C. In the vernacular of stacks, the position of the last element pushed onto the stack is called the top and the position of the first element pushed onto the stack is called the bottom (stacks are usually illustrated vertically, such as seen with stacks of paper to be processed or stacks of dishes to be cleaned). The counterpart to a FIFO queue is a Last-in-First-out (LIFO) queue, or a stack, where the last element to be enqueued is the next element to be dequeued. Instead, the head of the queue is always returned when we dequeue therefore, the target of the dequeue is always implicitly the head of the queue and is never explicitly specified. Note that we do not dequeue a specific element (i.e. Each enqueue and dequeue step, along with the resulting state of the FIFO queue, is shown, starting with the topmost step and ending with the bottom-most step. The example of the A, B, and C elements being added to a FIFO queue is illustrated in the figure below. A FIFO queue is illustrated in the figure below. ![]() In general, the next element to be dequeued from a queue (in this case, A) is called the head of the queue. For example, if we enqueue elements A, B, and C (in that order) on a queue, the next element to be dequeued is A, since it is was the first element enqueued (i.e. In most cases, though, queues are FIFO queues, where the first element enqueued is the first element dequeued. The order of the elements in a queue can vary by the type of queue. Although not all queues are formed in the same manner, the most common type of queue (such as in the supermarket or drive-through examples) is the First-in-First-out (FIFO) queue. If we wish to retrieve the next element from a queue without removing it from the queue, we can peek at the queue, which results in the next element from the queue but leaves it in the queue. Queues have a distinct set of characteristics and behaviors, where the insertion of a new element in a queue is called enqueuing and the atomic retrieval and removal of the next element from the queue is called dequeuing. In general, a queue can be defined as follows:Ī queue is a collection of elements to be processed Although seemingly different in their application, each of these concepts is closely related. Likewise, when we travel through a drive-through window at a fast food restaurant, we insert our car in a line of other cars and the restaurant staff handles orders one car at a time, starting with the first car in the line and terminating with the last car in the line. When we check out at a supermarket, we form a queue at the register (some British dialects refer to this as queuing). The Concept of a QueueĪ queue is one of the most familiar of collections we see on a daily basis. Before diving into these details, though, we must first gain a solid grasp of the concept of a queue. With this understanding, we will then be able to make grounded decisions about when and when not to use each implementation. Lastly, we will delve into the various queue implementations Java offers and how each implementation differs from one another. Starting with an explanation of the concepts behind queues, we will work our way into the actual code of the Queue and Deque interfaces, looking at the intent and logic behind each of these abstractions of the queue concept. In this last installment of The Developer's Guide to Collections, we will export the queue portion of the Java Collections Framework (JCF) and focus particularly on two types of data structures: Queues and double-ended queues (deque pronounced "deck"). This category of problem is so prolific, it has even been codified into a well-known problem for decades: The Producer-Consumer problem. ![]() For example, many concurrent (multi-threaded) applications require queues to process data or execute tasks. While these are important aspects of the Java ecosystem, the same importance of queues can be found at the micro-application level, as well. ![]() In recent years, queues have taken on an entirely new meaning with the acceptance of the Advanced Message Queuing Protocol (AMQP) and many of its implementations, such as RabbitMQ. Queues are an essential part of most software applications, whether in an isolated system or a widely-distributed, networked application. ![]()
0 Comments
Leave a Reply. |