Implementing a Queue

There are many ways to hold a bundle of data in memory. Novice programmers will be aware of the array, a data structure that holds data in sequence within a block of memory. The key feature of an array is the use of indices assigned to each item in the array. This allows us to quickly recall items from memory. We can even dynamically allocate memory to the array using C++'s new and delete keywords.

In programming, just as in economics, there is no such thing as a free lunch. We pay for the speed of an array by losing the ability to change the amount of data held in an array. If we create an array to hold n elements, there is no way to make it hold n+1 elements without allocating new memory. If, for instance, we create an array holding n ints, and we want it to hold just one more int (n+1), the total cost of the operation is 2n+4. That is, if we had 100 ints and we want it to hold 101 ints instead, we would need 804 bytes of memory - 400 for the first array, 400 more for the first 100 intes of the second array, and 4 more for the last int.

If we are willing to sacrifice a bit of speed, we can use linked lists to structure our data instead. Linked lists contain 'nodes' which hold data and pointers to the next node in the list. There are actually many types of linked lists, but for now, let's take a look at the queue list. As a data structure, a queue replicates the behaviour of a queue in real life - like the lineup at a drive through or at an amusement park. Nodes move from the back of the queue to the front, and at the front, they are deleted from a queue.

So how does this look in C++? Let's take a look:

//
//  main.cpp
//  Queue
//
//  Created by Natesh Mayuranathan on 11-10-12.
//

#include <iostream>

using namespace std;

class Queue; 

class QNode {
  int _data;
  QNode* _next;
  
  QNode(int data, QNode* next = (QNode*)0){
  
    _data = data;
    _next = next;
    
  }
  
  friend class Queue;
  
};


class Queue{ 
  
  QNode* _front; 
  QNode* _back;
  QNode* _current;
  
  public:
  
  Queue(){
    _front = (QNode*)0;
    _back = _front;
  }
  
  void add(int data){
    
    //create a new node item and a pointer to it
    QNode* temp = new QNode(data); 
    
    //if the list is empty, add temp to the front of the list
    if(isEmpty()) {
      _front = temp;
    }
    
    //if the list is not empty, point back's next to temp
    if (_back) {
      _back->_next=temp;
    }
    
    //assign temp to back
    _back = temp;
}//add a node to the list 
  
int remove() {
  int val = _front->_data;
  delete _front;
  _front = _front->_next;
  return val;
}//remove node from the list
  
bool isEmpty(){
  return !_front;
}
  
~Queue(){
  while (!isEmpty()) {
    remove();
  }
  
}
  
};

int main (int argc, const char * argv[])
{

  Queue q;
  
  for (int i=100; i<1000; i+=100) {
    q.add(i);
  }
  
  while (!q.isEmpty()) {
    cout << q.remove()<<endl;
  }
  
  return 0;
}