A queue is a data structure that is extremely similar to a stack. However, unlike a stack, which has a LIFO property, a queue has a FIFO (first in first out) property.
Rules of the queue:
1. An item can only be added in the back.
2. An item can only be removed from the front.
3. An item can only be accessed from the front.
4. If the queue is empty, items cannot be removed or accessed.
In stack terms, those rules are:
1. An item can only be added at the top.
2. An item can only be removed from the bottom.
3. An item can only be accessed from the bottom.
4. If the queue is empty, items cannot be removed or accessed.
So, pretty much, the only major difference is that the FIFO property of queues makes it so that the items of the queue and the stack are accessed and removed from opposite ends.
There are some queue terms that you should know:
Enqueue- Add an item to the back, which in a stack is called pushing
Dequeue-Remove an item from the front, which is like popping an item from the bottom of the stack instead of the top
Back- The queue’s equivalent to the top of a stack
Front- The queue’s equivalent to the bottom of a stack
Like stacks, queues can be implemented either as arrays or linked lists. I will start this tutorial by showing them as arrays.
One problem created by the queue property when making an array queue is that you can only enqueue at one end and only dequeue at the opposite end. Because of this, eventually the whole array will be shifted to one end, making it so you have to shift it back to the other end with a function that has a runtime of O(n). This disadvantage looks like this:
However, if we “circularize” the array, then we will not have this problem. To do this, we draw the array as a circle (although really that’s just for us; the computer implements the array the same way it does with a linear array). To make it a circle, we need the following in the class:
The array itself, which will start out with five items (you can pick its initial size).
An int called capacity to keep track of the array’s maximum size
An int called currentSize to keep track of the array’s current size
An int called back, which is the array index at which the next item in the queue will be added.
An int called front, which is the array index of the item in the front of the queue.
The ArrayQueue class and its constructor therefore look like this:
class ArrayQueue
{
public:
ArrayQueue();
~ArrayQueue();
void enqueue(int x);
int dequeue();
bool isEmpty();
int frontItem();
int size();
private:
int capacity;
int currentSize;
int back;
int front;
int* queue;
void doubleSize();
};
ArrayQueue::ArrayQueue()
{
queue = new int[5];
back = 0;
front = 0;
capacity = 5;
currentSize = 0;
}
In the class constructor, the circular array queue is initialized to have its front and back at zero. This is because an array queue’s back is the index at which we will insert the next item, so when the queue is empty, back and front are equal (as you’re about to see, back and front are also briefly equal when the queue is full before we double the queue’s size).
Now, here’s the enqueue function:
void ArrayQueue::enqueue(int x)
{
queue[back] = x;
back++;//1
currentSize++;
if(back == capacity)//2
back = 0;
if(back == front)//3
doubleSize();
}
1. After back gets an item in the queue, back is increased by one so that we have the next back space open for adding another item.
2. However, if back is now at a number equal to the maximum size, back no longer indexes a space in the array, so back is set to zero, which in the circle, is the next space after size - 1.
3. If back and front are now the same index AFTER adding an item, then that means that the queue is full, so we will call a doubleSize function (explained later) to make the array bigger.
Here’s the dequeue function.
//Invariant: Dequeue is not to be used on an empty
int ArrayQueue::dequeue()
{
int x = queue[front];
front++;//1
currentSize--;
if(front == capacity)
front = 0;
return x;
}
1. Front increases by one to get the deququed item out of the queue (but still in the array, much like stacks when an element is popped out of the stack but still in the array). If front is equal to capacity, front is now moved to 0 since the array wraps around with the new circular property. If after calling dequeue front is equal to back, the queue is now empty.
Now, here are the three one-liner functions in the queue.
bool ArrayQueue::isEmpty()
{
return (currentSize == 0);
}
//Invariant: Will not be used on an empty array queue!
int ArrayQueue::frontItem()
{
return queue[front];
}
int ArrayQueue::size()
{
return currentSize;
}
Finally, we have the doubleSize function. However, I am not going to draw a picture because it’s basically just doubling the size of a dynamic array except the array is circular, so it’s really just applied knowledge from COMP 11.
void ArrayQueue::doubleSize()
{
int* big = new int[2 * capacity];//1
int loc = front;
for(int i = 0; i < currentSize; i++)//2
{
big[i] = queue[loc];
loc++;
if(loc == capacity)
loc = 0;
}
front = 0;//3
back = currentSize;
delete[] queue;
queue = big;
capacity*=2;//4
}
1. Like with increasing the size of any dynamic array, we make a new dynamic array that is twice the size of the one we are copying.
2. With this for loop, we use the index int variable loc to iterate one “lap” around the array, copying each value of the array to corresponding spaces of big starting at big[0].
3. Since we started copying to big at big[0] and ended at big[currentSize-1], we set front to 0 and back to currentSize.
4. Now that queue is pointing to big, we double capacity to account for our new array’s maximum capacity.
That’s it for array queues. Much like with stacks, you can also make queues that are implemented as linked lists. However, a singly-linked list might not be the best implementation. Why?
-You need pointers to access both the front and back of the queue because the queue property requires access to both ends.
-In addition, when you dequeue an item, you need to be able to access the second to last item in the list.
What kind of linked list has access to both ends of the list? The doubly-linked list!
And much like the way we were able to use the pre-made LinkedList class in the implementation of a linked stack, in a linked queue we can use our pre-made DList class! Having said that, take a look at the LinkedQueue class and its constructor:
class LinkedQueue
{
private:
int currentSize;
DList queue;
public:
LinkedQueue();
void enqueue(int x);
int dequeue();
bool isEmpty();
int frontItem();
int size();
//For a linked queue a destructor is not needed since the DList already has a destructor to take care of the dynamic memory.
};
LinkedQueue::LinkedQueue()
{
//The DList itself is not in the constructor since DLists come with their own constructor.
currentSize = 0;
}
Now, from here all we need to do is use function calls we already wrote to make the LinkedQueue’s member functions:
void LinkedQueue::enqueue(int x)
{
queue.insertBack(x);
currentSize++;
}
Note that for consistency with the front-back terminology of queues we are using the DList’s head as the front of the queue and the DList’s tail as the back of the queue, so since insertion in the queue is done in the back to maintain the FIFO property of the queue, we call the DList’s insertBack function and then increment currentSize by one.
Similarly, to dequeue an element from the queue, we decrement currentSize by one and then remove from the front with the DList’s removeFront.
//Invariant: Dequeue is not to be used in an empty queue.
int LinkedQueue::dequeue()
{
currentSize--;
return queue.removeFront();
}
Now, here’s the one-liners again; like with the linked stack, the one-liners use the DList to do all the work (with the exception of size, which uses currentSize.)
bool LinkedQueue::isEmpty()
{
return queue.isEmpty();
}
//Invariant: frontItem is not to be used in an empty queue.
int LinkedQueue::frontItem()
{
return queue.head -> data;
}
int LinkedQueue::size()
{
return currentSize;
}
Really the only thing that is different about linked queue one-liner functions is that they are made for a DList instead of an array.
Here is a diagram of enqueue, dequeue, and frontItem for linked queues:
One other notable point I would like to mention is that linked queues do not have a destructor since the only dynamic memory accessed when using a linked queue is the DList, and the DList class comes with a destructor of its own.
That’s it for queues. Now, before you go on to the next tutorial, something I would like you to notice is that as you saw in the last few tutorials, it is often convenient to either use classes you already wrote in new classes or modify them to make new classes. Linked lists are used in linked stacks and queues. Singly-linked lists are modified to make doubly-linked lists. you take code for a function in a class and insert into another class, the question changes from how the function works to how it is used because you will already have how it works covered. Reusability is awesome in computer science, and it’s not plagiarism that will send you to Pro 1 (unless you steal the code from SOMEONE ELSE and don’t cite them for helping you out, in which case you’re busted). In the next tutorial, we will be taking reusability to the next level with templates!
No comments :
Post a Comment