Queue: C++ Data Structure

Queue:

The queue can be implemented in a number of ways, one can use arrays or implement it something similar to linked-lists. Here we use the latter.

First, we create a class called as a node, this represents each node in our queue.

class Node{
private:
  int data;
  Node* next;
public:
  int getData(){
    return data;
  }
  Node* getNext(){
    return next;
  }
  void setData(int a){
    data = a;
  }
  void setNext(Node* n){
    next = n;
  }
};

Nothing new here, a simple class with setters and getter functions.

Now we implement a very basic Queue as follows:

class Queue{
private:
  Node* tail =NULL, *head=NULL;
public:
  void enqueue(int data){
    Node* new_node = new Node();
    new_node->setData(data);
    new_node->setNext(NULL);
    if(tail==NULL){
      tail = new_node;
      head = new_node;
    }else{
      tail->setNext(new_node);
      tail = new_node;

    }
  }

  int deque(){
    if(head==NULL)return -1;
    int temp = head->getData();
    head = head->getNext();
    return temp;
  }
  bool isempty(){
    return head==NULL;
  }
};

The private fields contain a pointer to the tail and the head of the queue. You can only add data at the tail of the queue and access it from the head.

The public field contains two functions, enqueue adds data at the end of the queue, and dequeue removes the head from the top and return the data it contained previously.

The public function isempty checks if the queue is empty, it returns true if it is, else returns false.