Queue/Definition: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 29: | Line 29: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">T FIFO |
||
[Int] contents |
[Int] contents |
||
Line 44: | Line 44: | ||
f.push(1) |
f.push(1) |
||
L !f.empty() |
L !f.empty() |
||
print(f.pop())</ |
print(f.pop())</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 55: | Line 55: | ||
=={{header|AArch64 Assembly}}== |
=={{header|AArch64 Assembly}}== |
||
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
{{works with|as|Raspberry Pi 3B version Buster 64 bits}} |
||
<syntaxhighlight lang="aarch64 assembly"> |
|||
<lang AArch64 Assembly> |
|||
/* ARM assembly AARCH64 Raspberry PI 3B */ |
/* ARM assembly AARCH64 Raspberry PI 3B */ |
||
/* program defqueue64.s */ |
/* program defqueue64.s */ |
||
Line 292: | Line 292: | ||
.include "../includeARM64.inc" |
.include "../includeARM64.inc" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
<pre> |
<pre> |
||
Line 303: | Line 303: | ||
=={{header|ACL2}}== |
=={{header|ACL2}}== |
||
< |
<syntaxhighlight lang="lisp">(defun enqueue (x xs) |
||
(cons x xs)) |
(cons x xs)) |
||
Line 316: | Line 316: | ||
(defun empty (xs) |
(defun empty (xs) |
||
(endp xs))</ |
(endp xs))</syntaxhighlight> |
||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
===Static memory=== |
===Static memory=== |
||
Following solution uses fixed array as a buffer for the queue. |
Following solution uses fixed array as a buffer for the queue. |
||
< |
<syntaxhighlight lang="action!">DEFINE MAXSIZE="200" |
||
BYTE ARRAY queue(MAXSIZE) |
BYTE ARRAY queue(MAXSIZE) |
||
BYTE queueFront=[0],queueRear=[0] |
BYTE queueFront=[0],queueRear=[0] |
||
Line 392: | Line 392: | ||
TestPop() |
TestPop() |
||
TestPop() |
TestPop() |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
===Dynamic memory=== |
===Dynamic memory=== |
||
Following solution uses module for dynamic memory allocation. The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
Following solution uses module for dynamic memory allocation. The user must type in the monitor the following command after compilation and before running the program!<pre>SET EndProg=*</pre> |
||
{{libheader|Action! Tool Kit}} |
{{libheader|Action! Tool Kit}} |
||
< |
<syntaxhighlight lang="action!">CARD EndProg ;required for ALLOCATE.ACT |
||
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program! |
INCLUDE "D2:ALLOCATE.ACT" ;from the Action! Tool Kit. You must type 'SET EndProg=*' from the monitor after compiling, but before running this program! |
||
Line 479: | Line 479: | ||
TestPop() |
TestPop() |
||
TestPop() |
TestPop() |
||
RETURN</ |
RETURN</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Error at the end of the program is intentional. |
Error at the end of the program is intentional. |
||
Line 503: | Line 503: | ||
The interface specification for a FIFO is described in the package specification. |
The interface specification for a FIFO is described in the package specification. |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
package Fifo is |
package Fifo is |
||
Line 522: | Line 522: | ||
Next : Fifo_Ptr := null; |
Next : Fifo_Ptr := null; |
||
end record; |
end record; |
||
end Fifo;</ |
end Fifo;</syntaxhighlight> |
||
The FIFO implementation is described in the package body: |
The FIFO implementation is described in the package body: |
||
< |
<syntaxhighlight lang="ada">with Ada.Unchecked_Deallocation; |
||
package body Fifo is |
package body Fifo is |
||
Line 572: | Line 572: | ||
end Is_Empty; |
end Is_Empty; |
||
end Fifo;</ |
end Fifo;</syntaxhighlight> |
||
A "main" procedure for this program is: |
A "main" procedure for this program is: |
||
< |
<syntaxhighlight lang="ada">with Fifo; |
||
with Ada.Text_Io; use Ada.Text_Io; |
with Ada.Text_Io; use Ada.Text_Io; |
||
Line 590: | Line 590: | ||
Put_Line(Integer'Image(Val)); |
Put_Line(Integer'Image(Val)); |
||
end loop; |
end loop; |
||
end Fifo_Test;</ |
end Fifo_Test;</syntaxhighlight> |
||
The following implementation produces equivalent functionality by deriving from the standard Ada Container type Doubly_Linked_Lists. |
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. |
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. |
||
< |
<syntaxhighlight lang="ada"> |
||
with Ada.Containers.Doubly_Linked_Lists; |
with Ada.Containers.Doubly_Linked_Lists; |
||
generic |
generic |
||
Line 608: | Line 608: | ||
Type Fifo_Type is new List with null record; |
Type Fifo_Type is new List with null record; |
||
end Generic_Fifo; |
end Generic_Fifo; |
||
</syntaxhighlight> |
|||
</lang> |
|||
< |
<syntaxhighlight lang="ada"> |
||
package body Generic_Fifo is |
package body Generic_Fifo is |
||
Line 634: | Line 634: | ||
end Pop; |
end Pop; |
||
end Generic_Fifo;</ |
end Generic_Fifo;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ada">with Generic_Fifo; |
||
with Ada.Text_Io; use Ada.Text_Io; |
with Ada.Text_Io; use Ada.Text_Io; |
||
Line 651: | Line 651: | ||
Put_Line(Integer'Image(Val)); |
Put_Line(Integer'Image(Val)); |
||
end loop; |
end loop; |
||
end Generic_Fifo_Test;</ |
end Generic_Fifo_Test;</syntaxhighlight> |
||
The function Is_Empty is inherited from the Lists type. |
The function Is_Empty is inherited from the Lists type. |
||
Line 657: | Line 657: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
package Synchronous_Fifo is |
package Synchronous_Fifo is |
||
Line 667: | Line 667: | ||
Is_New : Boolean := False; |
Is_New : Boolean := False; |
||
end Fifo; |
end Fifo; |
||
end Synchronous_Fifo;</ |
end Synchronous_Fifo;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ada">package body Synchronous_Fifo is |
||
---------- |
---------- |
||
Line 698: | Line 698: | ||
end Fifo; |
end Fifo; |
||
end Synchronous_Fifo;</ |
end Synchronous_Fifo;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ada">with Synchronous_Fifo; |
||
with Ada.Text_Io; use Ada.Text_Io; |
with Ada.Text_Io; use Ada.Text_Io; |
||
Line 754: | Line 754: | ||
Writer.Stop; |
Writer.Stop; |
||
Reader.Stop; |
Reader.Stop; |
||
end Synchronous_Fifo_Test;</ |
end Synchronous_Fifo_Test;</syntaxhighlight> |
||
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. |
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. |
||
Line 760: | Line 760: | ||
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. |
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. |
||
< |
<syntaxhighlight lang="ada">generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
package Asynchronous_Fifo is |
package Asynchronous_Fifo is |
||
Line 770: | Line 770: | ||
Valid : Boolean := False; |
Valid : Boolean := False; |
||
end Fifo; |
end Fifo; |
||
end Asynchronous_Fifo;</ |
end Asynchronous_Fifo;</syntaxhighlight> |
||
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. |
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. |
||
< |
<syntaxhighlight lang="ada">package body Asynchronous_Fifo is |
||
---------- |
---------- |
||
Line 801: | Line 801: | ||
end Fifo; |
end Fifo; |
||
end Asynchronous_Fifo;</ |
end Asynchronous_Fifo;</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ada">with Asynchronous_Fifo; |
||
with Ada.Text_Io; use Ada.Text_Io; |
with Ada.Text_Io; use Ada.Text_Io; |
||
Line 843: | Line 843: | ||
Put_Line(Integer'Image(Val)); |
Put_Line(Integer'Image(Val)); |
||
end select; |
end select; |
||
end loop;< |
end loop;<syntaxhighlight lang="ada"> |
||
end Reader; |
end Reader; |
||
begin |
begin |
||
Line 849: | Line 849: | ||
Writer.Stop; |
Writer.Stop; |
||
Reader.Stop; |
Reader.Stop; |
||
end Asynchronous_Fifo_Test;</ |
end Asynchronous_Fifo_Test;</syntaxhighlight> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
Line 855: | Line 855: | ||
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.7 algol68g-2.7].}} |
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-2.7 algol68g-2.7].}} |
||
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}} |
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}} |
||
'''File: prelude/queue_base.a68'''< |
'''File: prelude/queue_base.a68'''<syntaxhighlight lang="algol68"># -*- coding: utf-8 -*- # |
||
CO REQUIRES: |
CO REQUIRES: |
||
MODE OBJLINK = STRUCT( |
MODE OBJLINK = STRUCT( |
||
Line 927: | Line 927: | ||
self IS obj queue empty; |
self IS obj queue empty; |
||
SKIP</ |
SKIP</syntaxhighlight>'''See also:''' [[Queue/Usage#ALGOL_68|Queue/Usage]] |
||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
< |
<syntaxhighlight lang="algolw">begin |
||
% define a Queue type that will hold StringQueueElements % |
% define a Queue type that will hold StringQueueElements % |
||
record StringQueue ( reference(StringQueueElement) front, back ); |
record StringQueue ( reference(StringQueueElement) front, back ); |
||
Line 980: | Line 980: | ||
while not isEmptyStringQueue( q ) do write( popString( q ) ) |
while not isEmptyStringQueue( q ) do write( popString( q ) ) |
||
end |
end |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 990: | Line 990: | ||
=={{header|Applesoft BASIC}}== |
=={{header|Applesoft BASIC}}== |
||
< |
<syntaxhighlight lang="applesoftbasic"> 0 DEF FN E(MPTY) = SP = FIRST |
||
10 GOSUB 150EMPTY |
10 GOSUB 150EMPTY |
||
20 LET A$ = "A": GOSUB 100PUSH |
20 LET A$ = "A": GOSUB 100PUSH |
||
Line 1,005: | Line 1,005: | ||
130 IF FN E(0) THEN PRINT "POPPING FROM EMPTY QUEUE";: STOP |
130 IF FN E(0) THEN PRINT "POPPING FROM EMPTY QUEUE";: STOP |
||
140 A$ = S$(FI): FI = FI + 1 : RETURN |
140 A$ = S$(FI): FI = FI + 1 : RETURN |
||
150 PRINT "EMPTY? " MID$ ("YESNO",4 ^ FN E(0),3): RETURN</ |
150 PRINT "EMPTY? " MID$ ("YESNO",4 ^ FN E(0),3): RETURN</syntaxhighlight> |
||
=={{header|ARM Assembly}}== |
=={{header|ARM Assembly}}== |
||
{{works with|as|Raspberry Pi}} |
{{works with|as|Raspberry Pi}} |
||
<syntaxhighlight lang="arm assembly"> |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI */ |
/* ARM assembly Raspberry PI */ |
||
/* program defqueue.s */ |
/* program defqueue.s */ |
||
Line 1,294: | Line 1,294: | ||
bx lr @ return |
bx lr @ return |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{output}} |
{{output}} |
||
Empty queue. |
Empty queue. |
||
Line 1,313: | Line 1,313: | ||
=== A linear linked list as a queue === |
=== A linear linked list as a queue === |
||
< |
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*) |
||
#define ATS_DYNLOADFLAG 0 |
#define ATS_DYNLOADFLAG 0 |
||
Line 1,493: | Line 1,493: | ||
} |
} |
||
(*------------------------------------------------------------------*)</ |
(*------------------------------------------------------------------*)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,514: | Line 1,514: | ||
=== A nonlinear circular queue with an automatically resizing buffer === |
=== A nonlinear circular queue with an automatically resizing buffer === |
||
< |
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*) |
||
(* |
(* |
||
Line 1,721: | Line 1,721: | ||
} |
} |
||
(*------------------------------------------------------------------*)</ |
(*------------------------------------------------------------------*)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,751: | Line 1,751: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
< |
<syntaxhighlight lang="autohotkey">push("qu", 2), push("qu", 44), push("qu", "xyz") ; TEST |
||
MsgBox % "Len = " len("qu") ; Number of entries |
MsgBox % "Len = " len("qu") ; Number of entries |
||
Line 1,781: | Line 1,781: | ||
StringReplace %queue%, %queue%, |, |, UseErrorLevel |
StringReplace %queue%, %queue%, |, |, UseErrorLevel |
||
Return %queue% = "" ? 0 : ErrorLevel+1 |
Return %queue% = "" ? 0 : ErrorLevel+1 |
||
}</ |
}</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
< |
<syntaxhighlight lang="awk">#!/usr/bin/awk -f |
||
BEGIN { |
BEGIN { |
||
Line 1,816: | Line 1,816: | ||
return length(q) == 0 |
return length(q) == 0 |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 1,836: | Line 1,836: | ||
More complex variations can be written that remove this limitation. |
More complex variations can be written that remove this limitation. |
||
< |
<syntaxhighlight lang="dos"> |
||
@echo off |
@echo off |
||
setlocal enableDelayedExpansion |
setlocal enableDelayedExpansion |
||
Line 1,906: | Line 1,906: | ||
for %%N in (!%~1.head!) do set %~2=!%~1.%%N! |
for %%N in (!%~1.head!) do set %~2=!%~1.%%N! |
||
exit /b 0 |
exit /b 0 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
{{works with|BBC BASIC for Windows}} |
{{works with|BBC BASIC for Windows}} |
||
< |
<syntaxhighlight lang="bbcbasic"> FIFOSIZE = 1000 |
||
FOR n = 3 TO 5 |
FOR n = 3 TO 5 |
||
Line 1,940: | Line 1,940: | ||
= (rptr% = wptr%) |
= (rptr% = wptr%) |
||
ENDCASE |
ENDCASE |
||
ENDPROC</ |
ENDPROC</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,959: | Line 1,959: | ||
Queues are already straightforward to make in BQN via its convenient builtins. This object is made for demonstration of BQN's object oriented features. It would generally be much simpler to apply the related functions to an array instead of creating a big object. |
Queues are already straightforward to make in BQN via its convenient builtins. This object is made for demonstration of BQN's object oriented features. It would generally be much simpler to apply the related functions to an array instead of creating a big object. |
||
< |
<syntaxhighlight lang="bqn">queue ← { |
||
data ← ⟨⟩ |
data ← ⟨⟩ |
||
Push ⇐ {data∾˜↩𝕩} |
Push ⇐ {data∾˜↩𝕩} |
||
Line 1,978: | Line 1,978: | ||
q1.Display@ |
q1.Display@ |
||
•Show q1.Pop@ |
•Show q1.Pop@ |
||
q1.Display@</ |
q1.Display@</syntaxhighlight><syntaxhighlight lang="text">1 |
||
⟨ 4 3 ⟩ |
⟨ 4 3 ⟩ |
||
3 |
3 |
||
⟨ 4 ⟩</ |
⟨ 4 ⟩</syntaxhighlight> |
||
It's also possible to build a queue out of linked node objects, an approach discussed in [https://mlochbaum.github.io/BQN/doc/oop.html#mutability this section] of the BQN documentation. While much slower to traverse, this approach opens up new possibilities, such as constant time deletion and insertion at an arbitrary node, that aren't available with plain arrays. |
It's also possible to build a queue out of linked node objects, an approach discussed in [https://mlochbaum.github.io/BQN/doc/oop.html#mutability this section] of the BQN documentation. While much slower to traverse, this approach opens up new possibilities, such as constant time deletion and insertion at an arbitrary node, that aren't available with plain arrays. |
||
Line 1,989: | Line 1,989: | ||
No special provision is implemented to "throw and exception" in case you try to dequeue from and empty queue, because, in Bracmat, evaluation of an expression, besides resulting in an evaluated expression, always also either "succeeds" or "fails". (There is, in fact, a third possibility, "ignore", telling Bracmat to close an eye even though an evaluation didn't succeed.) So in the example below, the last dequeue operation fails and the program continues on the right hand side of the bar (<code>|</code>) operator |
No special provision is implemented to "throw and exception" in case you try to dequeue from and empty queue, because, in Bracmat, evaluation of an expression, besides resulting in an evaluated expression, always also either "succeeds" or "fails". (There is, in fact, a third possibility, "ignore", telling Bracmat to close an eye even though an evaluation didn't succeed.) So in the example below, the last dequeue operation fails and the program continues on the right hand side of the bar (<code>|</code>) operator |
||
< |
<syntaxhighlight lang="bracmat"> ( queue |
||
= (list=) |
= (list=) |
||
(enqueue=.(.!arg) !(its.list):?(its.list)) |
(enqueue=.(.!arg) !(its.list):?(its.list)) |
||
Line 1,998: | Line 1,998: | ||
) |
) |
||
(empty=.!(its.list):) |
(empty=.!(its.list):) |
||
)</ |
)</syntaxhighlight> |
||
Normally you would seldom use a class as depicted above, because the operations are so simple that you probably use them directly. Bracmat lists allow prepending as well as appending elements, and single elements can be removed from the beginning or from the end of a list. |
Normally you would seldom use a class as depicted above, because the operations are so simple that you probably use them directly. Bracmat lists allow prepending as well as appending elements, and single elements can be removed from the beginning or from the end of a list. |
||
Line 2,007: | Line 2,007: | ||
===Dynamic array=== |
===Dynamic array=== |
||
Dynamic array working as a circular buffer. |
Dynamic array working as a circular buffer. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 2,058: | Line 2,058: | ||
} |
} |
||
return 1; |
return 1; |
||
}</ |
}</syntaxhighlight> |
||
===Doubly linked list=== |
===Doubly linked list=== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 2,104: | Line 2,104: | ||
return 1; |
return 1; |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''Test code''' |
'''Test code''' |
||
This main function works with both implementions above. |
This main function works with both implementions above. |
||
< |
<syntaxhighlight lang="c">int main() |
||
{ |
{ |
||
int i, n; |
int i, n; |
||
Line 2,129: | Line 2,129: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
Of the above two programs, for int types the array method is about twice as fast for the test code given. The doubly linked list is marginally faster than the <code>sys/queue.h</code> below. |
Of the above two programs, for int types the array method is about twice as fast for the test code given. The doubly linked list is marginally faster than the <code>sys/queue.h</code> below. |
||
Line 2,136: | Line 2,136: | ||
Using the <tt>sys/queue.h</tt>, which is not POSIX.1-2001 (but it is BSD). The example allows to push/pop int values, but instead of <tt>int</tt> one can use <tt>void *</tt> and push/pop any kind of "object" (of course changes to the commodity functions <tt>m_queue</tt> and <tt>m_dequeue</tt> are needed) |
Using the <tt>sys/queue.h</tt>, which is not POSIX.1-2001 (but it is BSD). The example allows to push/pop int values, but instead of <tt>int</tt> one can use <tt>void *</tt> and push/pop any kind of "object" (of course changes to the commodity functions <tt>m_queue</tt> and <tt>m_dequeue</tt> are needed) |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stdbool.h> |
#include <stdbool.h> |
||
Line 2,182: | Line 2,182: | ||
if ( l->tqh_first == NULL ) return true; |
if ( l->tqh_first == NULL ) return true; |
||
return false; |
return false; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp}}== |
=={{header|C sharp}}== |
||
Compatible with C# 3.0 specification, requires System library for exceptions (from either .Net or Mono). A FIFO class in C# using generics and nodes. |
Compatible with C# 3.0 specification, requires System library for exceptions (from either .Net or Mono). A FIFO class in C# using generics and nodes. |
||
< |
<syntaxhighlight lang="csharp">public class FIFO<T> |
||
{ |
{ |
||
class Node |
class Node |
||
Line 2,223: | Line 2,223: | ||
return first == null; |
return first == null; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C++}}== |
=={{header|C++}}== |
||
{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}} |
{{works with|g++|4.1.2 20061115 (prerelease) (Debian 4.1.1-21)}} |
||
C++ already has a class <code>queue</code> 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 <code>head == 0</code>, therefore it doesn't matter that the <code>tail</code> value is invalid in that case. |
C++ already has a class <code>queue</code> 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 <code>head == 0</code>, therefore it doesn't matter that the <code>tail</code> value is invalid in that case. |
||
< |
<syntaxhighlight lang="cpp">namespace rosettacode |
||
{ |
{ |
||
template<typename T> class queue |
template<typename T> class queue |
||
Line 2,294: | Line 2,294: | ||
return head == 0; |
return head == 0; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Clojure}}== |
=={{header|Clojure}}== |
||
Clojure has a built-in persistent FIFO queue which can be accessed by referring to clojure.lang.PersistentQueue/EMPTY. Queues are manipulated similarly to Clojure's stacks using peek and pop. |
Clojure has a built-in persistent FIFO queue which can be accessed by referring to clojure.lang.PersistentQueue/EMPTY. Queues are manipulated similarly to Clojure's stacks using peek and pop. |
||
< |
<syntaxhighlight lang="clojure"> |
||
user=> (def empty-queue clojure.lang.PersistentQueue/EMPTY) |
user=> (def empty-queue clojure.lang.PersistentQueue/EMPTY) |
||
Line 2,332: | Line 2,332: | ||
<-(2 3 4 5)-< |
<-(2 3 4 5)-< |
||
</syntaxhighlight> |
|||
</lang> |
|||
Here's a link with further documentation [https://admay.github.io/queues-in-clojure/ Queues in Clojure] |
Here's a link with further documentation [https://admay.github.io/queues-in-clojure/ Queues in Clojure] |
||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
< |
<syntaxhighlight lang="coffeescript"> |
||
# Implement a fifo as an array of arrays, to |
# Implement a fifo as an array of arrays, to |
||
# greatly amortize dequeue costs, at some expense of |
# greatly amortize dequeue costs, at some expense of |
||
Line 2,376: | Line 2,376: | ||
v = q.dequeue() |
v = q.dequeue() |
||
console.log v |
console.log v |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,392: | Line 2,392: | ||
This defines a queue structure that stores its items in a list, and maintains a tail pointer (i.e., a pointer to the last cons in the list). Note that dequeuing the last item in the queue does not clear the tail pointer—enqueuing into the resulting empty queue will correctly reset the tail pointer. |
This defines a queue structure that stores its items in a list, and maintains a tail pointer (i.e., a pointer to the last cons in the list). Note that dequeuing the last item in the queue does not clear the tail pointer—enqueuing into the resulting empty queue will correctly reset the tail pointer. |
||
< |
<syntaxhighlight lang="lisp">(defstruct (queue (:constructor %make-queue)) |
||
(items '() :type list) |
(items '() :type list) |
||
(tail '() :type list)) |
(tail '() :type list)) |
||
Line 2,417: | Line 2,417: | ||
(if (queue-empty-p queue) |
(if (queue-empty-p queue) |
||
(error "Cannot dequeue from empty queue.") |
(error "Cannot dequeue from empty queue.") |
||
(pop (queue-items queue))))</ |
(pop (queue-items queue))))</syntaxhighlight> |
||
=={{header|Component Pascal}}== |
=={{header|Component Pascal}}== |
||
BlackBox Component Builder |
BlackBox Component Builder |
||
< |
<syntaxhighlight lang="oberon2"> |
||
MODULE Queue; |
MODULE Queue; |
||
IMPORT |
IMPORT |
||
Line 2,503: | Line 2,503: | ||
END Queue. |
END Queue. |
||
</syntaxhighlight> |
|||
</lang> |
|||
Interface extracted from implementation |
Interface extracted from implementation |
||
< |
<syntaxhighlight lang="oberon2"> |
||
DEFINITION Queue; |
DEFINITION Queue; |
||
Line 2,524: | Line 2,524: | ||
END Queue. |
END Queue. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
Line 2,531: | Line 2,531: | ||
Cowgol program at [[Queue/Usage]]. The queue is implemented by means of a linked list. |
Cowgol program at [[Queue/Usage]]. The queue is implemented by means of a linked list. |
||
< |
<syntaxhighlight lang="cowgol">include "strings.coh"; |
||
include "malloc.coh"; |
include "malloc.coh"; |
||
Line 2,595: | Line 2,595: | ||
q.tail := Q_NONE; |
q.tail := Q_NONE; |
||
end if; |
end if; |
||
end sub;</ |
end sub;</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
Line 2,602: | Line 2,602: | ||
=={{header|Déjà Vu}}== |
=={{header|Déjà Vu}}== |
||
This uses a dictionary to have a sort of [[wp:Circular_buffer|circular buffer]] of infinite size. |
This uses a dictionary to have a sort of [[wp:Circular_buffer|circular buffer]] of infinite size. |
||
< |
<syntaxhighlight lang="dejavu">queue: |
||
{ :start 0 :end 0 } |
{ :start 0 :end 0 } |
||
Line 2,617: | Line 2,617: | ||
empty q: |
empty q: |
||
= q!start q!end</ |
= q!start q!end</syntaxhighlight> |
||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
{{libheader| System.Generics.Collections}} |
{{libheader| System.Generics.Collections}} |
||
< |
<syntaxhighlight lang="delphi">program QueueDefinition; |
||
{$APPTYPE CONSOLE} |
{$APPTYPE CONSOLE} |
||
Line 2,670: | Line 2,670: | ||
Readln; |
Readln; |
||
end. |
end. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|E}}== |
=={{header|E}}== |
||
Line 2,677: | Line 2,677: | ||
Also, according to E design principles, the read and write ends of the queue are separate objects. This has two advantages; first, it implements [http://wiki.erights.org/wiki/POLA POLA] by allowing only the needed end of the queue to be handed out to its users; second, if the reader end is garbage collected the contents of the queue automatically will be as well (rather than accumulating if the writer continues writing). |
Also, according to E design principles, the read and write ends of the queue are separate objects. This has two advantages; first, it implements [http://wiki.erights.org/wiki/POLA POLA] by allowing only the needed end of the queue to be handed out to its users; second, if the reader end is garbage collected the contents of the queue automatically will be as well (rather than accumulating if the writer continues writing). |
||
< |
<syntaxhighlight lang="e">def makeQueue() { |
||
def [var head, var tail] := Ref.promise() |
def [var head, var tail] := Ref.promise() |
||
Line 2,703: | Line 2,703: | ||
return [reader, writer] |
return [reader, writer] |
||
}</ |
}</syntaxhighlight> |
||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
There is no native queue type in EchoLisp. make-Q implements queues in message passing style, using vector operations. Conversions from-to lists are also provided. |
There is no native queue type in EchoLisp. make-Q implements queues in message passing style, using vector operations. Conversions from-to lists are also provided. |
||
< |
<syntaxhighlight lang="lisp"> |
||
;; put info string in permanent storage for later use |
;; put info string in permanent storage for later use |
||
(info 'make-Q |
(info 'make-Q |
||
Line 2,742: | Line 2,742: | ||
;; save make-Q |
;; save make-Q |
||
(local-put 'make-Q) |
(local-put 'make-Q) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elena}}== |
=={{header|Elena}}== |
||
ELENA 4.x : |
ELENA 4.x : |
||
< |
<syntaxhighlight lang="elena">import extensions; |
||
template queue<T> |
template queue<T> |
||
Line 2,808: | Line 2,808: | ||
console.printLine(e.Message) |
console.printLine(e.Message) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 2,822: | Line 2,822: | ||
This is a generic Queue component based on bi-directional lists. See how in Elisa these [http://jklunder.home.xs4all.nl/elisa/part01/doc080.html lists] are defined. |
This is a generic Queue component based on bi-directional lists. See how in Elisa these [http://jklunder.home.xs4all.nl/elisa/part01/doc080.html lists] are defined. |
||
<syntaxhighlight lang="elisa"> |
|||
<lang Elisa> |
|||
component GenericQueue ( Queue, Element ); |
component GenericQueue ( Queue, Element ); |
||
type Queue; |
type Queue; |
||
Line 2,846: | Line 2,846: | ||
remove(first(queue.list))]; |
remove(first(queue.list))]; |
||
end component GenericQueue; |
end component GenericQueue; |
||
</syntaxhighlight> |
|||
</lang> |
|||
In the following tests we will also show how the internal structure of the queue can be made visible to support debugging. |
In the following tests we will also show how the internal structure of the queue can be made visible to support debugging. |
||
<syntaxhighlight lang="elisa"> |
|||
<lang Elisa> |
|||
use GenericQueue (QueueofPersons, Person); |
use GenericQueue (QueueofPersons, Person); |
||
type Person = text; |
type Person = text; |
||
Line 2,878: | Line 2,878: | ||
Pull (Q)? |
Pull (Q)? |
||
***** Exception: Queue Underflow |
***** Exception: Queue Underflow |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Erlang}} |
{{trans|Erlang}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Queue do |
||
def new, do: {Queue, [], []} |
def new, do: {Queue, [], []} |
||
Line 2,893: | Line 2,893: | ||
def empty?({Queue, [], []}), do: true |
def empty?({Queue, [], []}), do: true |
||
def empty?({Queue, _, _}), do: false |
def empty?({Queue, _, _}), do: false |
||
end</ |
end</syntaxhighlight> |
||
Example: |
Example: |
||
Line 2,921: | Line 2,921: | ||
The standard way to manage fifo in functional programming is to use a pair of list for the fifo queue, one is the input, the other is the output. |
The standard way to manage fifo in functional programming is to use a pair of list for the fifo queue, one is the input, the other is the output. |
||
When the output is empty just take the input list and reverse it. |
When the output is empty just take the input list and reverse it. |
||
< |
<syntaxhighlight lang="erlang">-module(fifo). |
||
-export([new/0, push/2, pop/1, empty/1]). |
-export([new/0, push/2, pop/1, empty/1]). |
||
Line 2,933: | Line 2,933: | ||
empty({fifo, [], []}) -> true; |
empty({fifo, [], []}) -> true; |
||
empty({fifo, _, _}) -> false.</ |
empty({fifo, _, _}) -> false.</syntaxhighlight> |
||
Note that there exists a 'queue' module in the standard library handling this for you in the first place |
Note that there exists a 'queue' module in the standard library handling this for you in the first place |
||
Line 2,939: | Line 2,939: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
With ERRE 3.0 you can use a class to define the task (in C-64 version you can simply use procedures): |
With ERRE 3.0 you can use a class to define the task (in C-64 version you can simply use procedures): |
||
< |
<syntaxhighlight lang="erre">PROGRAM CLASS_DEMO |
||
CLASS QUEUE |
CLASS QUEUE |
||
Line 2,983: | Line 2,983: | ||
END FOR |
END FOR |
||
PRINT("* End *") |
PRINT("* End *") |
||
END PROGRAM</ |
END PROGRAM</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Push 1 |
<pre>Push 1 |
||
Line 2,998: | Line 2,998: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="factor">USING: accessors kernel ; |
||
IN: rosetta-code.queue-definition |
IN: rosetta-code.queue-definition |
||
Line 3,015: | Line 3,015: | ||
: dequeue ( queue -- obj ) |
: dequeue ( queue -- obj ) |
||
dup empty? [ "Cannot dequeue empty queue." throw ] when |
dup empty? [ "Cannot dequeue empty queue." throw ] when |
||
[ head>> value>> ] [ head>> next>> ] [ head<< ] tri ;</ |
[ head>> value>> ] [ head>> next>> ] [ head<< ] tri ;</syntaxhighlight> |
||
=={{header|Fantom}}== |
=={{header|Fantom}}== |
||
< |
<syntaxhighlight lang="fantom"> |
||
class Queue |
class Queue |
||
{ |
{ |
||
Line 3,044: | Line 3,044: | ||
} |
} |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
This is a FIFO implemented as a circular buffer, as is often found between communicating processes such the interrupt and user parts of a device driver. In practice, the get/put actions would block instead of aborting if the queue is empty/full. |
This is a FIFO implemented as a circular buffer, as is often found between communicating processes such the interrupt and user parts of a device driver. In practice, the get/put actions would block instead of aborting if the queue is empty/full. |
||
< |
<syntaxhighlight lang="forth">1024 constant size |
||
create buffer size cells allot |
create buffer size cells allot |
||
here constant end |
here constant end |
||
Line 3,070: | Line 3,070: | ||
empty? abort" buffer empty" |
empty? abort" buffer empty" |
||
\ begin empty? while pause repeat |
\ begin empty? while pause repeat |
||
head @ @ head @ next head ! -1 used +! ;</ |
head @ @ head @ next head ! -1 used +! ;</syntaxhighlight> |
||
=== Linked list version === |
=== Linked list version === |
||
Line 3,076: | Line 3,076: | ||
Using Forth-2012 structure words and ALLOCATE/FREE. In spirit quite similar to the Java variant below, with one difference: Here we use addresses of fields (not possible in Java), which often makes things simpler than in Java (fewer special cases at boundaries), but in this case it does not. Where the Java version has a special case on enqueue, this version has a special case on dequeue: |
Using Forth-2012 structure words and ALLOCATE/FREE. In spirit quite similar to the Java variant below, with one difference: Here we use addresses of fields (not possible in Java), which often makes things simpler than in Java (fewer special cases at boundaries), but in this case it does not. Where the Java version has a special case on enqueue, this version has a special case on dequeue: |
||
< |
<syntaxhighlight lang="forth"> |
||
0 |
0 |
||
field: list-next |
field: list-next |
||
Line 3,119: | Line 3,119: | ||
over init-queue then |
over init-queue then |
||
nip ; |
nip ; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
Line 3,126: | Line 3,126: | ||
See [[FIFO (usage)]] for an example of <code>fifo_nodes</code> |
See [[FIFO (usage)]] for an example of <code>fifo_nodes</code> |
||
< |
<syntaxhighlight lang="fortran">module FIFO |
||
use fifo_nodes |
use fifo_nodes |
||
! fifo_nodes must define the type fifo_node, with the two field |
! fifo_nodes must define the type fifo_node, with the two field |
||
Line 3,194: | Line 3,194: | ||
end function fifo_isempty |
end function fifo_isempty |
||
end module FIFO</ |
end module FIFO</syntaxhighlight> |
||
=={{header|Free Pascal}}== |
=={{header|Free Pascal}}== |
||
< |
<syntaxhighlight lang="pascal">program queue; |
||
{$IFDEF FPC}{$MODE DELPHI}{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}{$ENDIF} |
{$IFDEF FPC}{$MODE DELPHI}{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}{$ENDIF} |
||
{$ASSERTIONS ON} |
{$ASSERTIONS ON} |
||
Line 3,217: | Line 3,217: | ||
lQueue.Free; |
lQueue.Free; |
||
end; |
end; |
||
end.</ |
end.</syntaxhighlight> |
||
<pre> |
<pre> |
||
Output: |
Output: |
||
Line 3,224: | Line 3,224: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
We first use a macro to define a generic Queue type : |
We first use a macro to define a generic Queue type : |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
' queue_rosetta.bi |
' queue_rosetta.bi |
||
Line 3,312: | Line 3,312: | ||
Return size |
Return size |
||
End Function |
End Function |
||
#EndMacro</ |
#EndMacro</syntaxhighlight> |
||
We now use this type to create a Queue of Cat instances : |
We now use this type to create a Queue of Cat instances : |
||
< |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
#Include "queue_rosetta.bi" |
#Include "queue_rosetta.bi" |
||
Line 3,366: | Line 3,366: | ||
Print |
Print |
||
Print "Press any key to quit" |
Print "Press any key to quit" |
||
Sleep</ |
Sleep</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,384: | Line 3,384: | ||
=={{header|GAP}}== |
=={{header|GAP}}== |
||
< |
<syntaxhighlight lang="gap">Enqueue := function(v, x) |
||
Add(v[1], x); |
Add(v[1], x); |
||
end; |
end; |
||
Line 3,417: | Line 3,417: | ||
# 6 |
# 6 |
||
Dequeue(v); |
Dequeue(v); |
||
# fail</ |
# fail</syntaxhighlight> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
Hard coded to be a queue of strings. Implementation is a circular buffer which grows as needed. |
Hard coded to be a queue of strings. Implementation is a circular buffer which grows as needed. |
||
<syntaxhighlight lang="go"> |
|||
<lang go> |
|||
package queue |
package queue |
||
Line 3,477: | Line 3,477: | ||
return q.head == q.tail |
return q.head == q.tail |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
Solution: |
Solution: |
||
< |
<syntaxhighlight lang="groovy">class Queue { |
||
private List buffer |
private List buffer |
||
Line 3,502: | Line 3,502: | ||
String toString() { "Queue:${buffer}" } |
String toString() { "Queue:${buffer}" } |
||
}</ |
}</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="groovy">def q = new Queue() |
||
assert q.empty |
assert q.empty |
||
Line 3,531: | Line 3,531: | ||
assert q.empty |
assert q.empty |
||
try { q.pop() } catch (NoSuchElementException e) { println e } |
try { q.pop() } catch (NoSuchElementException e) { println e } |
||
try { q.dequeue() } catch (NoSuchElementException e) { println e }</ |
try { q.dequeue() } catch (NoSuchElementException e) { println e }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,549: | Line 3,549: | ||
When the output is empty just take the input list and reverse it. |
When the output is empty just take the input list and reverse it. |
||
< |
<syntaxhighlight lang="haskell">data Fifo a = F [a] [a] |
||
emptyFifo :: Fifo a |
emptyFifo :: Fifo a |
||
Line 3,565: | Line 3,565: | ||
isEmpty (F [] []) = True |
isEmpty (F [] []) = True |
||
isEmpty _ = False |
isEmpty _ = False |
||
</syntaxhighlight> |
|||
</lang> |
|||
== Icon and Unicon == |
== Icon and Unicon == |
||
Line 3,573: | Line 3,573: | ||
The following works in both Icon and Unicon: |
The following works in both Icon and Unicon: |
||
< |
<syntaxhighlight lang="icon"> |
||
# Use a record to hold a Queue, using a list as the concrete implementation |
# Use a record to hold a Queue, using a list as the concrete implementation |
||
record Queue(items) |
record Queue(items) |
||
Line 3,608: | Line 3,608: | ||
} |
} |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,624: | Line 3,624: | ||
Unicon also provides classes: |
Unicon also provides classes: |
||
<syntaxhighlight lang="unicon"> |
|||
<lang Unicon> |
|||
# Use a class to hold a Queue, with a list as the concrete implementation |
# Use a class to hold a Queue, with a list as the concrete implementation |
||
class Queue (items) |
class Queue (items) |
||
Line 3,655: | Line 3,655: | ||
} |
} |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
Produces the same output as above. |
Produces the same output as above. |
||
Line 3,662: | Line 3,662: | ||
Object oriented technique, using mutable state: |
Object oriented technique, using mutable state: |
||
< |
<syntaxhighlight lang="j">queue_fifo_=: '' |
||
pop_fifo_=: verb define |
pop_fifo_=: verb define |
||
Line 3,677: | Line 3,677: | ||
isEmpty_fifo_=: verb define |
isEmpty_fifo_=: verb define |
||
0=#queue |
0=#queue |
||
)</ |
)</syntaxhighlight> |
||
Function-level technique, with no reliance on mutable state: |
Function-level technique, with no reliance on mutable state: |
||
< |
<syntaxhighlight lang="j">pop =: ( {.^:notnull ; }. )@: > @: ] / |
||
push =: ( '' ; ,~ )& > / |
push =: ( '' ; ,~ )& > / |
||
tell_atom =: >& {. |
tell_atom =: >& {. |
||
Line 3,690: | Line 3,690: | ||
onto =: [ ; }.@] |
onto =: [ ; }.@] |
||
notnull =: 0 ~: #</ |
notnull =: 0 ~: #</syntaxhighlight> |
||
See also [[FIFO (usage)#J]] |
See also [[FIFO (usage)#J]] |
||
Line 3,697: | Line 3,697: | ||
{{works with|Java|1.5+}} |
{{works with|Java|1.5+}} |
||
This task could be done using a LinkedList from java.util, but here is a user-defined version with generics: |
This task could be done using a LinkedList from java.util, but here is a user-defined version with generics: |
||
< |
<syntaxhighlight lang="java">public class Queue<E>{ |
||
Node<E> head = null, tail = null; |
Node<E> head = null, tail = null; |
||
Line 3,736: | Line 3,736: | ||
return head == null; |
return head == null; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
Line 3,742: | Line 3,742: | ||
=== Using built-in Array === |
=== Using built-in Array === |
||
< |
<syntaxhighlight lang="javascript">var fifo = []; |
||
fifo.push(42); // Enqueue. |
fifo.push(42); // Enqueue. |
||
fifo.push(43); |
fifo.push(43); |
||
var x = fifo.shift(); // Dequeue. |
var x = fifo.shift(); // Dequeue. |
||
alert(x); // 42</ |
alert(x); // 42</syntaxhighlight> |
||
=== Custom constructor function === |
=== Custom constructor function === |
||
< |
<syntaxhighlight lang="javascript">function FIFO() { |
||
this.data = new Array(); |
this.data = new Array(); |
||
Line 3,758: | Line 3,758: | ||
this.enqueue = this.push; |
this.enqueue = this.push; |
||
this.dequeue = this.pop; |
this.dequeue = this.pop; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|jq}}== |
=={{header|jq}}== |
||
Line 3,769: | Line 3,769: | ||
alternative definition, pop_or_error, is also given to illustrate |
alternative definition, pop_or_error, is also given to illustrate |
||
how an error condition can be generated. |
how an error condition can be generated. |
||
< |
<syntaxhighlight lang="jq"># An empty queue: |
||
def fifo: []; |
def fifo: []; |
||
Line 3,778: | Line 3,778: | ||
def pop_or_error: if length == 0 then error("pop_or_error") else pop end; |
def pop_or_error: if length == 0 then error("pop_or_error") else pop end; |
||
def empty: length == 0;</ |
def empty: length == 0;</syntaxhighlight> |
||
'''Examples''': |
'''Examples''': |
||
< |
<syntaxhighlight lang="jq">fifo | pop # produces [null,[]] |
||
fifo |
fifo |
||
Line 3,792: | Line 3,792: | ||
| fifo|push(2) as $q2 |
| fifo|push(2) as $q2 |
||
| [($q1|pop|.[0]), ($q2|pop|.[0])] |
| [($q1|pop|.[0]), ($q2|pop|.[0])] |
||
# produces: [1, 2]</ |
# produces: [1, 2]</syntaxhighlight> |
||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
Julia provides a variety of queue-like methods for vectors, making the solution to this task rather straightforward. Define a <tt>Queue</tt> in terms of a one dimensional array, and provide its methods using the appropriate vector operations. To adhere to Julia naming conventions, the queue operations are named "push!", "pop!" and "isempty" rather than "push", "pop" and "empty". |
Julia provides a variety of queue-like methods for vectors, making the solution to this task rather straightforward. Define a <tt>Queue</tt> in terms of a one dimensional array, and provide its methods using the appropriate vector operations. To adhere to Julia naming conventions, the queue operations are named "push!", "pop!" and "isempty" rather than "push", "pop" and "empty". |
||
<syntaxhighlight lang="julia"> |
|||
<lang Julia> |
|||
struct Queue{T} |
struct Queue{T} |
||
a::Array{T,1} |
a::Array{T,1} |
||
Line 3,821: | Line 3,821: | ||
return q |
return q |
||
end |
end |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,872: | Line 3,872: | ||
=={{header|Klingphix}}== |
=={{header|Klingphix}}== |
||
< |
<syntaxhighlight lang="klingphix">{ include ..\Utilitys.tlhy } |
||
"..\Utilitys.tlhy" load |
"..\Utilitys.tlhy" load |
||
Line 3,897: | Line 3,897: | ||
pop! ? pop! ? pop! ? pop! ? |
pop! ? pop! ? pop! ? pop! ? |
||
"End " input</ |
"End " input</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 |
<pre>1 |
||
Line 3,906: | Line 3,906: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
< |
<syntaxhighlight lang="scala">// version 1.1.2 |
||
import java.util.LinkedList |
import java.util.LinkedList |
||
Line 3,952: | Line 3,952: | ||
println(e.message) |
println(e.message) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,970: | Line 3,970: | ||
=={{header|Lasso}}== |
=={{header|Lasso}}== |
||
Definition: |
Definition: |
||
< |
<syntaxhighlight lang="lasso">define myqueue => type { |
||
data store = list |
data store = list |
||
Line 3,990: | Line 3,990: | ||
public isEmpty => (.`store`->size == 0) |
public isEmpty => (.`store`->size == 0) |
||
}</ |
}</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang="lasso">local(q) = myqueue('a') |
||
#q->isEmpty |
#q->isEmpty |
||
// => false |
// => false |
||
Line 4,006: | Line 4,006: | ||
// => true |
// => true |
||
#q->pop |
#q->pop |
||
// => void</ |
// => void</syntaxhighlight> |
||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
< |
<syntaxhighlight lang="lua">Queue = {} |
||
function Queue.new() |
function Queue.new() |
||
Line 4,033: | Line 4,033: | ||
function Queue.empty( queue ) |
function Queue.empty( queue ) |
||
return queue.first > queue.last |
return queue.first > queue.last |
||
end</ |
end</syntaxhighlight> |
||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
A Stack object can be used as LIFO or FIFO. Data push to bottom of stack. Read pop a value to a variable from top of stack. |
A Stack object can be used as LIFO or FIFO. Data push to bottom of stack. Read pop a value to a variable from top of stack. |
||
<syntaxhighlight lang="m2000 interpreter"> |
|||
<lang M2000 Interpreter> |
|||
Module Checkit { |
Module Checkit { |
||
a=Stack |
a=Stack |
||
Line 4,051: | Line 4,051: | ||
} |
} |
||
Checkit |
Checkit |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">EmptyQ[a_] := Length[a] == 0 |
||
SetAttributes[Push, HoldAll]; Push[a_, elem_] := AppendTo[a, elem] |
SetAttributes[Push, HoldAll]; Push[a_, elem_] := AppendTo[a, elem] |
||
SetAttributes[Pop, HoldAllComplete]; Pop[a_] := If[EmptyQ[a], False, b = First[a]; Set[a, Most[a]]; b]</ |
SetAttributes[Pop, HoldAllComplete]; Pop[a_] := If[EmptyQ[a], False, b = First[a]; Set[a, Most[a]]; b]</syntaxhighlight> |
||
=={{header|MATLAB}} / {{header|Octave}}== |
=={{header|MATLAB}} / {{header|Octave}}== |
||
Here is a simple implementation of a queue, that works in Matlab and Octave. |
Here is a simple implementation of a queue, that works in Matlab and Octave. |
||
< |
<syntaxhighlight lang="matlab">myfifo = {}; |
||
% push |
% push |
||
Line 4,070: | Line 4,070: | ||
% empty |
% empty |
||
isempty(myfifo)</ |
isempty(myfifo)</syntaxhighlight> |
||
Below is another solution, that encapsulates the fifo within the object-orientated "class" elements supported by Matlab. For this to work it must be saved in a file named "FIFOQueue.m" in a folder named "@FIFOQueue" in your current Matlab directory. |
Below is another solution, that encapsulates the fifo within the object-orientated "class" elements supported by Matlab. For this to work it must be saved in a file named "FIFOQueue.m" in a folder named "@FIFOQueue" in your current Matlab directory. |
||
< |
<syntaxhighlight lang="matlab">%This class impliments a standard FIFO queue. |
||
classdef FIFOQueue |
classdef FIFOQueue |
||
Line 4,154: | Line 4,154: | ||
end %methods |
end %methods |
||
end</ |
end</syntaxhighlight> |
||
Sample usage: |
Sample usage: |
||
< |
<syntaxhighlight lang="matlab">>> myQueue = FIFOQueue({'hello'}) |
||
myQueue = |
myQueue = |
||
Line 4,178: | Line 4,178: | ||
>> pop(myQueue) |
>> pop(myQueue) |
||
??? Error using ==> FIFOQueue.FIFOQueue>FIFOQueue.pop at 61 |
??? Error using ==> FIFOQueue.FIFOQueue>FIFOQueue.pop at 61 |
||
The queue is empty</ |
The queue is empty</syntaxhighlight> |
||
=={{header|Maxima}}== |
=={{header|Maxima}}== |
||
< |
<syntaxhighlight lang="maxima">defstruct(queue(in=[], out=[]))$ |
||
enqueue(x, q) := (q@in: cons(x, q@in), done)$ |
enqueue(x, q) := (q@in: cons(x, q@in), done)$ |
||
Line 4,198: | Line 4,198: | ||
dequeue(q); /* 3 */ |
dequeue(q); /* 3 */ |
||
dequeue(q); /* 4 */ |
dequeue(q); /* 4 */ |
||
dequeue(q); /* fail */</ |
dequeue(q); /* fail */</syntaxhighlight> |
||
=={{header|Nanoquery}}== |
=={{header|Nanoquery}}== |
||
This is a fully-featured FIFO queue class definition. In addition to the functions required by the task, it also demonstrates redefining operators for Nanoquery classes by redefining +, *, and =. |
This is a fully-featured FIFO queue class definition. In addition to the functions required by the task, it also demonstrates redefining operators for Nanoquery classes by redefining +, *, and =. |
||
< |
<syntaxhighlight lang="nanoquery">class FIFO |
||
declare contents |
declare contents |
||
Line 4,251: | Line 4,251: | ||
return this.contents = other.contents |
return this.contents = other.contents |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
Unlike [[#REXX|Rexx]], NetRexx does not include built–in support for queues but the language's ability to access the [[Java]] SDK permits use of any number of Java's "Collection" classes. |
Unlike [[#REXX|Rexx]], NetRexx does not include built–in support for queues but the language's ability to access the [[Java]] SDK permits use of any number of Java's "Collection" classes. |
||
The following sample implements a stack via the <code>ArrayDeque</code> double–ended queue. |
The following sample implements a stack via the <code>ArrayDeque</code> double–ended queue. |
||
< |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref savelog symbols nobinary |
options replace format comments java crossref savelog symbols nobinary |
||
Line 4,291: | Line 4,291: | ||
return |
return |
||
</syntaxhighlight> |
|||
</lang> |
|||
<pre style="height: 20ex; overflow: scroll;"> |
<pre style="height: 20ex; overflow: scroll;"> |
||
Line 4,305: | Line 4,305: | ||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">type |
||
Node[T] = ref object |
Node[T] = ref object |
||
Line 4,353: | Line 4,353: | ||
echo "Popping: ", fifo.pop() |
echo "Popping: ", fifo.pop() |
||
except ValueError: |
except ValueError: |
||
echo "Exception catched: ", getCurrentExceptionMsg()</ |
echo "Exception catched: ", getCurrentExceptionMsg()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Fifo size: 3 |
<pre>Fifo size: 3 |
||
Line 4,366: | Line 4,366: | ||
When the output is empty just take the input list and reverse it. |
When the output is empty just take the input list and reverse it. |
||
< |
<syntaxhighlight lang="ocaml">module FIFO : sig |
||
type 'a fifo |
type 'a fifo |
||
val empty: 'a fifo |
val empty: 'a fifo |
||
Line 4,385: | Line 4,385: | ||
| [], [] -> failwith "empty fifo" |
| [], [] -> failwith "empty fifo" |
||
| input, [] -> pop ([], List.rev input) |
| input, [] -> pop ([], List.rev input) |
||
end</ |
end</syntaxhighlight> |
||
and a session in the top-level: |
and a session in the top-level: |
||
< |
<syntaxhighlight lang="ocaml"># open FIFO;; |
||
# let q = empty ;; |
# let q = empty ;; |
||
val q : '_a FIFO.fifo = <abstr> |
val q : '_a FIFO.fifo = <abstr> |
||
Line 4,416: | Line 4,416: | ||
val q : int FIFO.fifo = <abstr> |
val q : int FIFO.fifo = <abstr> |
||
# let v, q = pop q ;; |
# let v, q = pop q ;; |
||
Exception: Failure "empty fifo".</ |
Exception: Failure "empty fifo".</syntaxhighlight> |
||
The standard ocaml library also provides a |
The standard ocaml library also provides a |
||
Line 4,426: | Line 4,426: | ||
If queue is empty, null is returned. |
If queue is empty, null is returned. |
||
< |
<syntaxhighlight lang="oforth">Object Class new: Queue(mutable l) |
||
Queue method: initialize ListBuffer new := l ; |
Queue method: initialize ListBuffer new := l ; |
||
Queue method: empty @l isEmpty ; |
Queue method: empty @l isEmpty ; |
||
Queue method: push @l add ; |
Queue method: push @l add ; |
||
Queue method: pop @l removeFirst ;</ |
Queue method: pop @l removeFirst ;</syntaxhighlight> |
||
=={{header|OxygenBasic}}== |
=={{header|OxygenBasic}}== |
||
This buffer pushes any primitive data (auto converted to strings), and pops strings. The buffer can expand or contract according to usage. |
This buffer pushes any primitive data (auto converted to strings), and pops strings. The buffer can expand or contract according to usage. |
||
<lang> |
<syntaxhighlight lang="text"> |
||
'========== |
'========== |
||
Line 4,535: | Line 4,535: | ||
del fifo |
del fifo |
||
</ |
</syntaxhighlight> |
||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
Line 4,544: | Line 4,544: | ||
The implementation is thread-safe if there is only one reader thread. When multiple reader threads exist, it is possible that a value is popped more than once. |
The implementation is thread-safe if there is only one reader thread. When multiple reader threads exist, it is possible that a value is popped more than once. |
||
< |
<syntaxhighlight lang="oz">declare |
||
fun {NewQueue} |
fun {NewQueue} |
||
Stream |
Stream |
||
Line 4,577: | Line 4,577: | ||
{Show {Empty Q}} |
{Show {Empty Q}} |
||
{Show {Pop Q}} |
{Show {Pop Q}} |
||
{Show {Empty Q}}</ |
{Show {Empty Q}}</syntaxhighlight> |
||
There is also a [http://www.mozart-oz.org/home/doc/mozart-stdlib/adt/queue.html queue datatype] in the Mozart standard library. |
There is also a [http://www.mozart-oz.org/home/doc/mozart-stdlib/adt/queue.html queue datatype] in the Mozart standard library. |
||
Line 4,588: | Line 4,588: | ||
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). |
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). |
||
< |
<syntaxhighlight lang="pascal">program fifo(input, output); |
||
type |
type |
||
Line 4,688: | Line 4,688: | ||
testFifo; |
testFifo; |
||
writeln('Testing finished.') |
writeln('Testing finished.') |
||
end.</ |
end.</syntaxhighlight> |
||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
Lists are a central part of Perl. To implement a FIFO using OO will to many Perl programmers seem a bit awkward. |
Lists are a central part of Perl. To implement a FIFO using OO will to many Perl programmers seem a bit awkward. |
||
< |
<syntaxhighlight lang="perl">use Carp; |
||
sub mypush (\@@) {my($list,@things)=@_; push @$list, @things} |
sub mypush (\@@) {my($list,@things)=@_; push @$list, @things} |
||
sub mypop (\@) {my($list)=@_; @$list or croak "Empty"; shift @$list } |
sub mypop (\@) {my($list)=@_; @$list or croak "Empty"; shift @$list } |
||
sub empty (@) {not @_}</ |
sub empty (@) {not @_}</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang="perl">my @fifo=qw(1 2 3 a b c); |
||
mypush @fifo, 44, 55, 66; |
mypush @fifo, 44, 55, 66; |
||
mypop @fifo for 1 .. 6+3; |
mypop @fifo for 1 .. 6+3; |
||
mypop @fifo; #empty now</ |
mypop @fifo; #empty now</syntaxhighlight> |
||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">queue</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
<span style="color: #004080;">sequence</span> <span style="color: #000000;">queue</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
||
Line 4,724: | Line 4,724: | ||
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">queue</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> |
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">queue</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> |
||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
As of 1.0.2 there are standard builtins for the above, named new_queue(), push(), and queue_empty() respectively, see docs. |
As of 1.0.2 there are standard builtins for the above, named new_queue(), push(), and queue_empty() respectively, see docs. |
||
=={{header|Phixmonti}}== |
=={{header|Phixmonti}}== |
||
< |
<syntaxhighlight lang="phixmonti">include ..\Utilitys.pmt |
||
def push /# l i -- l&i #/ |
def push /# l i -- l&i #/ |
||
Line 4,750: | Line 4,750: | ||
1 push 2 push 3 push |
1 push 2 push 3 push |
||
pop ? pop ? pop ? pop ?</ |
pop ? pop ? pop ? pop ?</syntaxhighlight> |
||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
< |
<syntaxhighlight lang="php">class Fifo { |
||
private $data = array(); |
private $data = array(); |
||
public function push($element){ |
public function push($element){ |
||
Line 4,773: | Line 4,773: | ||
return empty($this->data); |
return empty($this->data); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Example: |
Example: |
||
< |
<syntaxhighlight lang="php">$foo = new Fifo(); |
||
$foo->push('One'); |
$foo->push('One'); |
||
$foo->enqueue('Two'); |
$foo->enqueue('Two'); |
||
Line 4,786: | Line 4,786: | ||
echo $foo->pop(); //Prints 'Three' |
echo $foo->pop(); //Prints 'Three' |
||
echo $foo->pop(); //Throws an exception |
echo $foo->pop(); //Throws an exception |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Picat}}== |
=={{header|Picat}}== |
||
===First variant=== |
===First variant=== |
||
< |
<syntaxhighlight lang="picat">go => |
||
println("Test 1"), |
println("Test 1"), |
||
queue_test1, |
queue_test1, |
||
Line 4,838: | Line 4,838: | ||
nl, |
nl, |
||
println("\nEnd of tests.").</ |
println("\nEnd of tests.").</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,865: | Line 4,865: | ||
</pre> |
</pre> |
||
< |
<syntaxhighlight lang="picat">go2 => |
||
println("Test 2"), |
println("Test 2"), |
||
queue_test2, |
queue_test2, |
||
Line 4,915: | Line 4,915: | ||
printf("V3: %w V4: %w\n", V3, V4), |
printf("V3: %w V4: %w\n", V3, V4), |
||
nl, |
nl, |
||
println(q=Q).</ |
println(q=Q).</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,942: | Line 4,942: | ||
The built-in function 'fifo' maintains a queue in a circular list, with direct |
The built-in function 'fifo' maintains a queue in a circular list, with direct |
||
access to the first and the last cell |
access to the first and the last cell |
||
< |
<syntaxhighlight lang="picolisp">(off Queue) # Clear Queue |
||
(fifo 'Queue 1) # Store number '1' |
(fifo 'Queue 1) # Store number '1' |
||
(fifo 'Queue 'abc) # an internal symbol 'abc' |
(fifo 'Queue 'abc) # an internal symbol 'abc' |
||
(fifo 'Queue "abc") # a transient symbol "abc" |
(fifo 'Queue "abc") # a transient symbol "abc" |
||
(fifo 'Queue '(a b c)) # and a list (a b c) |
(fifo 'Queue '(a b c)) # and a list (a b c) |
||
Queue # Show the queue</ |
Queue # Show the queue</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>->((a b c) 1 abc "abc" .)</pre> |
<pre>->((a b c) 1 abc "abc" .)</pre> |
||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
< |
<syntaxhighlight lang="pli"> |
||
/* To push a node onto the end of the queue. */ |
/* To push a node onto the end of the queue. */ |
||
push: procedure (tail); |
push: procedure (tail); |
||
Line 4,981: | Line 4,981: | ||
return (h = bind(:Node, null:) ); |
return (h = bind(:Node, null:) ); |
||
end empty; |
end empty; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PostScript}}== |
=={{header|PostScript}}== |
||
{{libheader|initlib}} |
{{libheader|initlib}} |
||
< |
<syntaxhighlight lang="postscript"> |
||
% our queue is just [] and empty? is already defined. |
% our queue is just [] and empty? is already defined. |
||
/push {exch tadd}. |
/push {exch tadd}. |
||
/pop {uncons exch}. |
/pop {uncons exch}. |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
{{works with|PowerShell|2}}<br/> |
{{works with|PowerShell|2}}<br/> |
||
PowerShell can natively use the .Net Queue class. |
PowerShell can natively use the .Net Queue class. |
||
<syntaxhighlight lang="powershell"> |
|||
<lang PowerShell> |
|||
$Q = New-Object System.Collections.Queue |
$Q = New-Object System.Collections.Queue |
||
Line 5,011: | Line 5,011: | ||
{ $Q.Dequeue() } |
{ $Q.Dequeue() } |
||
catch [System.InvalidOperationException] |
catch [System.InvalidOperationException] |
||
{ If ( $_.Exception.Message -eq 'Queue empty.' ) { 'Caught error' } }</ |
{ If ( $_.Exception.Message -eq 'Queue empty.' ) { 'Caught error' } }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>1 |
<pre>1 |
||
Line 5,023: | Line 5,023: | ||
Works with SWI-Prolog. |
Works with SWI-Prolog. |
||
One can push any data in queue. |
One can push any data in queue. |
||
< |
<syntaxhighlight lang="prolog">empty(U-V) :- |
||
unify_with_occurs_check(U, V). |
unify_with_occurs_check(U, V). |
||
Line 5,034: | Line 5,034: | ||
append_dl(X-Y, Y-Z, X-Z). |
append_dl(X-Y, Y-Z, X-Z). |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
For FIFO function PureBasic normally uses linked lists. |
For FIFO function PureBasic normally uses linked lists. |
||
Usage as described above could look like; |
Usage as described above could look like; |
||
< |
<syntaxhighlight lang="purebasic">NewList MyStack() |
||
Procedure Push(n) |
Procedure Push(n) |
||
Line 5,076: | Line 5,076: | ||
Wend |
Wend |
||
;---- Now an extra Pop(), e.g. one to many ---- |
;---- Now an extra Pop(), e.g. one to many ---- |
||
Debug Pop()</ |
Debug Pop()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,092: | Line 5,092: | ||
To encapsulate this behavior into a class and provide the task's specific API we can simply use: |
To encapsulate this behavior into a class and provide the task's specific API we can simply use: |
||
< |
<syntaxhighlight lang="python"> class FIFO(object): |
||
def __init__(self, *args): |
def __init__(self, *args): |
||
self.contents = list(args) |
self.contents = list(args) |
||
Line 5,136: | Line 5,136: | ||
f = FIFO(3,2,1) |
f = FIFO(3,2,1) |
||
for i in f: |
for i in f: |
||
print i,</ |
print i,</syntaxhighlight> |
||
This example does add to a couple of features which are easy in Python and allow this FIFO class to be used in ways that Python programmers might find more natural. Our ''__init__'' accepts and optional list of initial values, we add ''__len__'' and ''extend'' methods which simply wrap the corresponding list methods; we define a ''__call__'' method to show how one can make objects "callable" as functions, and we define ''__iter__'' and ''next()'' methods to facilitate using these FIFO objects with Python's prevalent iteration syntax (the ''for'' loop). The ''empty'' method could be implemented as simply an alias for ''__len__'' --- but we've chosen to have it more strictly conform to the task specification. Implementing the ''__len__'' method allows code using this object to test of emptiness using normal Python idioms for "truth" (any non-empty container is considered to be "true" and any empty container evaluates as "false"). |
This example does add to a couple of features which are easy in Python and allow this FIFO class to be used in ways that Python programmers might find more natural. Our ''__init__'' accepts and optional list of initial values, we add ''__len__'' and ''extend'' methods which simply wrap the corresponding list methods; we define a ''__call__'' method to show how one can make objects "callable" as functions, and we define ''__iter__'' and ''next()'' methods to facilitate using these FIFO objects with Python's prevalent iteration syntax (the ''for'' loop). The ''empty'' method could be implemented as simply an alias for ''__len__'' --- but we've chosen to have it more strictly conform to the task specification. Implementing the ''__len__'' method allows code using this object to test of emptiness using normal Python idioms for "truth" (any non-empty container is considered to be "true" and any empty container evaluates as "false"). |
||
Line 5,144: | Line 5,144: | ||
That sort of wrapper looks like: |
That sort of wrapper looks like: |
||
< |
<syntaxhighlight lang="python">class FIFO: ## NOT a new-style class, must not derive from "object" |
||
def __init__(self,*args): |
def __init__(self,*args): |
||
self.contents = list(args) |
self.contents = list(args) |
||
Line 5,158: | Line 5,158: | ||
if not self: |
if not self: |
||
raise StopIteration |
raise StopIteration |
||
return self.pop()</ |
return self.pop()</syntaxhighlight> |
||
As noted in the contents this must NOT be a new-style class, it must NOT but sub-classed from ''object'' nor any of its descendents. (A new-style implementation using __getattribute__ would be possible) |
As noted in the contents this must NOT be a new-style class, it must NOT but sub-classed from ''object'' nor any of its descendents. (A new-style implementation using __getattribute__ would be possible) |
||
Line 5,166: | Line 5,166: | ||
Python 2.4 and later includes a [http://docs.python.org/lib/deque-objects.html 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 [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436 Python Cookbook]. |
Python 2.4 and later includes a [http://docs.python.org/lib/deque-objects.html 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 [http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/68436 Python Cookbook]. |
||
< |
<syntaxhighlight lang="python">from collections import deque |
||
fifo = deque() |
fifo = deque() |
||
fifo. appendleft(value) # push |
fifo. appendleft(value) # push |
||
value = fifo.pop() |
value = fifo.pop() |
||
not fifo # empty |
not fifo # empty |
||
fifo.pop() # raises IndexError when empty</ |
fifo.pop() # raises IndexError when empty</syntaxhighlight> |
||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||
< |
<syntaxhighlight lang="quackery"> [ [] ] is queue ( --> [ ) |
||
[ [] = ] is empty? ( [ --> b ) |
[ [] = ] is empty? ( [ --> b ) |
||
Line 5,184: | Line 5,184: | ||
[ $ "Queue unexpectedly empty." |
[ $ "Queue unexpectedly empty." |
||
fail ] |
fail ] |
||
behead ] is pop ( [ --> [ x )</ |
behead ] is pop ( [ --> [ x )</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,212: | Line 5,212: | ||
===Simple functional implementation=== |
===Simple functional implementation=== |
||
This simple implementation provides three functions that act on a variable in the global environment (user workspace) named ''l''. the push and pop functions display the new status of ''l'', but return NULL silently. |
This simple implementation provides three functions that act on a variable in the global environment (user workspace) named ''l''. the push and pop functions display the new status of ''l'', but return NULL silently. |
||
< |
<syntaxhighlight lang="r">empty <- function() length(l) == 0 |
||
push <- function(x) |
push <- function(x) |
||
{ |
{ |
||
Line 5,259: | Line 5,259: | ||
# list() |
# list() |
||
pop() |
pop() |
||
# Error in pop() : can't pop from an empty list</ |
# Error in pop() : can't pop from an empty list</syntaxhighlight> |
||
The problem with this is that the functions aren't related to the FIFO object (the list ''l''), and they require the list to exist in the global environment. (This second problem is possible to get round by passing ''l'' into the function and then returning it, but that is extra work.) |
The problem with this is that the functions aren't related to the FIFO object (the list ''l''), and they require the list to exist in the global environment. (This second problem is possible to get round by passing ''l'' into the function and then returning it, but that is extra work.) |
||
Line 5,265: | Line 5,265: | ||
===Message passing=== |
===Message passing=== |
||
< |
<syntaxhighlight lang="r"># The usual Scheme way : build a function that takes commands as parameters (it's like message passing oriented programming) |
||
queue <- function() { |
queue <- function() { |
||
v <- list() |
v <- list() |
||
Line 5,303: | Line 5,303: | ||
# [1] 1 |
# [1] 1 |
||
b("pop") |
b("pop") |
||
# [1] 3</ |
# [1] 3</syntaxhighlight> |
||
===Object oriented implementation=== |
===Object oriented implementation=== |
||
Line 5,309: | Line 5,309: | ||
A better solution is to use the object oriented facility in the proto package. (R does have it's own native object oriented code, though the proto package is often nicer to use.) |
A better solution is to use the object oriented facility in the proto package. (R does have it's own native object oriented code, though the proto package is often nicer to use.) |
||
< |
<syntaxhighlight lang="r">library(proto) |
||
fifo <- proto(expr = { |
fifo <- proto(expr = { |
||
Line 5,338: | Line 5,338: | ||
fifo$pop() |
fifo$pop() |
||
fifo$pop() |
fifo$pop() |
||
fifo$pop()</ |
fifo$pop()</syntaxhighlight> |
||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
Line 5,345: | Line 5,345: | ||
Here's an explicit implementation: |
Here's an explicit implementation: |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
Line 5,368: | Line 5,368: | ||
(pop! Q) ; -> 'x |
(pop! Q) ; -> 'x |
||
(list (pop! Q) (pop! Q) (pop! Q)) ; -> '(0 1 2) |
(list (pop! Q) (pop! Q) (pop! Q)) ; -> '(0 1 2) |
||
</syntaxhighlight> |
|||
</lang> |
|||
And this is an implementation of a functional queue. |
And this is an implementation of a functional queue. |
||
< |
<syntaxhighlight lang="racket"> |
||
#lang racket |
#lang racket |
||
;; Invariants: |
;; Invariants: |
||
Line 5,404: | Line 5,404: | ||
(push x q))))) |
(push x q))))) |
||
;; => 3 |
;; => 3 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Line 5,410: | Line 5,410: | ||
{{Works with|rakudo|2018.03}} |
{{Works with|rakudo|2018.03}} |
||
We could build a new container class to do FIFO pretty easily, but Arrays already do everything needed by a FIFO queue, so it is easier to just compose a Role on the existing Array class. |
We could build a new container class to do FIFO pretty easily, but Arrays already do everything needed by a FIFO queue, so it is easier to just compose a Role on the existing Array class. |
||
<lang |
<syntaxhighlight lang="raku" line>role FIFO { |
||
method enqueue ( *@values ) { # Add values to queue, returns the number of values added. |
method enqueue ( *@values ) { # Add values to queue, returns the number of values added. |
||
self.push: @values; |
self.push: @values; |
||
Line 5,440: | Line 5,440: | ||
say @queue.dequeue until @queue.is-empty; # -> C \n Any() \n [7 8] \n OHAI! |
say @queue.dequeue until @queue.is-empty; # -> C \n Any() \n [7 8] \n OHAI! |
||
say @queue.is-empty; # -> Bool::True |
say @queue.is-empty; # -> Bool::True |
||
say @queue.dequeue; # -></ |
say @queue.dequeue; # -></syntaxhighlight> |
||
=={{header|REBOL}}== |
=={{header|REBOL}}== |
||
< |
<syntaxhighlight lang="rebol">rebol [ |
||
Title: "FIFO" |
Title: "FIFO" |
||
URL: http://rosettacode.org/wiki/FIFO |
URL: http://rosettacode.org/wiki/FIFO |
||
Line 5,473: | Line 5,473: | ||
while [not q/empty][print [" " q/pop]] |
while [not q/empty][print [" " q/pop]] |
||
print rejoin ["Queue is " either q/empty [""]["not "] "empty."] |
print rejoin ["Queue is " either q/empty [""]["not "] "empty."] |
||
print ["Trying to pop an empty queue yields:" q/pop]</ |
print ["Trying to pop an empty queue yields:" q/pop]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 5,503: | Line 5,503: | ||
-- Gerard Schildberger. --> |
-- Gerard Schildberger. --> |
||
< |
<syntaxhighlight lang="rexx">/*REXX program to demonstrate FIFO queue usage by some simple operations*/ |
||
call viewQueue |
call viewQueue |
||
a="Fred" |
a="Fred" |
||
Line 5,522: | Line 5,522: | ||
viewQueue: if queued()==0 then say 'Queue is empty' |
viewQueue: if queued()==0 then say 'Queue is empty' |
||
else say 'There are' queued() 'elements in the queue' |
else say 'There are' queued() 'elements in the queue' |
||
return</ |
return</syntaxhighlight> |
||
'''output''' |
'''output''' |
||
<pre> |
<pre> |
||
Line 5,536: | Line 5,536: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
# Project : Queue/Definition |
# Project : Queue/Definition |
||
Line 5,556: | Line 5,556: | ||
see "Error: queue is empty" + nl |
see "Error: queue is empty" + nl |
||
ok |
ok |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 5,573: | Line 5,573: | ||
The core class ''Array'' already implements all queue operations, so this class ''FIFO'' delegates everything to methods of ''Array''. |
The core class ''Array'' already implements all queue operations, so this class ''FIFO'' delegates everything to methods of ''Array''. |
||
< |
<syntaxhighlight lang="ruby">require 'forwardable' |
||
# A FIFO queue contains elements in first-in, first-out order. |
# A FIFO queue contains elements in first-in, first-out order. |
||
Line 5,629: | Line 5,629: | ||
end |
end |
||
alias inspect to_s |
alias inspect to_s |
||
end</ |
end</syntaxhighlight> |
||
< |
<syntaxhighlight lang="ruby">f = FIFO.new |
||
f.empty? # => true |
f.empty? # => true |
||
f.pop # => nil |
f.pop # => nil |
||
Line 5,646: | Line 5,646: | ||
g.pop(2) # => [:a, :b] |
g.pop(2) # => [:a, :b] |
||
g.pop(2) # => [:c] |
g.pop(2) # => [:c] |
||
g.pop(2) # => []</ |
g.pop(2) # => []</syntaxhighlight> |
||
=={{header|Rust}}== |
=={{header|Rust}}== |
||
===Using the standard library=== |
===Using the standard library=== |
||
The standard library has a double-ended queue implementation (<code>VecDeque<T></code>) which will work here. |
The standard library has a double-ended queue implementation (<code>VecDeque<T></code>) which will work here. |
||
< |
<syntaxhighlight lang="rust">use std::collections::VecDeque; |
||
fn main() { |
fn main() { |
||
let mut stack = VecDeque::new(); |
let mut stack = VecDeque::new(); |
||
Line 5,663: | Line 5,663: | ||
assert_eq!(Some("Element3"), stack.pop_front()); |
assert_eq!(Some("Element3"), stack.pop_front()); |
||
assert_eq!(None, stack.pop_front()); |
assert_eq!(None, stack.pop_front()); |
||
}</ |
}</syntaxhighlight> |
||
===A simple implementation=== |
===A simple implementation=== |
||
This shows the implementation of a singly-linked queue with <code>dequeue</code> and <code>enqueue</code>. There are two <code>peek</code> implementations, one returns an immutable reference, the other returns a mutable one. This implementation also shows iteration over the Queue by value (consumes queue), immutable reference, and mutable reference. |
This shows the implementation of a singly-linked queue with <code>dequeue</code> and <code>enqueue</code>. There are two <code>peek</code> implementations, one returns an immutable reference, the other returns a mutable one. This implementation also shows iteration over the Queue by value (consumes queue), immutable reference, and mutable reference. |
||
< |
<syntaxhighlight lang="rust">use std::ptr; |
||
pub struct Queue<T> { |
pub struct Queue<T> { |
||
Line 5,789: | Line 5,789: | ||
}) |
}) |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
< |
<syntaxhighlight lang="scala">class Queue[T] { |
||
private[this] class Node[T](val value:T) { |
private[this] class Node[T](val value:T) { |
||
var next:Option[Node[T]]=None |
var next:Option[Node[T]]=None |
||
Line 5,825: | Line 5,825: | ||
override def toString()=iterator.mkString("Queue(", ", ", ")") |
override def toString()=iterator.mkString("Queue(", ", ", ")") |
||
}</ |
}</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang="scala">val q=new Queue[Int]() |
||
println("isEmpty = " + q.isEmpty) |
println("isEmpty = " + q.isEmpty) |
||
try{q dequeue} catch{case _:java.util.NoSuchElementException => println("dequeue(empty) failed.")} |
try{q dequeue} catch{case _:java.util.NoSuchElementException => println("dequeue(empty) failed.")} |
||
Line 5,837: | Line 5,837: | ||
println("dequeue = " + q.dequeue) |
println("dequeue = " + q.dequeue) |
||
println("dequeue = " + q.dequeue) |
println("dequeue = " + q.dequeue) |
||
println("isEmpty = " + q.isEmpty)</ |
println("isEmpty = " + q.isEmpty)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>isEmpty = true |
<pre>isEmpty = true |
||
Line 5,852: | Line 5,852: | ||
in the vector to hold tail pointer to avoid the append call. |
in the vector to hold tail pointer to avoid the append call. |
||
< |
<syntaxhighlight lang="scheme">(define (make-queue) |
||
(make-vector 1 '())) |
(make-vector 1 '())) |
||
Line 5,867: | Line 5,867: | ||
(vector-set! queue 0 (cdr (vector-ref queue 0))) |
(vector-set! queue 0 (cdr (vector-ref queue 0))) |
||
ret))) |
ret))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=== Message passing === |
=== Message passing === |
||
< |
<syntaxhighlight lang="scheme">(define (make-queue) |
||
(let ((q (cons '() '()))) |
(let ((q (cons '() '()))) |
||
(lambda (cmd . arg) |
(lambda (cmd . arg) |
||
Line 5,894: | Line 5,894: | ||
; 6 |
; 6 |
||
(q 'get) |
(q 'get) |
||
; empty</ |
; empty</syntaxhighlight> |
||
=={{header|SenseTalk}}== |
=={{header|SenseTalk}}== |
||
A queue in SenseTalk is implemented using push and pull operations on a list. |
A queue in SenseTalk is implemented using push and pull operations on a list. |
||
< |
<syntaxhighlight lang="sensetalk"> |
||
set myFoods to be an empty list |
set myFoods to be an empty list |
||
Line 5,916: | Line 5,916: | ||
put "The remaining foods are: " & myFoods |
put "The remaining foods are: " & myFoods |
||
end if |
end if |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output: |
Output: |
||
< |
<syntaxhighlight lang="sensetalk"> |
||
The foods in my queue are: (grapes,orange,apricot) |
The foods in my queue are: (grapes,orange,apricot) |
||
The first thing to eat is: grapes |
The first thing to eat is: grapes |
||
The remaining foods are: (orange,apricot) |
The remaining foods are: (orange,apricot) |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
Implemented as a class: |
Implemented as a class: |
||
< |
<syntaxhighlight lang="ruby">class FIFO(*array) { |
||
method pop { |
method pop { |
||
array.is_empty && die "underflow"; |
array.is_empty && die "underflow"; |
||
Line 5,938: | Line 5,938: | ||
array.len == 0; |
array.len == 0; |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Slate}}== |
=={{header|Slate}}== |
||
Toy code based on Slate's Queue standard library (which is optimized for FIFO access): |
Toy code based on Slate's Queue standard library (which is optimized for FIFO access): |
||
< |
<syntaxhighlight lang="slate">collections define: #Queue &parents: {ExtensibleArray}. |
||
q@(Queue traits) isEmpty [resend]. |
q@(Queue traits) isEmpty [resend]. |
||
Line 5,948: | Line 5,948: | ||
q@(Queue traits) pop [q removeFirst]. |
q@(Queue traits) pop [q removeFirst]. |
||
q@(Queue traits) pushAll: c [q addAllLast: c]. |
q@(Queue traits) pushAll: c [q addAllLast: c]. |
||
q@(Queue traits) pop: n [q removeFirst: n].</ |
q@(Queue traits) pop: n [q removeFirst: n].</syntaxhighlight> |
||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
Line 5,955: | Line 5,955: | ||
An OrderedCollection can be easily used as a FIFO queue. |
An OrderedCollection can be easily used as a FIFO queue. |
||
< |
<syntaxhighlight lang="smalltalk">OrderedCollection extend [ |
||
push: obj [ ^(self add: obj) ] |
push: obj [ ^(self add: obj) ] |
||
pop [ |
pop [ |
||
Line 5,974: | Line 5,974: | ||
f pop printNl. |
f pop printNl. |
||
f isEmpty printNl. |
f isEmpty printNl. |
||
f pop. "queue empty error"</ |
f pop. "queue empty error"</syntaxhighlight> |
||
=={{header|Standard ML}}== |
=={{header|Standard ML}}== |
||
Here is the signature for a basic queue: |
Here is the signature for a basic queue: |
||
<syntaxhighlight lang="standard ml"> |
|||
<lang Standard ML> |
|||
signature QUEUE = |
signature QUEUE = |
||
sig |
sig |
||
Line 5,991: | Line 5,991: | ||
val empty: 'a queue -> bool |
val empty: 'a queue -> bool |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</lang> |
|||
A very basic implementation of this signature backed by a list is as follows: |
A very basic implementation of this signature backed by a list is as follows: |
||
<syntaxhighlight lang="standard ml"> |
|||
<lang Standard ML> |
|||
structure Queue:> QUEUE = |
structure Queue:> QUEUE = |
||
struct |
struct |
||
Line 6,010: | Line 6,010: | ||
| empty _ = false |
| empty _ = false |
||
end; |
end; |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Stata}}== |
=={{header|Stata}}== |
||
Line 6,017: | Line 6,017: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
Here's a simple implementation using a list: |
Here's a simple implementation using a list: |
||
< |
<syntaxhighlight lang="tcl">proc push {stackvar value} { |
||
upvar 1 $stackvar stack |
upvar 1 $stackvar stack |
||
lappend stack $value |
lappend stack $value |
||
Line 6,047: | Line 6,047: | ||
peek Q ;# ==> foo |
peek Q ;# ==> foo |
||
pop Q ;# ==> foo |
pop Q ;# ==> foo |
||
peek Q ;# ==> bar</ |
peek Q ;# ==> bar</syntaxhighlight> |
||
{{tcllib|struct::queue}} |
{{tcllib|struct::queue}} |
||
< |
<syntaxhighlight lang="tcl">package require struct::queue |
||
struct::queue Q |
struct::queue Q |
||
Q size ;# ==> 0 |
Q size ;# ==> 0 |
||
Line 6,059: | Line 6,059: | ||
Q peek ;# ==> b |
Q peek ;# ==> b |
||
Q pop 4 ;# ==> b c d e |
Q pop 4 ;# ==> b c d e |
||
Q size ;# ==> 0</ |
Q size ;# ==> 0</syntaxhighlight> |
||
=={{header|UNIX Shell}}== |
=={{header|UNIX Shell}}== |
||
{{works with|ksh93}} |
{{works with|ksh93}} |
||
< |
<syntaxhighlight lang="bash">queue_push() { |
||
typeset -n q=$1 |
typeset -n q=$1 |
||
shift |
shift |
||
Line 6,087: | Line 6,087: | ||
typeset -n q=$1 |
typeset -n q=$1 |
||
print "${q[0]}" |
print "${q[0]}" |
||
}</ |
}</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang="bash"># any valid variable name can be used as a queue without initialization |
||
queue_empty foo && echo foo is empty || echo foo is not empty |
queue_empty foo && echo foo is empty || echo foo is not empty |
||
Line 6,103: | Line 6,103: | ||
print "peek: $(queue_peek foo)"; queue_pop foo |
print "peek: $(queue_peek foo)"; queue_pop foo |
||
print "peek: $(queue_peek foo)"; queue_pop foo |
print "peek: $(queue_peek foo)"; queue_pop foo |
||
print "peek: $(queue_peek foo)"; queue_pop foo</ |
print "peek: $(queue_peek foo)"; queue_pop foo</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,116: | Line 6,116: | ||
=={{header|UnixPipes}}== |
=={{header|UnixPipes}}== |
||
Uses moreutils |
Uses moreutils |
||
< |
<syntaxhighlight lang="bash">init() {echo > fifo} |
||
push() {echo $1 >> fifo } |
push() {echo $1 >> fifo } |
||
pop() {head -1 fifo ; (cat fifo | tail -n +2)|sponge fifo} |
pop() {head -1 fifo ; (cat fifo | tail -n +2)|sponge fifo} |
||
empty() {cat fifo | wc -l}</ |
empty() {cat fifo | wc -l}</syntaxhighlight> |
||
Usage: |
Usage: |
||
< |
<syntaxhighlight lang="bash">push me; push you; push us; push them |
||
|pop;pop;pop;pop |
|pop;pop;pop;pop |
||
me |
me |
||
you |
you |
||
us |
us |
||
them</ |
them</syntaxhighlight> |
||
=={{header|V}}== |
=={{header|V}}== |
||
V doesn't have mutable data. Below is an function interface for a fifo. |
V doesn't have mutable data. Below is an function interface for a fifo. |
||
< |
<syntaxhighlight lang="v">[fifo_create []]. |
||
[fifo_push swap cons]. |
[fifo_push swap cons]. |
||
[fifo_pop [[*rest a] : [*rest] a] view]. |
[fifo_pop [[*rest a] : [*rest] a] view]. |
||
[fifo_empty? dup empty?].</ |
[fifo_empty? dup empty?].</syntaxhighlight> |
||
Using it |
Using it |
||
< |
<syntaxhighlight lang="v">|fifo_create 3 fifo_push 4 fifo_push 5 fifo_push ?? |
||
=[5 4 3] |
=[5 4 3] |
||
|fifo_empty? puts |
|fifo_empty? puts |
||
Line 6,144: | Line 6,144: | ||
=3 4 5 |
=3 4 5 |
||
|fifo_empty? puts |
|fifo_empty? puts |
||
=true</ |
=true</syntaxhighlight> |
||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
< |
<syntaxhighlight lang="vb">Public queue As New Collection |
||
Private Sub push(what As Variant) |
Private Sub push(what As Variant) |
||
Line 6,165: | Line 6,165: | ||
Private Function empty_() |
Private Function empty_() |
||
empty_ = queue.Count = 0 |
empty_ = queue.Count = 0 |
||
End Function</ |
End Function</syntaxhighlight> |
||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
Using an ArrayList. |
Using an ArrayList. |
||
< |
<syntaxhighlight lang="vb">' Queue Definition - VBScript |
||
Option Explicit |
Option Explicit |
||
Dim queue, i, x |
Dim queue, i, x |
||
Line 6,206: | Line 6,206: | ||
empty_ = q.Count = 0 |
empty_ = q.Count = 0 |
||
End Function 'empty_ |
End Function 'empty_ |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 6,221: | Line 6,221: | ||
=={{header|Vlang}}== |
=={{header|Vlang}}== |
||
Updated to Vlang version 0.2.2 |
Updated to Vlang version 0.2.2 |
||
< |
<syntaxhighlight lang="vlang">const max_tail = 256 |
||
struct Queue<T> { |
struct Queue<T> { |
||
Line 6,272: | Line 6,272: | ||
queue.pop() or { return } |
queue.pop() or { return } |
||
queue.push(1.2) |
queue.push(1.2) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Queue is empty? Yes |
<pre>Queue is empty? Yes |
||
Line 6,286: | Line 6,286: | ||
=={{header|Wart}}== |
=={{header|Wart}}== |
||
Wart defines queues as lists with a pointer to the last element saved for constant-time enqueuing: |
Wart defines queues as lists with a pointer to the last element saved for constant-time enqueuing: |
||
< |
<syntaxhighlight lang="python">def (queue seq) |
||
(tag queue (list seq lastcons.seq len.seq)) |
(tag queue (list seq lastcons.seq len.seq)) |
||
Line 6,305: | Line 6,305: | ||
def (len q) :case (isa queue q) |
def (len q) :case (isa queue q) |
||
rep.q.2</ |
rep.q.2</syntaxhighlight> |
||
<code>empty?</code> relies on <code>len</code> by default, so there's no need to separately override it. |
<code>empty?</code> relies on <code>len</code> by default, so there's no need to separately override it. |
||
Line 6,312: | Line 6,312: | ||
{{libheader|Wren-queue}} |
{{libheader|Wren-queue}} |
||
The above module contains a suitable Queue class. |
The above module contains a suitable Queue class. |
||
< |
<syntaxhighlight lang="ecmascript">import "/queue" for Queue |
||
var q = Queue.new() |
var q = Queue.new() |
||
Line 6,320: | Line 6,320: | ||
} else { |
} else { |
||
System.print("'%(item)' was popped") |
System.print("'%(item)' was popped") |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 6,329: | Line 6,329: | ||
=={{header|XLISP}}== |
=={{header|XLISP}}== |
||
A queue is similar to a stack, except that values are pushed onto and popped from different "ends" of it (whereas in a stack it is the same end for both operations). This implementation is based on the XLISP implementation of a stack, therefore, but with a <tt>push</tt> method that appends a new value to the end rather than sticking it onto the front. Attempting to pop from an empty queue will return the empty list, equivalent to Boolean "false". |
A queue is similar to a stack, except that values are pushed onto and popped from different "ends" of it (whereas in a stack it is the same end for both operations). This implementation is based on the XLISP implementation of a stack, therefore, but with a <tt>push</tt> method that appends a new value to the end rather than sticking it onto the front. Attempting to pop from an empty queue will return the empty list, equivalent to Boolean "false". |
||
< |
<syntaxhighlight lang="lisp">(define-class queue |
||
(instance-variables vals)) |
(instance-variables vals)) |
||
Line 6,345: | Line 6,345: | ||
(define-method (queue 'emptyp) |
(define-method (queue 'emptyp) |
||
(null vals))</ |
(null vals))</syntaxhighlight> |
||
A sample REPL session: |
A sample REPL session: |
||
< |
<syntaxhighlight lang="lisp">[1] (define my-queue (queue 'new)) |
||
MY-QUEUE |
MY-QUEUE |
||
Line 6,370: | Line 6,370: | ||
[8] (my-queue 'pop) |
[8] (my-queue 'pop) |
||
()</ |
()</syntaxhighlight> |
||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">include c:\cxpl\codes; |
||
def Size=8; |
def Size=8; |
||
int Fifo(Size); |
int Fifo(Size); |
||
Line 6,420: | Line 6,420: | ||
ChOut(0, ChIn(8)); CrLf(0); \pop |
ChOut(0, ChIn(8)); CrLf(0); \pop |
||
ChOut(0, ChIn(8)); CrLf(0); \pop |
ChOut(0, ChIn(8)); CrLf(0); \pop |
||
]</ |
]</syntaxhighlight> |
||
Output: |
Output: |
||
Line 6,437: | Line 6,437: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
< |
<syntaxhighlight lang="zkl">class Queue{ |
||
var [const] q=List(); |
var [const] q=List(); |
||
fcn push { q.append(vm.pasteArgs()) } |
fcn push { q.append(vm.pasteArgs()) } |
||
fcn pop { q.pop(0) } |
fcn pop { q.pop(0) } |
||
fcn empty { q.len()==0 } |
fcn empty { q.len()==0 } |
||
}</ |
}</syntaxhighlight> |
||
< |
<syntaxhighlight lang="zkl">q:=Queue(); |
||
q.push(1,2,3); |
q.push(1,2,3); |
||
q.pop(); //-->1 |
q.pop(); //-->1 |
||
q.empty(); //-->False |
q.empty(); //-->False |
||
q.pop();q.pop();q.pop() //-->IndexError thrown</ |
q.pop();q.pop();q.pop() //-->IndexError thrown</syntaxhighlight> |