Queue/Definition: Difference between revisions
(added C++) |
m (Moved out of Sol by Task cat) |
||
| Line 1: | Line 1: | ||
[[Category:Less Than 10 Examples]]{{Data structure}} |
[[Category:Less Than 10 Examples]]{{task|Data Structures}}{{Data structure}} |
||
{{BoxImage|Fifo.gif|Illustration of FIFO behavior}} |
{{BoxImage|Fifo.gif|Illustration of FIFO behavior}} |
||
Implement a FIFO queue. Elements are added at one side and popped from the other in the order of insertion. |
Implement a FIFO queue. Elements are added at one side and popped from the other in the order of insertion. |
||
Revision as of 00:01, 23 August 2008
You are encouraged to solve this task according to the task description, using any language you may know.
Data Structure
This illustrates a data structure, a means of storing data within a program.
Illustration of FIFO behavior
Implement a FIFO queue. Elements are added at one side and popped from the other in the order of insertion.
Operations:
- push (aka enqueue) - add element
- pop (aka dequeue) - 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 first example below demonstrates a FIFO created for single-threaded computing. This version has the advantage of using a minimum of memory per FIFO element, and being very fast.
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.
This example needs fewer lines of code on the part of the application programmer, but the implementation is less efficient than the previous example. Each element has all the data members needed for a doubly linked list. It also links in all the functionality of a doubly linked list. Most of that functionality is unneeded in a FIFO.
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.
The next two examples provide simple FIFO functionality for concurrent tasks. The buffer in each example holds a single value. When running concurrent tasks, one writing to the buffer, and one reading from the buffer, either the writer will be faster than the reader, or the reader will be faster than the writer. If the writer is faster a dynamic FIFO will grow to consume all available memory on the computer. If the reader is faster the FIFO will either contain a single value or it will be empty. In either case, no implementation is more efficient than a single element buffer.
If we wish for the reader to read every value written by the writer we must synchronize the tasks. The writer can only write a new value when the buffer contains a stale value. The reader can only read a value when the value is fresh. This synchronization forces the two tasks to run at the same speed.
generic
type Element_Type is private;
package Synchronous_Fifo is
protected type Fifo is
entry Push(Item : Element_Type);
entry Pop(Item : out Element_Type);
private
Value : Element_Type;
Is_New : Boolean := False;
end Fifo;
end Synchronous_Fifo;
package body Synchronous_Fifo is
----------
-- Fifo --
----------
protected body Fifo is
---------
-- Push --
---------
entry Push (Item : Element_Type) when not Is_New is
begin
Value := Item;
Is_New := True;
end Push;
---------
-- Pop --
---------
entry Pop (Item : out Element_Type) when Is_New is
begin
Item := Value;
Is_New := False;
end Pop;
end Fifo;
end Synchronous_Fifo;
with Synchronous_Fifo; with Ada.Text_Io; use Ada.Text_Io;
procedure Synchronous_Fifo_Test is
package Int_Fifo is new Synchronous_Fifo(Integer);
use Int_Fifo;
Buffer : Fifo;
task Writer is
entry Stop;
end Writer;
task body Writer is
Val : Positive := 1;
begin
loop
select
accept Stop;
exit;
else
select
Buffer.Push(Val);
Val := Val + 1;
or
delay 1.0;
end select;
end select;
end loop;
end Writer;
task Reader is
entry Stop;
end Reader;
task body Reader is
Val : Positive;
begin
loop
select
accept Stop;
exit;
else
select
Buffer.Pop(Val);
Put_Line(Integer'Image(Val));
or
delay 1.0;
end select;
end select;
end loop;
end Reader;
begin
delay 0.1;
Writer.Stop;
Reader.Stop;
end Synchronous_Fifo_Test;
Another choice is to cause the two tasks to run independently. The writer can write whenever it is scheduled. The reader reads whenever it is scheduled, after the writer writes the first valid value.
In this example the writer writes several values before the reader reads a value. The reader will then read that same value several times before the writer is scheduled to write more values.
In a fully asynchronous system the reader only samples the values written by the writer. There is no control over the number of values not sampled by the reader, or over the number of times the reader reads the same value.
generic
type Element_Type is private;
package Asynchronous_Fifo is
protected type Fifo is
procedure Push(Item : Element_Type);
entry Pop(Item : out Element_Type);
private
Value : Element_Type;
Valid : Boolean := False;
end Fifo;
end Asynchronous_Fifo;
You may notice that the protected type specification is remarkably similar to the synchronous example above. The only important difference is that Push is declared to be an Entry in the synchronous example while it is a procedure in the asynchronous example. Entries only execute when their boundary condition evaluates to TRUE. Procedures execute unconditionally.
package body Asynchronous_Fifo is
----------
-- Fifo --
----------
protected body Fifo is
----------
-- Push --
----------
procedure Push (Item : Element_Type) is
begin
Value := Item;
Valid := True;
end Push;
---------
-- Pop --
---------
entry Pop (Item : out Element_Type) when Valid is
begin
Item := Value;
end Pop;
end Fifo;
end Asynchronous_Fifo;
with Asynchronous_Fifo;
with Ada.Text_Io; use Ada.Text_Io;
procedure Asynchronous_Fifo_Test is
package Int_Fifo is new Asynchronous_Fifo(Integer);
use Int_Fifo;
Buffer : Fifo;
task Writer is
entry Stop;
end Writer;
task body Writer is
Val : Positive := 1;
begin
loop
select
accept Stop;
exit;
else
Buffer.Push(Val);
Val := Val + 1;
end select;
end loop;
end Writer;
task Reader is
entry Stop;
end Reader;
task body Reader is
Val : Positive;
begin
loop
select
accept Stop;
exit;
else
Buffer.Pop(Val);
Put_Line(Integer'Image(Val));
end select;
end loop;
end Reader;
begin
delay 0.1;
Writer.Stop;
Reader.Stop;
end Asynchronous_Fifo_Test;
C++
C++ already has a class queue in the standard library, however the following is a simple implementation based on a singly linkes list. Note that an empty queue is internally represented by head == 0, therefore it doesn't matter that the tail value is invalid in that case.
<cpp>
namespace rosettacode
{
template<typename T> class queue
{
public:
queue();
~queue();
void push(T const& t);
T pop();
bool empty();
private:
void drop();
struct node;
node* head;
node* tail;
};
template<typename T> struct queue<T>::node
{
T data;
node* next;
node(T const& t): data(t), next(0) {}
};
template<typename T>
queue<T>::queue():
head(0)
{
}
template<typename T>
inline void queue<T>::drop()
{
node* n = head;
head = head->next;
delete n;
}
template<typename T>
queue<T>::~queue()
{
while (!empty())
drop();
}
template<typename T>
void queue<T>::push(T const& t)
{
node*& next = head? tail->next : head;
next = new node(t);
tail = next;
}
template<typename T>
T queue<T>::pop()
{
T tmp = head->data;
drop();
return tmp;
}
template<typename T>
bool queue<T>::empty()
{
return head == 0;
}
} </cpp>
D
Implemented a queue class, by reusing previous stack class definition. See Stack#D.
module stack ;
class Stack(T){
...
void push(T top) { ... }
T pop() { ... }
bool empty() { ... }
}
module fifo ;
import stack ;
class FIFO(T) : Stack!(T){
override T pop() {
if (empty)
throw new Exception("FIFO Empty") ;
T top = content[0] ;
content = content[1..$] ;
return top ;
}
alias push enqueue ;
alias pop dequeue ;
}
Statement content = content[1..$] is efficient enough, because no array content is moved/copyed, but pointer modified.
The following is a linked implementation:
module fifolink ;
class FIFOLinked(T) {
class Node {
T content ;
Node next ;
this(T data, Node prevNode) {
content = data ;
if (prevNode)
prevNode.next = this ;
next = null ;
}
}
private Node head = null ;
private Node tail = null ;
void push(T last) {
tail = new Node(last, tail) ;
if(empty)
head = tail ;
}
T pop() {
if(empty)
throw new Exception("FIFO Empty") ;
T first = head.content ;
if (head is tail) // is last one?
tail = null ; // release tail reference so that GC can collect afterward
head = head.next ;
return first ;
}
bool empty() { return head is null ; }
alias push enqueue ;
alias pop dequeue ;
}
Java
This task could be done using a LinkedList from java.util, but here is a user-defined version with generics: <java>public class Queue<E>{ Node<E> head, tail;
static class Node<E>{ E value; Node<E> next;
public Node(){ this(0, null); }
public Node(E value, Node<E> next){ this.value= value; this.next= next; }
public Node<E> getNext(){ return next; }
public void setNext(Node<E> next){ this.next= next; }
}
public Queue(){ head= tail= null; }
public void enqueue(E value){ //standard queue name for "push" Node<E> newNode= new Node<E>(value, null); if(empty()){ head= newNode; }else{ tail.setNext(newNode); } tail= newNode; }
public E dequeue() throws java.util.NoSuchElementException{//standard queue name for "pop" if(empty()){ throw new java.util.NoSuchElementException("No more elements."); } E retVal= head.value; head= head.getNext(); return retVal; }
public boolean empty(){ return head == null; } }</java>
Pascal
This program should be Standard Pascal compliant (i.e. it doesn't make use of the advanced/non-standard features of FreePascal or GNU Pascal).
program fifo(input, output);
type
pNode = ^tNode;
tNode = record
value: integer;
next: pNode;
end;
tFifo = record
first, last: pNode;
end;
procedure initFifo(var fifo: tFifo);
begin
fifo.first := nil;
fifo.last := nil
end;
procedure pushFifo(var fifo: tFifo; value: integer);
var
node: pNode;
begin
new(node);
node^.value := value;
node^.next := nil;
if fifo.first = nil
then
fifo.first := node
else
fifo.last^.next := node;
fifo.last := node
end;
function popFifo(var fifo: tFifo; var value: integer): boolean;
var
node: pNode;
begin
if fifo.first = nil
then
popFifo := false
else
begin
node := fifo.first;
fifo.first := fifo.first^.next;
value := node^.value;
dispose(node);
popFifo := true
end
end;
procedure testFifo;
var
fifo: tFifo;
procedure testpop(expectEmpty: boolean; expectedValue: integer);
var
i: integer;
begin
if popFifo(fifo, i)
then
if expectEmpty
then
writeln('Error! Expected empty, got ', i, '.')
else
if i = expectedValue
then
writeln('Ok, got ', i, '.')
else
writeln('Error! Expected ', expectedValue, ', got ', i, '.')
else
if expectEmpty
then
writeln('Ok, fifo is empty.')
else
writeln('Error! Expected ', expectedValue, ', found fifo empty.')
end;
begin
initFifo(fifo);
pushFifo(fifo, 2);
pushFifo(fifo, 3);
pushFifo(fifo, 5);
testpop(false, 2);
pushFifo(fifo, 7);
testpop(false, 3);
testpop(false, 5);
pushFifo(fifo, 11);
testpop(false, 7);
testpop(false, 11);
pushFifo(fifo, 13);
testpop(false, 13);
testpop(true, 0);
pushFifo(fifo, 17);
testpop(false, 17);
testpop(true, 0)
end;
begin
writeln('Testing fifo implementation ...');
testFifo;
writeln('Testing finished.')
end.
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