Editing Queue
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= | |
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= | |
===Array implementation=== | ===Array implementation=== | ||
− | In an array implementation of a queue, the contents of the queue are stored in consecutive indices in an array. | + | In an array implementation of a queue, the contents of the queue are stored in consecutive indices in an array. The first element of the queue is normally at the lowest index (i.e. 0) and the last is at the highest. Following is an exemplary implementation: |
<pre> | <pre> | ||
object queue | object queue | ||
function construct(max_size) | function construct(max_size) | ||
− | let A be an array that can hold at least max_size | + | let A be an array that can hold at least max_size elements |
− | + | ||
− | + | ||
let last = 0 | let last = 0 | ||
function push(x) | function push(x) | ||
A[last] = x | A[last] = x | ||
− | last = | + | last = last + 1 |
function pop | function pop | ||
− | return_val = A[ | + | return_val = A[0] |
− | + | move memory from A[1..last] to A[0..last - 1] | |
+ | last = last - 1 | ||
return return_val | return return_val | ||
function peek | function peek | ||
− | return A[ | + | return A[0] |
function size | function size | ||
− | return | + | return last |
− | function | + | function empty |
− | last = | + | last = 0 |
</pre> | </pre> | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |