Click here to Skip to main content
14,603,732 members

Simple and Multithreading queue classes

Rate this:
1.72 (6 votes)
Please Sign up or sign in to vote.
1.72 (6 votes)
2 Feb 2006
Simple and Multithreading queue classes

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Alexander Kovachev
Web Developer
United States United States
No Biography provided

Comments and Discussions

 
QuestionQuestion for License Pin
jm_120419-Aug-18 19:24
Memberjm_120419-Aug-18 19:24 
Generalupdate version - without copy Pin
Sadru7-Feb-09 21:24
MemberSadru7-Feb-09 21:24 
template <class type=""> class SafeQueue; // forward declaration
template <class type=""> class _safe_queue_item
{
public:
Type value;
_safe_queue_item *next;
_safe_queue_item() { next=NULL;};
_safe_queue_item(const Type &val) {
value=val;
next=NULL;
};
~_safe_queue_item() {};
void DeleteQueue() { // delete all items
if(next!=NULL) next->DeleteQueue();
delete this;
};
friend class SafeQueue<type>; // the one and the only one friend
// who can use this class
};

template <class type=""> class SafeQueue
{
CRITICAL_SECTION lock;
_safe_queue_item<type> *first; // head pointer
_safe_queue_item<type> *last; // Tail pointer

public:
BOOL Push(_safe_queue_item<type> *nt) // Add the element at the end of queue
{ // user provided element
EnterCriticalSection(&lock);
nt->next = NULL;
if (first==NULL)
last=first=nt;
else {
last->next=nt;
last=nt;
}
LeaveCriticalSection(&lock);
return TRUE;
};
BOOL Push(const Type & item) // Add new element, initialize and copy element
{ // at the end of queue
EnterCriticalSection(&lock);
_safe_queue_item<type> *next=new _safe_queue_item<type> (item);
if (first==NULL)
last=first=next;
else {
last->next=next;
last=next;
}
LeaveCriticalSection(&lock);
return TRUE;
};
bool Pop(_safe_queue_item<type> ** val) { // Retrieve element from the head of queue
EnterCriticalSection(&lock); // and remove it from queue - return to caller

_safe_queue_item<type> *oldFirst= first;
if(first==NULL)
{
LeaveCriticalSection(&lock);
return false;
} else {
*val=oldFirst;
first=first->next;
LeaveCriticalSection(&lock);
}
return true;
};
Type Pop() { // Retrieve element from the head of queue,
EnterCriticalSection(&lock); // and remove it from queue - deletes the element
Type val;
_safe_queue_item<type> *oldFirst=first;
if(first==NULL)
{
LeaveCriticalSection(&lock);
throw "SB Queue underflow !";
} else {
val=first->value;
first=first->next;
delete oldFirst;
LeaveCriticalSection(&lock);
}
return val;
};
BOOL IsEmpty() { // check if queue is empty
EnterCriticalSection(&lock);
BOOL empty=(first==NULL);
LeaveCriticalSection(&lock);
return empty;
};
void Reset() { // reset contents of the queue
EnterCriticalSection(&lock);
if(first!=NULL) {
first->DeleteQueue();
first=NULL;
}
LeaveCriticalSection(&lock);
};
SafeQueue() {
InitializeCriticalSection( &lock);
first=last=NULL;
};
~SafeQueue() { // destructor - deletes all
EnterCriticalSection(&lock);
if(first!=NULL)
first->DeleteQueue();
first=NULL;
LeaveCriticalSection(&lock);
DeleteCriticalSection(&lock);
};
};
General:-* Pin
svetla9-Apr-08 21:41
Membersvetla9-Apr-08 21:41 
GeneralNot exception safe Pin
Graham Shanks3-Feb-06 5:08
MemberGraham Shanks3-Feb-06 5:08 
GeneralThe color of the text is not welcome Pin
ucc8012-Feb-06 22:59
Memberucc8012-Feb-06 22:59 
GeneralNot safe Pin
Johann Gerell2-Feb-06 22:02
MemberJohann Gerell2-Feb-06 22:02 
GeneralThe submission wizard screwed up the formatting Pin
Alexander Kovachev2-Feb-06 16:24
MemberAlexander Kovachev2-Feb-06 16:24 
GeneralRe: The submission wizard screwed up the formatting Pin
toxcct2-Feb-06 21:56
Membertoxcct2-Feb-06 21:56 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Article
Posted 2 Feb 2006

Stats

48K views
843 downloads
20 bookmarked