Editing Queue

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 11: Line 11:
 
Unlike with a [[stack]], a ''peek'' operation cannot be implemented on a queue as a pop followed by a push. (The ''test if empty'' operation is still the same as the ''find size'' operation followed by a test of whether or not the size is zero.)
 
Unlike with a [[stack]], a ''peek'' operation cannot be implemented on a queue as a pop followed by a push. (The ''test if empty'' operation is still the same as the ''find size'' operation followed by a test of whether or not the size is zero.)
  
==Terminology==
+
=Terminology=
 
The term ''queue'' is based off of real-life queues; they are often referred to as ''lines'', as in the case of a queue for a ride in an amusement park. In a queue like this, we join the end of the queue (become ''last'') and wait until we are at the front (become ''first'') before we are popped (let in). In computer science, the most recently pushed element is ''last'', whereas the least recently pushed element is ''first''. An element can be described as ''before'' another if the latter was pushed later; the latter is referred to as  being ''after'' the former. To ''push'' means to add an element, and to ''pop'' means to remove an element.
 
The term ''queue'' is based off of real-life queues; they are often referred to as ''lines'', as in the case of a queue for a ride in an amusement park. In a queue like this, we join the end of the queue (become ''last'') and wait until we are at the front (become ''first'') before we are popped (let in). In computer science, the most recently pushed element is ''last'', whereas the least recently pushed element is ''first''. An element can be described as ''before'' another if the latter was pushed later; the latter is referred to as  being ''after'' the former. To ''push'' means to add an element, and to ''pop'' means to remove an element.
  
==Implementation==
+
=Implementation=
 
===Array implementation===
 
===Array implementation===
 
In an array implementation of a queue, the contents of the queue are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. This can take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the queue. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped. That is, we maintain two indices into the array: one to the front and one to the back. When we push, we add an element to the back and increment the back index; when we pop, we remove the element from the front and increment the front index. However, consider what happens if, for example, we continually push one element, then pop one, then push another, and pop another, and so on: the size of the queue doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:
 
In an array implementation of a queue, the contents of the queue are stored in consecutive indices in an array. However, we encounter a problem if we want the element in the lowest-indexed position (''i.e.'' 0 or 1) to be constantly at the front: when we pop, we have to shift over all the other elements so that the lowest-indexed position contains the ''next'' element to be popped and all elements remain contiguous. This can take <math>\mathcal{O}(N)</math> time where <math>N</math> is the number of elements currently in the queue. But we need [[Asymptotic analysis|constant time]] push/pop operations in order to make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment an index into the next element to be popped. That is, we maintain two indices into the array: one to the front and one to the back. When we push, we add an element to the back and increment the back index; when we pop, we remove the element from the front and increment the front index. However, consider what happens if, for example, we continually push one element, then pop one, then push another, and pop another, and so on: the size of the queue doesn't change much, but both indices will eventually go out of range. To fix this problem, we allow the indices to wrap around, so that incrementing the highest possible index will give the lowest possible one. This is done using the modulo operation. Following is an exemplary implementation:
Line 68: Line 68:
 
* <code>bool empty()</code>: returns <code>true</code> if the queue is empty, <code>false</code> otherwise.
 
* <code>bool empty()</code>: returns <code>true</code> if the queue is empty, <code>false</code> otherwise.
 
The <code>queue</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own queue. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator|iteration]] through the elements of the queue. In such circumstances the STL <code>queue</code> cannot be used and a custom queue must be implemented.
 
The <code>queue</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own queue. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator|iteration]] through the elements of the queue. In such circumstances the STL <code>queue</code> cannot be used and a custom queue must be implemented.
 
Note that the pop operation defined by this container is not identical to our own; it only removes the element and it does not return its value. To do both, call <code>front</code> followed by <code>pop</code>.
 
 
[[Category:Data structures]]
 

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)
Retrieved from "http://wcipeg.com/wiki/Queue"