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?

Answer 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.

Answer 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