Slide 1
Data Structures and Abstractions
Queues
Lecture 22
*
Queues
Queues are ADS that emulate, for example, a queue at the movies: you can only get on the back of the queue, and off at the front of the queue.
There are only two operations allowed on a queue: [1]
Enqueue (something on to it)
Dequeue (something off it)
Plus two query methods:
Empty ()
Full ()
Since the last thing on is the last thing off, they are known as FIFO (First In, First Out) data structures, or sometimes LILO (Last In, Last Out).
*
[1] This abstraction is different to the abstraction presented in see the Chapter on Stacks and Queues in the textbook. What is the difference? Look at the abstract class queueADT in the text.
Again as indicated when we looked at sets, there are commonly available abstractions of sets which try to be everything to everyone. To keep to the minimal and complete approach we use the abstraction shown in this slide. Also see the chapter on Elementary Data Structures in the reference book Introduction to Algorithms http://prospero.murdoch.edu.au/record=b2156975.
Queue Implementation
Queues can be implemented any way you want, the encapsulation of the container used ensures that it does not matter.
As long as it only has Enqueue, Dequeue, Empty and Full, then it is a queue.
Most commonly they are implemented using arrays, lists or an STL structure, with the STL Queue being more relevant.
However since none of these exactly fit the required minimal abstraction we are after, they should always be encapsulated.
*
Error Conditions for Queues
If you try to Enqueue() onto a queue that has no free memory, then you get overflow.
If you try to Dequeue() from an empty queue then you have underflow.
So Enqueue() and Dequeue() return a boolean to indicate if one of these errors has occurred.
In the animation that follows, two approaches are used.
The internal container is an array
The internal container is a linked list
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
m_front
m_front
NULL
m_back
m_back
m_size
0
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
10
m_front
NULL
m_back
m_back
Enqueue(10)
m_front
m_back
m_size
1
0
10
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
10
1
m_front
NULL
m_back
m_back
Enqueue(1)
m_front
m_back
m_size
2
1
10
1
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
10
1
23
m_front
NULL
m_back
m_back
Enqueue(23)
m_front
m_back
m_size
3
2
10
1
23
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
10
1
23
m_front
NULL
m_back
Dequeue(num)
m_front
m_back
num
10
m_front
m_size
3
2
10
1
23
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
1
23
m_front
NULL
m_back
Dequeue(num)
m_front
m_back
num
1
m_front
m_size
2
1
1
23
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
23
m_front
NULL
m_back
Dequeue(num)
m_front
m_back
num
23
m_front
m_size
0
1
m_back
m_front
23
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
m_front
NULL
m_back
Dequeue(num)
m_back
num
m_front
UNDERFLOW
m_size
0
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
m_front
NULL
m_back
Dequeue(num)
m_back
num
m_front
m_size
0
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
m_front
12
m_front
NULL
m_back
m_back
Enqueue(12)
m_front
m_back
m_size
1
0
12
*
Queue Example (Animation)
* of 41
Array Implementation
Linked List Implementation
12
45
m_front
NULL
m_back
m_back
Enqueue(45)
m_front
m_back
m_size
2
1
12
45
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
m_front
NULL
m_back
m_back
Enqueue(23)
m_front
m_back
m_size
3
2
12
45
23
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
87
m_front
NULL
m_back
m_back
Enqueue(87)
m_front
m_back
m_size
4
3
12
45
23
87
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
87
9
m_front
NULL
m_back
m_back
Enqueue(9)
m_front
m_back
m_size
5
4
12
45
23
87
9
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
87
9
63
m_front
NULL
m_back
m_back
Enqueue(63)
m_front
m_back
m_size
6
5
12
45
23
87
9
63
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
87
9
63
6
m_front
NULL
m_back
m_back
Enqueue(6)
m_front
m_back
m_size
7
6
12
45
23
87
9
63
6
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
87
9
63
6
m_front
NULL
m_back
Enqueue(22)
m_front
m_back
m_size
7
OVERFLOW
12
45
23
87
9
63
6
22
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
12
45
23
87
9
63
6
m_front
NULL
m_back
Dequeue(num)
m_front
m_back
m_size
7
m_front
6
12
45
23
87
9
63
6
22
*
Queue Example (Animation)
Array Implementation
Linked List Implementation
31
45
23
87
9
63
6
m_front
NULL
m_back
Enqueue(31)
m_back
m_size
6
m_front
7
m_back
END
12
45
23
87
9
63
6
22
31
*
Study the array animation to see what happens when there are a series of enqueues followed by dequeues.
Array Enqueue Algorithm
ENQUEUE (DataType data): boolean
IF m_size >= ARRAY_SIZE-1
return FALSE
ELSE
Increment m_size
Increment m_back MOD ARRAY_SIZE [1]
Place data at position m_back
return TRUE
ENDIF
END Enqueue
*
[1]
What is the MOD operation doing – see the Chapter on Stacks and Queues in the textbook section on “Implementation of Queues as Arrays”. Go through the examples shown in the text where circular queues are explained.
Array Dequeue Algorithm
DEQUEUE (DataType data): boolean
IF m_size == 0
return FALSE
ELSE
data = data at position m_front
Increment m_front MOD ARRAY_SIZE
Decrement m_size
IF m_size == 0
m_front = -1
m_back = -1
ENDIF
return TRUE
ENDIF
END Dequeue
*
Linked List Enqueue Algorithm
ENQUEUE (DataType data): boolean
IF there is memory on the heap
Get newNode from the heap
IF m_front is NULL
m_front = newNode
m_back = newNode
ELSE
m_back.next = newNode
m_back = newNode
ENDIF
return TRUE
ELSE
return FALSE
ENDIF
END Enqueue
m_front
NULL
66
76
m_back
*
Linked List Dequeue Algorithm
DEQUEUE (DataType data): boolean
IF m_front == NULL
return FALSE
ELSE
data = m_front.data
oldNode = m_front
IF m_back == m_front
m_front = NULL
m_back = NULL
ENDIF
m_front = oldNode.next
release oldNode memory
oldNode = NULL
return TRUE
ENDIF
END Dequeue
m_front
NULL
66
76
m_back
oldNode
*
Using the STL
The other possibility is to use one of the STL structures.
If using a vector or list, then the algorithms above barely change.
However, remember that the structure must still be encapsulated in a class, otherwise it will not have just the Enqueue() and Dequeue() that it is supposed to have.
Finally, there is the STL queue class, (requiring
However, even this should be encapsulated, because it does not conform to the standard queue description! [1]
*
[1] Again the abstraction is different. You join a queue and you leave a queue. See the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures” (10). You will see that how removed the STL queue is from the abstract queue. http://prospero.murdoch.edu.au/record=b2156975
Non Standard Features of the STL queue
Its Enqueue method is called push() [1]
Its Dequeue method is called pop().
Its pop() method, only removes the data, it does not pass it back to the calling method.
In fact there is a front() method which returns a reference to the front of the queue.
Neither dequeue(), front() nor enqueue() return a boolean: overflow and underflow must be checked separately.
Therefore it is best that the STL queue must be encapsulated. [2]
*
[1] Better abstractions than push and pop (stack ops) can be join and leave. You join a queue and you leave a queue.
[2] See the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures” (10). You will see that how removed the STL queue is from the abstract queue. http://prospero.murdoch.edu.au/record=b2156975
Queue Header File using STL queue
// Queue.h
//
// Queue class
//
// See actual code provided in the zip file
//——————————————-
#ifndef MY_QUEUE
#define MY_QUEUE
//——————————————-
#include
#include
using namespace std;
//——————————————-
*
template
class Queue // minimal and complete
{
public:
Queue () {};
~Queue () {};
bool Enqueue(const T &data);
bool Dequeue (T &data);
bool Empty () const {return m_queue.empty();}
private:
queue
};
* of 41
*
//——————————————-
// It is a template, so we have to put all the code
// in the header file
//——————————————-
template
bool Queue
{
bool okay = true;
try
{
m_queue.push(data); // calls STL queue method
}
catch (…)
{
okay = false;
}
return okay;
}
*
//——————————————-
template
bool Queue
{
if (m_queue.size() > 0)
{
data = m_queue.front();
m_queue.pop();
return true;
}
else
{
return false;
}
}
//——————————————-
#endif
*
Simple (but interesting) Example of Queue Use
// IntQueueTest Program
//
// Version
// original by – Nicola Ritter
// modified by smr
//
//———————————————————
#include “Queue.h”
#include
#include
using namespace std;
//———————————————————
const int EVENT_COUNT = 20;
const int MAX_NUM = 100;
//———————————————————
typedef Queue
typedef Queue
//———————————————————
*
void DoEvents ();
void AddNumber (IntQueue &aqueue);
void DeleteNumber (IntQueue &aqueue);
void TestOverflow();
//———————————————————
int main()
{
DoEvents ();
cout << endl;
system("Pause");
cout << endl;
TestOverflow();
cout << endl;
return 0;
}
//---------------------------------------------------------
*
void DoEvents ()
{
IntQueue aqueue;
// Seed random number generator
srand (time(NULL));
for (int count = 0; count < EVENT_COUNT; count++)
{
// Choose a random event
int event = rand() % 5;
// Do something based on that event type, biasing
// it towards Adding
if (event <= 2) // event = 0, 1 or 2
{
AddNumber (aqueue);
}
else // event = 3 or 4
{
DeleteNumber (aqueue);
}
}
// aqueue is local so destructor for aqueue is called when routine finishes.
}
//---------------------------------------------------------
*
void AddNumber (IntQueue &aqueue)
{
// Get a random number
int num = rand() % (MAX_NUM+1);
// Try adding it, testing if the aqueue was full
if (aqueue.Enqueue(num))
{
cout.width(3);
cout << num << " added to the queue" << endl;
}
else
{
cout.width(3);
cout << "Overflow: could not add " << num << endl;
}
}
//---------------------------------------------------------
*
void DeleteNumber (IntQueue &aqueue)
{
int num;
if (aqueue.Dequeue(num))
{
cout.width(3);
cout << num << " deleted from the queue" << endl;
}
else
{
cout << "IntQueue is empty, cannot delete" << endl;
}
}
//---------------------------------------------------------
*
void TestOverflow()
{
Queue
int count = 0;
// Keeping adding numbers until we run out of space, will take //time
while (mqueue.Enqueue(count))
{
count++;
cout << "Count is " << count << endl;
}
}
//---------------------------------------------------------
*
Screen Output
IntQueue is empty, cannot delete
79 added to the queue
79 deleted from the queue
IntQueue is empty, cannot delete
2 added to the queue
2 deleted from the queue
IntQueue is empty, cannot delete
72 added to the queue
72 deleted from the queue
88 added to the queue
88 deleted from the queue
22 added to the queue
5 added to the queue
22 deleted from the queue
37 added to the queue
46 added to the queue
74 added to the queue
58 added to the queue
5 deleted from the queue
37 deleted from the queue
Press any key to continue . . .
Count is 1
Count is 2
Count is 3
Count is 4
Count is 5
Count is 6
Count is 7
Count is 8
Count is 9
Count is 10
Count is 11
Count is 12
Count is 13
Count is 14
Count is 15
Count is 16
Count is 17
...
At 300,000 I stopped: it was just too boring
*
TestOverflow is going to take a while when adding a few bytes at a time.
Advantages of Implementations
It is assumed for each of the containers below, that the Queue encapsulates it in its own class.
Array Linked List list/vector/deque STL queue
Available in all languages. Full memory control Easy to code Easiest to code
Memory ‘never’ runs out. [1]
Memory ‘never’ runs out. [1] Memory ‘never’ runs out. [1]
*
1
It can run out if the physical resources run out. RAM and virtual ram
Disadvantages of Implementations
It is assumed for each of the containers below, that the Queue encapsulates it in its own class.
Array Linked List list/vector/deque STL queue
Can run out of space easily. Difficult to code as it uses pointers. Excess code sitting ‘behind’ the implementation, increasing the size of the program. Excess code sitting ‘behind’ the implementation, increasing the size of the program.
Messy to code, because m_back ends up in front of m_front Only available in C++. Only available in C++.
*
Readings
Textbook: Stacks and Queues, entire section on Queues
STL Queue: http://en.cppreference.com/w/cpp/container/queue
For more details of Queues with some level of language independence, see the reference book, Introduction to Algorithms section on “Stacks and Queues” in the chapter on “Elementary Data Structures”. You will see that how removed the STL queue is from the abstract queue we are after.