Introduction
This article describes a C++ Queue class (simple and MT safe version). A queue is a data structure which is a FIFO list. This means that you can push elements and also you can "pull" elements, and each time you pull an element you pull the element which was first pushed (First-In-First-Out). Queues are great for buffering data or scheduling events. One characteristic of a queue is that it does not have a specific capacity. Regardless of how many elements are already contained, a new element can always be added. It can also be empty, at which point removing an element will be impossible until a new element has been added again.
The class interface
Because the queue class is usually used in multi-tasking enviroinment, I put the code for both simple and multi-threading safe classes.
template <class Type> class Queue
{
public:
Queue();
~Queue();
BOOL Push(const Type & item);
Type Pop();
BOOL IsEmpty();
void Reset();
};
template <class Type> class SafeQueue
{
public:
Queue();
~Queue();
BOOL Push(const Type & item);
Type Pop();
BOOL IsEmpty();
void Reset();
};
Using the code
There are 3 most important methods of this class, which actually represent the FIFO logic.
BOOL Push(const Type & item);
Push()
method adds (pushes) a new first element in the queue.
Type Pop();
Pop()
method retrieves (pops) the last element of the queue. If there are no elements in the queue, it throws an exception. To avoid the exception use IsEmpty()
.
BOOL IsEmpty();
IsEmpty()
method checks if there are any elements in the queue.
Single-threaded Example
Here is a brief example how to use the Queue
class. It pushes 3 string to a list, and afterwards prints the whole queue element by element in the order of adding.
#include "queue.h"
#include "string"
#include "stdio.h"
using std::string;
int main()
{
Queue<string> myQueue;
myQueue.Push("Mr. ");
myQueue.Push("Bill ");
myQueue.Push("Gates ");
while(!myQueue.IsEmpty())
{
string s=myQueue.Pop();
puts(s.c_str());
}
return 0;
}
Multi-threaded Example
Here is a more interesting example how to use the SafeQueue
class. It has two tasks. The first one pushes 3 strings to a list, and the second one prints element by element in the order of adding.
#include "safequeue.h"
#include "string"
#include "stdio.h"
#include "process.h"
using std::string;
SafeQueue<string> myQueue;
volatile BOOL done=FALSE;
void testThread(void *param)
{
myQueue.Push("Mr. ");
::Sleep(1000);
myQueue.Push("Bill ");
::Sleep(1000);
myQueue.Push("Gates ");
::Sleep(1000);
done=TRUE;
}
int main()
{
_beginthread( testThread, 0, NULL );
while(!done)
{
if(!myQueue.IsEmpty())
{
string s=myQueue.Pop();
puts(s.c_str());
}
}
return 0;
}
The "safe" queue
The SafeQueue
class uses a critical section internally. The section is locked for each method call. This gurantees that no two callers will push/pop data at the same time.