Queue/Definition

Queue/Definition
You are encouraged to solve this task according to the task description, using any language you may know.

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;

The following implementation produces equivalent functionality by deriving from the standard Ada Container type Doubly_Linked_Lists.

with Ada.Containers.Doubly_Linked_Lists;
generic
   type Element_Type is private;
package Generic_Fifo is
   type Fifo_Type is tagged private;
   procedure Push(The_Fifo : in out Fifo_Type; Item : in Element_Type);
   procedure Pop(The_Fifo : in out Fifo_Type; Item : out Element_Type);
   Empty_Error : Exception;
private
   package List_Pkg is new Ada.Containers.Doubly_Linked_Lists(Element_Type);
   use List_Pkg;
   Type Fifo_Type is new List with null record;
end Generic_Fifo;

package body Generic_Fifo is

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

   procedure Push (The_Fifo : in out Fifo_Type; Item : in Element_Type) is
   begin
      The_Fifo.Prepend(Item);
   end Push;

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

   procedure Pop (The_Fifo : in out Fifo_Type; Item : out Element_Type) is
   begin
      if Is_Empty(The_Fifo) then
         raise Empty_Error;
      end if;
      Item := The_Fifo.Last_Element;
      The_Fifo.Delete_Last;
   end Pop;

end Generic_Fifo;

with Generic_Fifo;
with Ada.Text_Io; use Ada.Text_Io;

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

The function Is_Empty is inherited from the Lists type.

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

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