Queue (data structure)

Queue (data structure)

A queue (pronounced /kjuː/) is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only) operations on the collection are the addition of entities to the rear terminal position and removal of entities from the front terminal position. This makes the queue a First-In-First-Out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed. This is equivalent to the requirement that whenever an element is added, all elements that were added before have to be removed before the new element can be invoked. A queue is an example of a linear data structure.

Queues provide services in computer science, transport and operations research where various entities such as data, objects, persons, or events are stored and held to be processed later. In these contexts, the queue performs the function of a buffer.

Queues are common in computer programs, where they are implemented as data structures coupled with access routines, as an abstract data structure or in object-oriented languages as classes. Common implementations are Circular buffers and Linked lists.

Operations

Common operations from the C++ Standard Template Library include the following:;bool empty(): Returns True if the queue is empty, and False otherwise.;T& front(): Returns a reference to the value at the front of a non-empty queue. There is also a constant version of this function, "const T& front()".;void pop(): Removes the item at the front of a non-empty queue.;void push(const T& foo): Inserts the argument foo at the back of the queue.;int size(): Returns the total number of elements in the queue

Example C++ Program

Based on an example in Ford and Topp "Data Structures with C++" page 387.

queue< char > theQueue; // creates a queue of chars named "theQueue"theQueue.push('a'); // theQueue now contains "a"theQueue.push('b'); // theQueue now contains "a b"theQueue.push('c'); // theQueue now contains "a b c"cout << "theQueue contains: a b c" << endl << endl;while( !theQueue.empty() ) // while the queue is not empty...{ cout << "Size = " << theQueue.size() << endl; // ...output queue size cout << "Value at front = " << theQueue.front() << endl << endl; // ...and output the first element value theQueue.pop(); // ...and remove it}

Representing a Queue

The defining attribute of a queue data structure is the fact that allows access to only the front and back of the structure. Furthermore, elements can only be removed from the front and can only be added to the back. In this way, an appropriate metaphor often used to represent queues is the idea of a checkout line ("Ford/Topp p. 385"). Other examples of queues are people traveling up an escalator, machine parts on an assembly line, or cars in line at a gas station. The recurring theme is clear: queues are essentially waiting lines.

In each of the cases, the customer or object at the front of the line was the first one to enter, while at the end of the line is the last to have entered. Every time a customer finishes paying for their items (or a person steps off the escalator, or the machine part is removed from the assembly line, etc.) that object leaves the queue from the front. This represents the queue “dequeue” function. Every time another object or customer enters the line to wait, they join the end of the line and represent the “enqueue” function. The queue “size” function would return the length of the line, and the “empty” function would return true only if there was nothing in the line.

Practical Usage

Queues can be very useful in many different situations. As seen in the grocery store metaphor, they are a data structure ordered as first-in-first-out (FIFO) or first-come-first-served (FCFS). This specific type of structure is used for applications that require items to be retrieved in their order of addition to the list (their order of occurrence). Examples of such applications could be an event scheduler (perhaps for a hair salon, or massage parlor), a simple to-do list, or specific operations of the Radix sort algorithm.

Additional Information

Theoretically, one characteristic of a queue is that it does not have a specific capacity. Regardless of how many elements are already contained, a new element can always be added. It can also be empty, at which point removing an element will be impossible until a new element has been added again.

A practical implementation of a queue e.g. with pointers of course does have some capacity limit, that depends on the concrete situation it is used in. For a data structure the executing computer will eventually run out of memory, thus limiting the queue size. Queue overflow results from trying to add an element onto a full queue and queue underflow happens when trying to remove an element from an empty queue.

A bounded queue is a queue limited to a fixed number of items.

ee also

*Array
*Circular buffer
*Congestion
*Deque
*Differential execution
*Linked list
*Pipeline
*Priority queue
*Queueing theory
*Radix sort
*Spooling
*Stack - the "opposite" of a queue: LIFO (Last In First Out)

References

* Donald Knuth. "The Art of Computer Programming", Volume 1: "Fundamental Algorithms", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4. Section 2.2.1: Stacks, Queues, and Deques, pp. 238&ndash;243.
* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 10.1: Stacks and queues, pp.200&ndash;204.
* William Ford, William Topp. "Data Structures with C++ and STL", Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 8: Queues and Priority Queues, pp.386&ndash;390.
* Adam Drozdek. "Data Structures and Algorithms in C++", Third Edition. Thomson Course Technology, 2005. ISBN 0-534-49182-0. Chapter 4: Stacks and Queues, pp.137&ndash;169.

External links

* Pointers to [http://web-cat.cs.vt.edu/AlgovizWiki/Queues queue visualizations]
*Queue program in c++ [http://24bytes.com/Queue.html Queue ]
* STL Quick Reference: [http://www.halpernwightsoftware.com/stdlib-scratch/quickref.html#containers14 Queue]
*
* [http://www.qdecoder.org/goto/qQueue.html qDecoder's C/C++ circular queue implementation] &mdash; opensource library which supports FIFO and STACK for the user objects


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Data structure — In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.[1][2] Different kinds of data structures are suited to different kinds of applications, and some are highly …   Wikipedia

  • Heap (data structure) — This article is about the programming data structure. For the dynamic memory area, see Dynamic memory allocation. Example of a complete binary max heap In computer science, a heap is a specialized tree based data structure that satisfies the heap …   Wikipedia

  • Stack (data structure) — In computer science, a stack is an abstract data type and data structure based on the principle of Last In First Out (LIFO) . Stacks are used extensively at every level of a modern computer system. For example, a modern PC uses stacks at the… …   Wikipedia

  • Persistent data structure — In computing, a persistent data structure is a data structure which always preserves the previous version of itself when it is modified; such data structures are effectively immutable, as their operations do not (visibly) update the structure in… …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Container (data structure) — For the abstract notion of containers in Type theory, see Container (Type theory). In computer science, a container is a class, a data structure[1][2], or an abstract data type (ADT) whose instances are collections of other objects. In other… …   Wikipedia

  • Active data structure — A data structure with an associated thread or process that performs internal operations to give the external behavior of another, usually more general, data structure.For example, a queue is usually considered to be unbounded. However, actual… …   Wikipedia

  • Pile (data structure) — A pile is an abstract data structure for storing data in a loosely ordered way. There are two different usages of the termOrdered dequeThe first version combines the properties of the deque and a priority queue and may be described as an ordered… …   Wikipedia

  • data structure — noun An organization in software of data that allows more optimal searching, categorizing, or storage of information. Examples: matrix, stack, queue, dequeue, list …   Wiktionary

  • Queue — can mean: * Queue area, where a line of people wait. The verb queue means to form a line, and to wait for services. Queue is also the name of this line * Queueing theory, the study of waiting lines * Queue (data structure), in computing, a type… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”