Queue

Queues are a data structure where the elements that are first to be inserted are also the first to be removed (first-in-first-out, FIFO). They have two fundamental operations, to enqueue() an element and to dequeue(). To enqueue a new node, we add to the end of the linked list (end of the queue). To dequeue, we take the head node out of the list.

Our special considerations during implementation involve if the list is empty.

class Queue { // assuming node is defined properly
	private:
		Node *head;
		Node *tail; // points at the last node
	public:
		Queue() {
			head = NULL;
			tail = NULL;	
		}
		~Queue() { delete head; }
		void enqueue(int d) {
			Node *p = new Node(d);
			if (head == NULL) { // assume tail is equal to null in this case
				head = p;
				tail = p;
				return; // so the code below doesn't complicate things
			}
			tail->setNext(p)
			tail = p;
		}
		int dequeue() {
			if (head == NULL)
				return -1;
			int n = head->getData();
			Node *p = head;
			head = p->getNext();
			p->setNext(NULL);
			delete p;
			return n;
		}
}

Deques

A double-ended queue (or deque) extends the queue structure by supporting insertion and deletion at both the front and back of the list.

In hardware

Hardware components have a type of buffer memory called a First-In First-Out (FIFO) memory, especially for streaming in packets from IO devices. The mechanism behind accessing FIFO registers are simple: the FIFO has a fixed, finite size, when we write it enqueues a packet and when we read it dequeues a packet.

This can be implemented in practice with a circular FIFO, similar to a circular queue. The read and write operations wrap around to the beginning, and we make use of a read and write pointer. See this post.

Language-specific

C++

Queues are provided as part of the STL as std::queue<T>.

Some useful methods:

• front() and back() returns the first and last element in the queue.
• push() inserts an element at the end of the queue.
• pop() dequeues the first element.

See also

• Stack, the last-in-first-out equivalent