Python ships with several queue implementations that each have slightly different characteristics. You get what you put in, and in exactly that order (remember the pipe example?) The priority of individual elements is decided by the queue based on the ordering applied to their keys.Ī regular queue, however, won’t re-order the items it carries. These are specialized queues: instead of retrieving the next element by insertion time, a priority queue retrieves the highest-priority element. Scheduling algorithms often use priority queues internally. A short and beautiful algorithm using a queue is breadth-first search (BFS) on a tree or graph data structure. Queues have a wide range of applications in algorithms and to solve scheduling, as well as parallel programming problems. These are the two main operations performed on a queue and they should be fast in a correct implementation. Performance-wise, a proper queue implementation is expected to take O(1) time for insert and delete operations. With a queue you remove the item least recently added ( first-in, first-out or FIFO) and with a stack you remove the item most recently added ( last-in, first-out or LIFO).
Queues are similar to stacks and the difference between them is in removing items: The only way to interact with the items in the queue is to add new items at the back ( enqueue) or to remove items at the front ( dequeue) of the pipe. While the items are in the queue, a solid metal pipe, you can’t get at them. New items (water molecules, ping-pong balls, …) are put in at one end and travel to the other where you or someone else removes them again. Removal (serving) happens in the front of the queue, as developers receive their badges and conference swag bags and leave the queue.Īnother way to memorize the characteristics of a queue data structure is to think of it as a pipe: New additions to the line are made to the back of the queue as new people enter the conference venue and “queue up” to receive their badges. Imagine a line of Pythonistas waiting to pick up their conference badges on day one of P圜on registration. Here’s a real-world analogy for a first-in, first-out queue: Unlike lists or arrays, queues typically don’t allow for random access to the objects they contain. The insert and delete operations sometimes called enqueue and dequeue.
#Python queue how to#
How to implement a FIFO queue data structure in Python using only built-in data types and classes from the standard library.Ī queue is a collection of objects that supports fast first-in, first-out (FIFO) semantics for inserts and deletes.
0 kommentar(er)
