A queue (pronounce like the letter 'Q') is a container like a stack. It hold a bunch of numbers but follows a rule for adding and removing. A queue holds a FIFO rule. The First one In is the First one Out. A queue is basically a line of numbers, like the ones you use to form in grade schools. (Except these are a lot better since there are not cuts or budges.) In a queue there is a designated front and back. Numbers go in the back and come out the front. Adding to a queue is called enqueueing (pronouced 'N'-'Q'-"ing") and removing is called dequeuing (pronouced 'D'-'Q'-"ing").
The queue can implement all normal container functions as well and enqueue() and dequeue. In addtion to these a front() and back() would be useful.
A queue can easily be implemented with a linked list. It can hold as much as it needs, and enqueue and dequeue can easily be implemented with a tail pointer. However is can be implemented with an array just as easily.
If the array is treated circularly then the trouble of coping data to move the queue up one dissapears. If the front and back are just positions on the array. When something is enqueued, it is added to the back. If something is dequeued the front moves up one index. Now if the array gets full, just write over the old data that is "before" the front". The best image is a if the array is a thing strip of paper taped together. Where the pages meet is the 0 and size-1 indexes. However data can be added and removed without worrying about space.
This array implementation will need some additional functions and data menbers to help it out. There will like with the Set an ensure() and trim() to adjust the array size as needed. Since the size of the array may not be the size of the queue a maxsize() will return the maximum size the queue can hold. There will be two integers to hold the size of the queue and the array. There will also be another two integers to hold the indexes of the front and back positions of the queue.
class Queue
{
public:
Queue(int maxsize=10);
Queue(const Queue& q);
~Queue();
void enqueue(int num);
void dequeue(int num);
int front();
int back();
void ensure(int sz);
void trim();
int size();
int maxsize();
bool empty();
Queue& operator=(const Queue& rhs);
private:
int theSize;
int theArraySize;
int theFront;
int theBack;
int theQueue[];
};
Another type of the queue is a Priority queue. It is just like a queue except the elements are adding according to priority. For example lets same the lessor the integer value the higher priority. With a list of "11356" a enqueue of 2 will make it "112356". The two can skip over 3, 5, and 6 since it has a higher priority.
The basic uses of queue are for actual simluations of lines. Common problems are organizing who goes first in what line or figuring the timing of a wait in line.
| Function | Evaluation | Order |
|---|---|---|
| Queue() | Simple declarations. | O(1) |
| Queue(Queue) | Simple declarations and linear aplications of enqueue and dequeue, O(n*en+de). | O(n) |
| ~Queue() | Simple deletion. | O(1) |
| enqueue() | Simple operations with at most an ensure. | O(1) or O(ensure) |
| dequeue() | Simple operatoins. | O(1) |
| front() | Simple return. | O(1) |
| back() | Simple return. | O(1) |
| ensure() | Simple operations with a linear application of enqueue and dequeue, and more simple opearations. O(1+n*1+1) | O(n) |
| trim() | Just like ensure with simple and linear operations. | O(n) |
| size() | Simple return. | O(1) |
| maxsize() | Simple return. | O(1) |
| empty() | Simple return. | O(1) |
| = | Simple operations and a linear copy. | O(n) |
The queue is like a stack on order of performance. It is constant in all its applications, but slow on resizing.
This circular implementation can also be done with a linked list. It is just like a normal list but the last node points to the first one, and a tail is kept instead of a head.
With this implementation the queue's performace stays the same since linear copiering for deep assignments are still needed. The only difference is that there is no concern for memory allocation (by the user).
Prev -- Back to Portal -- Next