Implementing a simple queue using arrays

Question

I don't know much about arrays and queues and stacks. I know how to implement a simple queue.

#include <iostream>
#include <queue>

using namespace std;

void main()
{
    queue<char> queue1;
    queue1.push('a');
    queue1.push('b');
    queue1.push('c');
    queue1.push('d');

    while(!queue1.empty())
    {
        cout << queue1.front();
        queue1.pop();
        cout << endl;
    }

    system("pause");
}

How can I implement a simple queue using an array?

Solution 1

If your queue is based on an array, then for efficiency's sake, I would recommend creating a bounded or "circular" queue, where the max-size of the queue is fixed, and you basically have a head and tail pointer that point to the "first" and "last" positions in the queue's array, and when the tail-pointer (or an index value) moves to a position "past" the end of the array, it actually moves back to the beginning of the array. An unbounded queue based on an array would be horribly inefficient, as you would need to keep reallocating memory each time you fill up the max-size of the array, and/or attempt to re-shuffle elements down the array when you remove the first element of the queue.

Using integral-type array indexes for head and tail rather than actual pointer types, along with a counter for determining the overall number of items in your queue, your enqueue and dequeue functions could look as simple as:

template<typename T>
bool queue<T>::enqueue(const T& item)
{
    if (count == array_size)
        return false;

    array[tail] = item;

    tail = (tail + 1) % array_size;
    count++;

    return true;
}

template<typename T>
bool queue<T>::dequeue(T& item)
{
    if (!count)
        return false;

    item = array[head];

    head = (head + 1) % array_size;
    count--;

    return true;
}

You can extend this concept to whatever other functions you'd like, i.e., if you'd rather have a separate functions like the STL uses for accessing the head of the queue and actually "removing" an element from the queue.

Solution 2

NOTE: While simulating an array(linear data storage) as a circular data storage and maintaining the properties of Queue, one cell will always be unused. Hence, the maximum capacity of array will be 5 for the array having 6 cells. The c++ code below is self explanatory. Also, see The Linked List Based Implementation of Queue.

/*Implementation of queue with basic operation using arrays */

#include<iostream>          
using namespace std;        
#define MAX 6               //to accomodate a maximum of 05 elements as 1 cell pointed by tail will always be vacant

void ENQUE(int key);        // ~insertion
int  DEQUEUE();             // ~deletion
void TRAVERSE();
bool isEmpty();
bool isFull ();

int Q[MAX], head=0, tail=0; /* Note: head is the side facing cashier and new person joins the queue at tail. So, from cashier point of view tail~rear and head~front.
                               Q -> [h ][][][][][][][][][][t]
                               Q -> [h,t][][][][][][][][][][] : initial configuration*/



int main(){
    int choice,val,i;
    char ch='y';

    do{
        cout<<"1. For Enqueue \n";
        cout<<"2. For Dequeue \n";
        cout<<"3. For Traverse \nYour Option : ";
        cin>>choice;

        switch(choice)
        {
            case 1 :        // insertion
                if( isFull() ){
                    cout<<"\nQueue Full !!!\n";
                    break;
                }
                cin>>val;
                ENQUE(val);
                TRAVERSE();
                break;

            case 2 :        //deletion
                if( isEmpty() ){
                    cout<<"\nQueue Empty !!!\n";
                    break;
                }
                cout<<"\nDeleted element from Queue : "<<DEQUEUE()<<endl;
                TRAVERSE();
                break;

            case 3 :        //traversal
                if( isEmpty() ){
                    cout<<"\nQueue Empty !!!\n";
                    break;
                }
                TRAVERSE();
                break;

            default :
                cout<<"Please choose 1/2/3 !!! \n";
        }
        cout<<"\nDo you want to continue(y/n):";
        cin>>ch;

    }while(ch=='y'||ch=='Y');  //end of do loop

    return 0;
}

void ENQUE(int x){

    Q[tail] = x;
    tail =(tail+1)%MAX ;       //OR tail =  (tail==MAX) ? 0 : tail+1 ; */
}

int  DEQUEUE(){

    int temp =Q[head];
    head =(head+1)%MAX ;       //OR head =  (head==MAX) ? 0 : head+1 ; */
    return temp;
}

void TRAVERSE(){
    int i;                              //simple  case: Q -> [  ][ ][h7][8][9][5t][  ][  ][  ][  ][  ]
    for(i=head; i!=tail; i=(i+1)% MAX)  //complex case: Q -> [16][t][  ][ ][ ][h5][11][12][13][14][15]
        cout<<Q[i]<<" ";
    cout<<endl;
}

bool isEmpty(){
    if(head == tail)
        return true;
    else
        return false;
}

bool isFull(){
    if( (tail == MAX-1 && head == 0) || (head == tail + 1)  )
        return true;
    else
        return false;
}

A video tutorial of the same can be seen here : Data structures: Array implementation of Queue

Comments

[Mark Ransom]

If you don't understand enough to implement it from scratch, just keep using the std version as you've demonstrated. If this is homework, just remember that a queue is first in, first out.

[Kerrek SB]

I dispute your statement that you "know how to implement a simple queue". So far you have only demonstrated that you can use a library class called "queue".

[Raghuram]

You can implement queue with a circular buffer/circular array. Check this link to get some idea vias.org/cppcourse/chap20_05.html

[Lu Yas]

can i apply the same thing on a stack?

[Jason]

Yes, definitely, although a stack would not "wrap-around" like a queue can since you only add and remove the "top" element.

[Sumit]

Can cause an issue due to 'tail' overflow.

[Jason]

If you use unsigned long types, then it will take a while to overflow tail ... there are other ways this could be done as well in order to avoid that issue, I was using this example for simplicity's sake.

[Sumit]

Implementing using a head and a count avoids many of the problems.

[Blastfurnace]

The literal in your MAX definition should probably be just 6. The leading 0 makes it an octal literal. Not a problem in this specific case but it can be a potential source of bugs.

[Mohsin]

can you please provide a working example of these operations?

[Patrick Trentin]

The suggestion by @Sumit appears to be very sensible, perhaps this answer should be edited since it is the accepted one.