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 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 (?), 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.