Sorted Queue

Posted: March 5, 2012 in OOP344

QUEUE.H

#ifndef __TV_QUEUE_H__
#define __TV_QUEUE_H__

class Queue;

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

class Queue{
  Node* _head;
public:
  Queue();
  virtual ~Queue();
  int remove();
  void add(int val);
  bool isEmpty();
};

#endif

QUEUE.CPP

#include "queue.h"

Node::Node(int data, Node* next){
  _data = data;
  _next = next;
}
Queue::Queue(){
  _head = (Node*)0;
}
Queue::~Queue(){
  while(!isEmpty()) remove();
}
int Queue::remove(){
  int ret = _head->_data;
  Node* toDel = _head;
  _head = _head->_next;
  delete toDel;
  return ret;
}
void Queue::add(int val){
  Node* cur = _head;
  Node* prev = cur;
  bool done = false;
  while(!done){
    if(!_head || _head->_data >= val){
      _head = new Node(val, _head);
      done = true;
    }
    else if(cur->_data >= val){
      prev->_next = new Node(val, cur);
      done = true;
    }
    else if(!cur->_next){
      cur->_next = new Node(val);
      done = true;
    }
    else {
      prev = cur;
      cur = cur->_next;
    }
  }
}
bool Queue::isEmpty(){
  return !_head;
}

QUEUEMAIN.CPP

#include <iostream>
using namespace std;
#include "queue.h"
#include <ctime>

int main(){
  Queue Q;
  for(int i = 1; i<25 ;i++){
    Q.add(rand()%10000+1);
  }
  while(!Q.isEmpty()){
    cout<<Q.remove()<<endl;
  }
  return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s