Queue/Definition

Implement a FIFO queue. Elements are added at one side and popped from the other in the order of insertion.

Operations:

push - add element
pop - pop first element
empty - return truth value when empty

Errors:

handle the error of trying to pop from an empty queue (behavior depends on the language and platform)

Define the data structure for a FIFO element. Said element should contain a data member capable of holding a numeric value, and the link to the next element should be mutable.

Ada

The interface specification for a FIFO is described in the package specification.

generic
   type Element_Type is private;
package Fifo is
   type Fifo_Type is private;
   procedure Push(List : in out Fifo_Type; Item : in Element_Type);
   procedure Pop(List : in out Fifo_Type; Item : out Element_Type);
   function Is_Empty(List : Fifo_Type) return Boolean;
   Empty_Error : exception;
private
   type Fifo_Element;
   type Fifo_Ptr is access Fifo_Element;
   type Fifo_Type is record
      Head : Fifo_Ptr := null;
      Tail : Fifo_Ptr := null;
   end record;
   type Fifo_Element is record
      Value : Element_Type;
      Next  : Fifo_Ptr := null;
   end record;
end Fifo;

The FIFO implementation is described in the package body:

with Ada.Unchecked_Deallocation;

package body Fifo is 

   ----------
   -- Push --
   ----------

   procedure Push (List : in out Fifo_Type; Item : in Element_Type) is
      Temp : Fifo_Ptr := new Fifo_Element'(Item, null);
   begin
      if List.Tail = null then
         List.Tail := Temp;
      end if;
      if List.Head /= null then
        List.Head.Next := Temp;
      end if;
      List.Head := Temp;
   end Push;

   ---------
   -- Pop --
   ---------

   procedure Pop (List : in out Fifo_Type; Item : out Element_Type) is
      procedure Free is new Ada.Unchecked_Deallocation(Fifo_Element, Fifo_Ptr);
      Temp : Fifo_Ptr := List.Tail;
   begin
      if List.Head = null then
         raise Empty_Error;
      end if;
      Item := List.Tail.Value;
      List.Tail := List.Tail.Next;
      if List.Tail = null then
         List.Head := null;
      end if;
      Free(Temp);
   end Pop;

   --------------
   -- Is_Empty --
   --------------

   function Is_Empty (List : Fifo_Type) return Boolean is
   begin
      return List.Head = null;
   end Is_Empty; 

end Fifo;

A "main" procedure for this program is:

with Fifo;
with Ada.Text_Io; use Ada.Text_Io;

procedure Fifo_Test is
   package Int_Fifo is new Fifo(Integer);
   use Int_Fifo;
   My_Fifo : Fifo_Type;
   Val : Integer;
begin
   for I in 1..10 loop
      Push(My_Fifo, I);
   end loop;
   while not Is_Empty(My_Fifo) loop
      Pop(My_Fifo, Val);
      Put_Line(Integer'Image(Val));
   end loop;
end Fifo_Test;

Java

This task could be done using a LinkedList from java.util, but here is a user-defined version:

public class Queue{
	Node head, tail;

	class Node{
		double value;
		Node next;

		public Node(){
			this(0, null);
		}

		public Node(double value, Node next){
			this.value= value;
			this.next= next;
		}

		public Node getNext(){
			return next;
		}

		public void setNext(Node next){
			this.next= next;
		}

	}

	public Queue(){
		head= tail= null;
	}

	public void push(double value){
		Node newNode= new Node(value, null);
		if(empty()){
			head= newNode;
		}else{
			tail.setNext(newNode);
		}
		tail= newNode;
	}

	public double pop() throws IllegalAccessException{
		if(empty()){
			throw new IllegalAccessException("No more elements.");
			//this is the closest-related, built-in Exception I could
			//find...making your own UnderflowException is recommended
		}
		double retVal= head.value;
		head= head.getNext();
		return retVal;
	} 

	public boolean empty(){
		return head == null;
	}
}

Python 2.4 and later includes a deque class, supporting thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction. For other options see Python Cookbook.

from collections import deque
fifo = deque()
fifo. appendleft(value) # push
value = fifo.pop()
not fifo # empty
fifo.pop() -> raises IndexError when empty