queue

A type of data structure that acts, well, like a queue. You insert data at the rear of the structure, and retrieve it from the front. FIFO. Compare to stack.

Rather generic C++ code for a queue data structure. Data are ints to make it simple. I give no guarantees of it working, but it works fine for me :P

/*
  queue.h
  header file for queue.cpp, implements a queue data structure using a linked list.
*/


#ifndef QUEUE_H
#define QUEUE_H

#include 

class queue;

class node
{
  friend queue;
 private:
  int data;
  node *link;
  //node *backward;
};

class queue
{
 public:
  queue();
  ~queue();
  bool isEmpty();
  int size();
  void push(int p);
  int peek();
  int pop();
 private:
  node *front;
  node *rear;
  bool empty;
  int howBig;
};

#endif //QUEUE_H

/*
  queue.cpp
  source code for a queue data structure, implemented using a linked list
*/


#include 
#include "queue.h"

queue::queue()
{
  front = rear = 0;
  //empty = true;
  howBig = 0;
}

queue::~queue()
{
  node *next;
  while(front != 0)
    {
      next = front->link;
      delete front;
      front = next;
    }
}




int queue::size()
{
  return howBig;
}

bool queue::isEmpty()
{
  if(front)
    empty = false;
  else
    empty = true;
  return(empty);
}

int queue::peek()
{
  if(isEmpty())
    {
      cerr << "queue is empty\n";
      exit(1);
    }
  return front->data;
}

void queue::push(int p)
{
  node *temp = new node;
  
  temp->data = p;
  temp->link = 0;
  howBig++;
  empty = false;
  if(front)
    {
      rear->link = temp;
    }
  else
    {
      front = temp;
    }
  rear = temp;
  return;

}

int queue::pop()
{
  if(isEmpty()) exit(1);
  int x = front->data;
  node *temp = front;
  front = front->link;
  delete temp;
  howBig--;
  return x;
}

Once more, I bring you the Java implementation of this Data Structure. Note: this Queue takes objects, not primitive types. This actually makes things much easier, even though I wouldn't admit it when I first started working with Queues (or other structures for that matter). Note that this Queue is based on a Doubly Linked List, which I have also noded. Enjoy!

//************************************************************
// This class defines a Queue.
// It is based on a Linked List.
//************************************************************

public class MyQueue extends ListClass
{

//************************************************************
// Declares an integer to hold the number of elements on the
// Queue.
//************************************************************

	private int numOnQueue = 0;	

//************************************************************
// This is the default constructor for the MyQueue class.
// It assigns all omnipresent nodes to null.
//************************************************************

	public MyQueue()
	{
	start = current = end = null;
	}

//************************************************************
// This method, dequeue() removes the first elements from the
// queue, and returns it to the calling object. It also
// decrements numOnQueue.
//************************************************************

	public Object dequeue()
	{
		Object o = null;
		current = start;

		if(this.isEmpty() == false)
		{
			if(start.getNext() == null)
			{
				o = start.getObject();
				current = start = end = null;
				numOnQueue--;
				return(o);
			}
			else
			{
				o = start.getObject();
				start = current = start.getNext();
				numOnQueue--;
				return(o);
			}
		}
		return("If you see this, there is an error.");
	}

//************************************************************
// This method, enqueue() takes an object and adds it to the
// end of the queue. It also increments numOnQueue.
//************************************************************

	public void enqueue(Object o)
	{
		addAfter(o);
		numOnQueue++;
	}

//************************************************************
// This method, getNumOnQueue() returns the current int value
// of numOnQueue.
//************************************************************

	public int getNumOnQueue()
	{
	return numOnQueue;
	}

//************************************************************
// This method, isEmpty() determines if the queue is empty,
// using the value of numOnQueue as an indicator.
//************************************************************

	public boolean isEmpty()
	{
		if(numOnQueue == 0)
			return true;
		else
			return false;
	}
}

queue

In reference to good old Webster 1913's definition first as a noun: 1. A tail-like appendage of hair; a pigtail.

and as a transitive verb: To fasten, as hair, in a queue.

And also in reference to Mind your Ps and Qs, a delightful write-up by Buttermaker, who unfortunately has not been seen in these parts since 2006. The write-up is an exploration of the possible origins of that phrase. One suggestion posits that at one time sailors would pull their hair into a queue and dip it in tar, but Buttermaker could not imagine a reason for this behavior. In fact, this was a common practice, especially among marines and sailors aboard ships that were likely to be involved in combat. First, the tarred queue (and that is the origin of the slang term "tar" for sailors) kept hair maintenance to a minimum and kept it from becoming a dangerous encumbrance when climbing rigging and dealing with loose sheets and halyards. Second, and probably more important, the tar in the queue made it into a very stiff, resilient protection for the back of the neck in hand-to-hand combat, which was very close and deadly in sea battles among the sailing vessels and galleys of the period.

Queue (?), n. [F. See Cue.] (a)

A tail-like appendage of hair; a pigtail.

(b)

A line of persons waiting anywhere.

 

© Webster 1913.

---

Queue, v. t.

To fasten, as hair, in a queue.

 

© Webster 1913.