Stack: Difference between revisions
m
→{{header|Groovy}}
(→{{header|LOLCODE}}: Add implementation.) |
|||
(39 intermediate revisions by 22 users not shown) | |||
Line 44:
{{trans|Crystal}}
<
L(i) 1..10
Line 50:
L 10
print(stack.pop())</
{{out}}
Line 66:
</pre>
=={{header|6502 Assembly}}==
The 6502 has a built-in stack, which is located at memory addresses $0100-$01FF. The first thing most boot ROMs will do is set the stack to equal $FF. Only the X register can interact with the stack pointer's value directly, and it does so using <code>TSX</code> (transfer stack to X) and <code>TXS</code> (transfer X to stack.) Each push will decrement S by 1 and write that byte to the stack memory. On the original 6502, only the accumulator could be pushed to the stack, so programs running on those CPUs would often use sequences such as <code>TXA PHA</code> and <code>TYA PHA</code> to save the X and Y registers. This had the nasty habit of destroying the accumulator, which made saving these registers difficult. Fortunately, the 65c02 and its later revisions can push/pop X and Y directly without having to go through the accumulator first.
Push:
<syntaxhighlight lang
Pop:
<syntaxhighlight lang
Empty:
<
CPX $FF
BEQ stackEmpty</syntaxhighlight>
Peek:
<
LDA $0101,x</
=={{header|68000 Assembly}}==
Line 84 ⟶ 85:
===Push===
You can push the contents of one or more variables.
<
MOVEM.L D0-D3,-(A0) ;moves the full 32 bits of registers D0,D1,D2,D3 into the address pointed by A0, with pre-decrement</
Unlike the "true" stack (A7), you can push a single byte onto the user stack and it won't get automatically padded with a trailing null byte.
Line 91 ⟶ 92:
===Pop===
The pop is just a reverse push.
<
===Empty===
The stack is empty if and only if the stack pointer equals its initialized value. This is only true provided you have never adjusted the stack pointer except by pushing and popping.
<
BEQ StackIsEmpty</
===Manually adjusting the stack===
You can offset the user stack (and the real stack) as follows:
<
===Peek===
If you know the intended length of the last item on the stack (1, 2, or 4 bytes), you can load it into memory without popping it. This applies to both the real stack and a user stack you may have created. Since this operation doesn't alter the value of the stack pointer, you don't have to worry about misaligning the stack, but the value you peek at should be of the correct size or you'll be "peeking" at more than one item at the same time.
<
MOVE.W (A0),D0 ;load the top two bytes of A0 into D0</
=={{header|8086 Assembly}}==
The 8086's hardware stack is very similar to that of [[Z80 Assembly]]. This is no coincidence, as the Z80 was based on the predecessor to the 8086.
<syntaxhighlight lang="asm">push ax ;push ax onto the stack
pop ax ; pop the top two bytes of the stack into ax</syntaxhighlight>
The "high" byte is pushed first, then the low byte. Popping does the opposite.
Depending on your assembler, the stack's initial value may be set using the <code>.stack</code> directive.
Like the Z80, the 8086 can only push or pop 2 bytes at a time. It's not possible to push <code>AH</code> without pushing <code>AL</code> alongside it. The stack can be used to exchange values of registers that even the <code>XCHG</code> command can't work with. This is done by deliberately pushing two registers and popping them in the "wrong" order.
The easiest way to "peek" is to pop then push that same register again.
<syntaxhighlight lang="asm">;get the top item of the stack
pop ax
push ax</syntaxhighlight>
The stack need not be accessed using these push and pop commands, it can also be read like any other area of memory. This is actually how [[C]] programs store and recall local variables and function arguments.
=={{header|ABAP}}==
Line 112 ⟶ 133:
This works for ABAP Version 7.40 and above
<syntaxhighlight lang="abap">
report z_stack.
Line 318 ⟶ 339:
stack3->pop( ).
write: |pop -> Stack3 = { stack3->stringify( ) }|, /, /.
</syntaxhighlight>
{{out}}
Line 339 ⟶ 360:
pop -> Stack3 = empty
</pre>
=={{header|Action!}}==
===Static memory===
<syntaxhighlight lang="action!">DEFINE MAXSIZE="200"
BYTE ARRAY stack(MAXSIZE)
BYTE stacksize=[0]
BYTE FUNC IsEmpty()
IF stacksize=0 THEN
RETURN (1)
FI
RETURN (0)
PROC Push(BYTE v)
IF stacksize=maxsize THEN
PrintE("Error: stack is full!")
Break()
FI
stack(stacksize)=v
stacksize==+1
RETURN
BYTE FUNC Pop()
IF IsEmpty() THEN
PrintE("Error: stack is empty!")
Break()
FI
stacksize==-1
RETURN (stack(stacksize))
PROC TestIsEmpty()
IF IsEmpty() THEN
PrintE("Stack is empty")
ELSE
PrintE("Stack is not empty")
FI
RETURN
PROC TestPush(BYTE v)
PrintF("Push: %B%E",v)
Push(v)
RETURN
PROC TestPop()
BYTE v
Print("Pop: ")
v=Pop()
PrintBE(v)
RETURN
PROC Main()
TestIsEmpty()
TestPush(10)
TestIsEmpty()
TestPush(31)
TestPop()
TestIsEmpty()
TestPush(5)
TestPop()
TestPop()
TestPop()
RETURN</syntaxhighlight>
===Dynamic memory===
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}}
<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!
DEFINE PTR="CARD"
DEFINE NODE_SIZE="3"
TYPE StackNode=[BYTE data PTR nxt]
StackNode POINTER stack
BYTE FUNC IsEmpty()
IF stack=0 THEN
RETURN (1)
FI
RETURN (0)
PROC Push(BYTE v)
StackNode POINTER node
node=Alloc(NODE_SIZE)
node.data=v
node.nxt=stack
stack=node
RETURN
BYTE FUNC Pop()
StackNode POINTER node
BYTE v
IF IsEmpty() THEN
PrintE("Error stack is empty!")
Break()
FI
node=stack
v=node.data
stack=node.nxt
Free(node,NODE_SIZE)
RETURN (v)
PROC TestIsEmpty()
IF IsEmpty() THEN
PrintE("Stack is empty")
ELSE
PrintE("Stack is not empty")
FI
RETURN
PROC TestPush(BYTE v)
PrintF("Push: %B%E",v)
Push(v)
RETURN
PROC TestPop()
BYTE v
Print("Pop: ")
v=Pop()
PrintBE(v)
RETURN
PROC Main()
AllocInit(0)
stack=0
Put(125) PutE() ;clear screen
TestIsEmpty()
TestPush(10)
TestIsEmpty()
TestPush(31)
TestPop()
TestIsEmpty()
TestPush(5)
TestPop()
TestPop()
TestPop()
RETURN</syntaxhighlight>
{{out}}
Error at the end of program is intentional.
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Stack_array.png Screenshot from Atari 8-bit computer]
<pre>
Stack is empty
Push: 10
Stack is not empty
Push: 31
Pop: 31
Stack is not empty
Push: 5
Pop: 5
Pop: 10
Pop: Error: stack is empty!
RETURN
Error: 128
</pre>
=={{header|ActionScript}}==
In ActionScript an Array object provides stack functionality.
<
stack.push(1);
stack.push(2);
trace(stack.pop()); // outputs "2"
trace(stack.pop()); // outputs "1"</
=={{header|Ada}}==
This is a generic stack implementation.
<
type Element_Type is private;
package Generic_Stack is
Line 366 ⟶ 551:
Next : Stack := null;
end record;
end Generic_Stack;</
<
package body Generic_Stack is
Line 408 ⟶ 593:
end Pop;
end Generic_Stack;</
=={{header|ALGOL 68}}==
Line 417 ⟶ 602:
{{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''.}}
'''File: prelude/next_link.a68'''<
CO REQUIRES:
MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked #
Line 431 ⟶ 616:
PROC obj nextlink free = (REF OBJNEXTLINK free)VOID:
next OF free := obj stack empty # give the garbage collector a BIG hint #</
CO REQUIRES:
MODE OBJNEXTLINK = STRUCT(
Line 487 ⟶ 672:
self IS obj stack empty;
SKIP</
MODE DIETITEM = STRUCT(
STRING food, annual quantity, units, REAL cost
Line 501 ⟶ 686:
("Wheat Flour", "370","lb.", 13.33),
("Total Annual Cost", "","", 39.93)
)</
# -*- coding: utf-8 -*- #
Line 520 ⟶ 705:
# OR example stack ISNT obj stack empty #
printf((diet item fmt, obj stack pop(example stack), $l$))
OD</
{{out}}
<pre>
Line 534 ⟶ 719:
===ALGOL 68: Using FLEX array===
An alternative to using a linked list is to use a FLEX array.
<
MODE DIETITEM = STRUCT (
STRING food, annual quantity, units, REAL cost
Line 580 ⟶ 765:
printf((diet item fmt, POP example stack, $l$))
OD
</syntaxhighlight>
{{out}}
<pre>
Line 593 ⟶ 778:
=={{header|ALGOL W}}==
<
% define a Stack type that will hold StringStackElements %
% and the StringStackElement type %
Line 640 ⟶ 825:
)
end
end.</
{{out}}
<pre>
Line 650 ⟶ 835:
=={{header|Applesoft BASIC}}==
<
110 DATA "(2*A)","PI","","TO BE OR","NOT TO BE"
120 FOR I = 1 TO 5
Line 689 ⟶ 874:
730 LET EMPTY = SP = 0
740 RETURN
</syntaxhighlight>
{{out}}
Line 702 ⟶ 887:
=={{header|ARM Assembly}}==
The stack is held in register
Pushing and popping multiple values is very similar to [[68000 Assembly]].
<
LDMFD sp!,{r0-r12,pc} ;pop r0 thru r12, and the value that was in the link register is put into the program counter.
;This acts as a pop and return command all-in-one. (Most programs use bx lr to return.)</
Like in 68000 Assembly, you are not limited to using <code>SP</code> as the source/destination for these commands; any register can fulfill that role. If you wish to have multiple stacks, then so be it.
The stack pointer will work with any operation the other registers can. As such, a peek can be done by using an <code>LDR</code> with the stack pointer as the address register:
<syntaxhighlight lang="arm assembly">LDR r0,[sp] ;load the top of the stack into r0</syntaxhighlight>
The order in which registers are pushed/popped is always the same, no matter which order you list the registers in your source code. If you want to push some registers and purposefully pop them into different registers, you'll need to push/pop them separately.
A check if the stack is empty is also very simple, provided the initial value of the stack pointer was saved at the start of the program, or (more likely) was loaded from a nearby memory location.
<syntaxhighlight lang="arm assembly">;this example uses VASM syntax which considers a "word" to be 16-bit regardless of the architecture
InitStackPointer: .long 0x3FFFFFFF ;other assemblers would call this a "word"
MOV R1,#InitStackPointer
LDR SP,[R1] ;set up the stack pointer
LDR R2,[R1] ;also load it into R2
;There's no point in checking since we haven't pushed/popped anything but just for demonstration purposes we'll check now
CMP SP,R2
BEQ StackIsEmpty</syntaxhighlight>
In THUMB mode, the <code>PUSH</code> and <code>POP</code> commands replace <code>STMFD</code> and <code>LDMFD</code>. They work in a similar fashion, but are limited to just the stack unlike the real <code>STMFD</code> and <code>LDMFD</code> commands which can use any register as the "stack pointer."
=={{header|Arturo}}==
<
pushTo: function [st val]-> 'st ++ val
Line 732 ⟶ 939:
emptyStack st
print ["finally:" st]</
{{out}}
Line 740 ⟶ 947:
one two
finally: []</pre>
=={{header|ATS}}==
<syntaxhighlight lang="ats">(* Stacks implemented as linked lists. *)
(* A nonlinear stack type of size n, which is good for when you are
using a garbage collector or can let the memory leak. *)
typedef stack_t (t : t@ype+, n : int) = list (t, n)
typedef stack_t (t : t@ype+) = [n : int] stack_t (t, n)
(* A linear stack type of size n, which requires (and will enforce)
explicit freeing. (Note that a "peek" function for a linear stack
is a complicated topic. But the task avoids this issue.) *)
viewtypedef stack_vt (vt : vt@ype+, n : int) = list_vt (vt, n)
viewtypedef stack_vt (vt : vt@ype+) = [n : int] stack_vt (vt, n)
(* Proof that a given nonlinear stack does not have a nonnegative
size. *)
prfn
lemma_stack_t_param {n : int} {t : t@ype}
(stack : stack_t (t, n)) :<prf>
[0 <= n] void =
lemma_list_param stack
(* Proof that a given linear stack does not have a nonnegative
size. *)
prfn
lemma_stack_vt_param {n : int} {vt : vt@ype}
(stack : !stack_vt (vt, n)) :<prf>
[0 <= n] void =
lemma_list_vt_param stack
(* Create an empty nonlinear stack. *)
fn {}
stack_t_nil {t : t@ype} () :<> stack_t (t, 0) =
list_nil ()
(* Create an empty linear stack. *)
fn {}
stack_vt_nil {vt : vt@ype} () :<> stack_vt (vt, 0) =
list_vt_nil ()
(* Is a nonlinear stack empty? *)
fn {}
stack_t_is_empty {n : int} {t : t@ype}
(stack : stack_t (t, n)) :<>
[empty : bool | empty == (n == 0)]
bool empty =
case+ stack of
| list_nil _ => true
| list_cons _ => false
(* Is a linear stack empty? *)
fn {}
stack_vt_is_empty {n : int} {vt : vt@ype}
(* ! = pass by value; stack is preserved. *)
(stack : !stack_vt (vt, n)) :<>
[empty : bool | empty == (n == 0)]
bool empty =
case+ stack of
| list_vt_nil _ => true
| list_vt_cons _ => false
(* Push to a nonlinear stack that is stored in a variable. *)
fn {t : t@ype}
stack_t_push {n : int}
(stack : &stack_t (t, n) >> stack_t (t, m),
x : t) :<!wrt>
(* It is proved that the stack is raised one higher. *)
#[m : int | 1 <= m; m == n + 1]
void =
let
prval _ = lemma_stack_t_param stack
prval _ = prop_verify {0 <= n} ()
in
stack := list_cons (x, stack)
end
(* Push to a linear stack that is stored in a variable. Beware: if x
is linear, it is consumed. *)
fn {vt : vt@ype}
stack_vt_push {n : int}
(stack : &stack_vt (vt, n) >> stack_vt (vt, m),
x : vt) :<!wrt>
(* It is proved that the stack is raised one higher. *)
#[m : int | 1 <= m; m == n + 1]
void =
let
prval _ = lemma_stack_vt_param stack
prval _ = prop_verify {0 <= n} ()
in
stack := list_vt_cons (x, stack)
end
(* Pop from a nonlinear stack that is stored in a variable. It is
impossible (unless you cheat the typechecker) to pop from an empty
stack. *)
fn {t : t@ype}
stack_t_pop {n : int | 1 <= n}
(stack : &stack_t (t, n) >> stack_t (t, m)) :<!wrt>
(* It is proved that the stack is lowered by one. *)
#[m : int | m == n - 1]
t =
case+ stack of
| list_cons (x, tail) =>
begin
stack := tail;
x
end
(* Pop from a linear stack that is stored in a variable. It is
impossible (unless you cheat the typechecker) to pop from an empty
stack. *)
fn {vt : vt@ype}
stack_vt_pop {n : int | 1 <= n}
(stack : &stack_vt (vt, n) >> stack_vt (vt, m)) :<!wrt>
(* It is proved that the stack is lowered by one. *)
#[m : int | m == n - 1]
vt =
case+ stack of
| ~ list_vt_cons (x, tail) => (* ~ = the top node is consumed. *)
begin
stack := tail;
x
end
(* A linear stack has to be consumed. *)
extern fun {vt : vt@ype}
stack_vt_free$element_free (x : vt) :<> void
fn {vt : vt@ype}
stack_vt_free {n : int}
(stack : stack_vt (vt, n)) :<> void =
let
fun
loop {m : int | 0 <= m}
.<m>. (* <-- proof of loop termination *)
(stk : stack_vt (vt, m)) :<> void =
case+ stk of
| ~ list_vt_nil () => begin end
| ~ list_vt_cons (x, tail) =>
begin
stack_vt_free$element_free x;
loop tail
end
prval _ = lemma_stack_vt_param stack
in
loop stack
end
implement
main0 () =
let
var nonlinear_stack : stack_t (int) = stack_t_nil ()
var linear_stack : stack_vt (int) = stack_vt_nil ()
implement stack_vt_free$element_free<int> x = begin end
overload is_empty with stack_t_is_empty
overload is_empty with stack_vt_is_empty
overload push with stack_t_push
overload push with stack_vt_push
overload pop with stack_t_pop
overload pop with stack_vt_pop
in
println! ("nonlinear_stack is empty? ", is_empty nonlinear_stack);
println! ("linear_stack is empty? ", is_empty linear_stack);
println! ("pushing 3, 2, 1...");
push (nonlinear_stack, 3);
push (nonlinear_stack, 2);
push (nonlinear_stack, 1);
push (linear_stack, 3);
push (linear_stack, 2);
push (linear_stack, 1);
println! ("nonlinear_stack is empty? ", is_empty nonlinear_stack);
println! ("linear_stack is empty? ", is_empty linear_stack);
println! ("popping nonlinear_stack: ", (pop nonlinear_stack) : int);
println! ("popping nonlinear_stack: ", (pop nonlinear_stack) : int);
println! ("popping nonlinear_stack: ", (pop nonlinear_stack) : int);
println! ("popping linear_stack: ", (pop linear_stack) : int);
println! ("popping linear_stack: ", (pop linear_stack) : int);
println! ("popping linear_stack: ", (pop linear_stack) : int);
println! ("nonlinear_stack is empty? ", is_empty nonlinear_stack);
println! ("linear_stack is empty? ", is_empty linear_stack);
stack_vt_free<int> linear_stack
end</syntaxhighlight>
{{out}}
<pre>$ patscc -O2 -DATS_MEMALLOC_LIBC stack-postiats.dats && ./a.out
nonlinear_stack is empty? true
linear_stack is empty? true
pushing 3, 2, 1...
nonlinear_stack is empty? false
linear_stack is empty? false
popping nonlinear_stack: 1
popping nonlinear_stack: 2
popping nonlinear_stack: 3
popping linear_stack: 1
popping linear_stack: 2
popping linear_stack: 3
nonlinear_stack is empty? true
linear_stack is empty? true</pre>
=={{header|AutoHotkey}}==
<
msgbox % stack("push", 5)
msgbox % stack("peek")
Line 780 ⟶ 1,195:
return 0
}
}</
=={{header|AWK}}==
<
arr["start"] = 0
arr["end"] = 0
Line 844 ⟶ 1,259:
}
printdeque(q)
}</
=={{header|Axe}}==
<
Lbl PUSH
r₁→{L₁+S}ʳ
Line 861 ⟶ 1,276:
Lbl EMPTY
S≤≤0
Return</
=={{header|Babel}}==
<
{ (1 2 3) foo set -- foo = (1 2 3)
4 foo push -- foo = (1 2 3 4)
Line 881 ⟶ 1,296:
"empty" .
cr << }
</syntaxhighlight>
{{out}}
<pre>
Line 889 ⟶ 1,304:
=={{header|Batch File}}==
This implementation uses an environment variable naming convention to implement a stack as a pseudo object containing a pseudo dynamic array and top attribute, as well as an empty "method" that is a sort of macro. The implementation depends on delayed expansion being enabled at the time of each call to a stack function. More complex variations can be written that remove this limitation.
<
setlocal enableDelayedExpansion
Line 957 ⟶ 1,372:
if !%~1.top! equ 0 exit /b 1
for %%N in (!%~1.top!) do set %~2=!%~1.%%N!
exit /b 0</
=={{header|
==={{header|BBC BASIC}}===
{{works with|BBC BASIC for Windows}}
<
FOR n = 3 TO 5
Line 991 ⟶ 1,407:
= (sptr% = 0)
ENDCASE
ENDPROC</
{{out}}
<pre>
Line 1,046 ⟶ 1,462:
<pre>*Ag'{`gstack empty, no value to return`</pre>
This method returns the top value of gstack only if gstack is not empty, otherwise it outputs <code>gstack empty, no value to return</code> to STDOUT.
=={{header|BQN}}==
Representing the stack as an array, pushing is appending, popping is removing the last element, and checking emptiness is checking the length.
<syntaxhighlight lang="bqn"> Push ← ∾
∾
Pop ← ¯1⊸↓
¯1⊸↓
Empty ← 0=≠
0=≠
1‿2‿3 Push 4
⟨ 1 2 3 4 ⟩
Pop 1‿2‿3
⟨ 1 2 ⟩
Empty 1‿2‿3
0
Empty ⟨⟩
1</syntaxhighlight>
=={{header|Bracmat}}==
A stack is easiest implemented as a dotted list <code>top.top-1.top-2.<i>[...]</i>.</code>. In the example below we also introduce a 'class' <code>stack</code>, instantiated in the 'object' <code>Stack</code>. The class has a member variable <code>S</code> and methods <code>push</code>,<code>pop</code>, <code>top</code> and <code>empty</code>. As a side note, <code>.</code> is to <code>..</code> as C's <code>.</code> is to <code>-></code>. In a method's body, <code>its</code> refers to the object itself. (Analogous to <code>(*this)</code> in C++.)
<
= (S=)
(push=.(!arg.!(its.S)):?(its.S))
Line 1,080 ⟶ 1,514:
)
&
);</
{{out}}
<pre>not to be
Line 1,095 ⟶ 1,529:
Built in arrays have push, pop, and empty? methods:
<
stack.push 1
stack.push 2
stack.push 3
until { stack.empty? } { p stack.pop }</
{{out}}
Line 1,109 ⟶ 1,543:
=={{header|C}}==
Macro expanding to type flexible stack routines.
<
#include <stdlib.h>
Line 1,170 ⟶ 1,604:
stk_int_delete(stk);
return 0;
}</
===Or===
<
#include <stdlib.h>
#include <stddef.h>
Line 1,242 ⟶ 1,676:
s->bottom = realloc(s->bottom, new_size);
check_pointer(s->bottom);
s->allocated_top = s->bottom + qtty - 1;}</
=={{header|C sharp|C#}}==
<
System.Collections.Stack stack = new System.Collections.Stack();
stack.Push( obj );
Line 1,257 ⟶ 1,691:
bool isEmpty = stack.Count == 0;
Foo top = stack.Peek(); // Peek without Popping.
top = stack.Pop();</
=={{header|C++}}==
{{libheader|STL}}
The C++ standard library already provides a ready-made stack class. You get it by writing
<syntaxhighlight lang
and then using the <tt>std::stack</tt> class.
An example of an explicit implementation of a stack class (which actually implements the standard stack class, except that the standard one is in namespace std):
<
template <class T, class Sequence = std::deque<T> >
class stack {
Line 1,320 ⟶ 1,754:
{
return !(x < y);
}</
=={{header|Clojure}}==
As is mentioned in the Common Lisp example below, built in cons-based lists work just fine. In this implementation, the list is wrapped in a datatype, providing a stateful solution.
<
(def stack (Stack (ref ())))
Line 1,343 ⟶ 1,777:
(defn empty-stack?
"Tests whether or not the stack is empty."
[] (= () (deref (:elements stack))))</
We can make this a bit smaller and general by using defprotocol along with deftype. Here is a revised version using defprotocol.
<
(push-stack [this x] "Pushes an item to the top of the stack.")
(pop-stack [this] "Pops an item from the top of the stack.")
Line 1,360 ⟶ 1,794:
(empty-stack? [] (= () (deref elements))))
(def stack (Stack (ref ())))</
=={{header|CLU}}==
<syntaxhighlight lang="clu">% Stack
stack = cluster [T: type] is new, push, pop, peek, empty
rep = array[T]
new = proc () returns (cvt)
return (rep$new())
end new
empty = proc (s: cvt) returns (bool)
return (rep$size(s) = 0)
end empty;
push = proc (s: cvt, val: T)
rep$addh(s, val)
end push;
pop = proc (s: cvt) returns (T) signals (empty)
if rep$empty(s)
then signal empty
else return(rep$remh(s))
end
end pop
peek = proc (s: cvt) returns (T) signals (empty)
if rep$empty(s)
then signal empty
else return(s[rep$high(s)])
end
end peek
end stack
start_up = proc ()
po: stream := stream$primary_output()
% Make a stack
s: stack[int] := stack[int]$new()
% Push 1..10 onto the stack
for i: int in int$from_to(1, 10) do
stack[int]$push(s, i)
end
% Pop items off the stack until the stack is empty
while ~stack[int]$empty(s) do
stream$putl(po, int$unparse(stack[int]$pop(s)))
end
% Trying to pop off the stack now should raise 'empty'
begin
i: int := stack[int]$pop(s)
stream$putl(po, "Still here! And I got: " || int$unparse(i))
end except when empty:
stream$putl(po, "The stack is empty.")
end
end start_up</syntaxhighlight>
{{out}}
<pre>10
9
8
7
6
5
4
3
2
1
The stack is empty.</pre>
=={{header|COBOL}}==
Line 1,371 ⟶ 1,874:
stack.cbl
<
05 head USAGE IS POINTER VALUE NULL.
</syntaxhighlight>
node.cbl
<
COPY node-info REPLACING
01 BY 05
node-info BY info.
05 link USAGE IS POINTER VALUE NULL.
</syntaxhighlight>
node-info.cbl
<
</syntaxhighlight>
p.cbl
<
88 nil VALUE ZERO WHEN SET TO FALSE IS 1.
88 t VALUE 1 WHEN SET TO FALSE IS ZERO.
</syntaxhighlight>
stack-utilities.cbl
<
PROGRAM-ID. push.
DATA DIVISION.
Line 1,641 ⟶ 2,144:
GOBACK.
END PROGRAM traverse-stack.
</syntaxhighlight>
stack-test.cbl
<
PROGRAM-ID. stack-test.
DATA DIVISION.
Line 1,681 ⟶ 2,184:
COPY stack-utilities.
</syntaxhighlight>
{{out}}
Line 1,711 ⟶ 2,214:
=={{header|CoffeeScript}}==
<
stack.push 1
stack.push 2
console.log stack
console.log stack.pop()
console.log stack</
=={{header|Common Lisp}}==
It's a bit unusual to write a wrapper for a stack in Common Lisp; built-in cons-based lists work just fine. Nonetheless, here's an implementation where the list is wrapped in a structure, providing a stateful solution.
<
elements)
Line 1,735 ⟶ 2,238:
(defun stack-peek (stack)
(stack-top stack))</
=={{header|Component Pascal}}==
Works with BlackBox Component Builder
<
MODULE Stacks;
IMPORT StdLog;
Line 1,850 ⟶ 2,353:
END Stacks.
</syntaxhighlight>
Execute: ^Q Stacks.TestStack<br/>
Line 1,861 ⟶ 2,364:
=={{header|Crystal}}==
<
(1..10).each do |x|
stack.push x
Line 1,868 ⟶ 2,371:
10.times do
puts stack.pop
end</
'''Output:'''
Line 1,887 ⟶ 2,390:
=={{header|D}}==
Generic stack class implemented with a dynamic array.
<
class Stack(T) {
Line 1,912 ⟶ 2,415:
assert(s.pop() == 10);
assert(s.empty());
}</
=={{header|Delphi}}==
<
{$APPTYPE CONSOLE}
Line 1,938 ⟶ 2,441:
lStack.Free;
end;
end.</
=={{header|DWScript}}==
Dynamic arrays have pseudo-methods that allow to treat them as a stack.
<syntaxhighlight lang="delphi">
var stack: array of Integer;
Line 1,954 ⟶ 2,457:
Assert(stack.Length = 0); // assert empty
</syntaxhighlight>
=={{header|Dyalect}}==
Line 1,960 ⟶ 2,463:
{{trans|Swift}}
<syntaxhighlight lang
var
}
func Stack.
func Stack.
var e = this!xs[this!xs.Length() - 1]
this!xs.RemoveAt(this!xs.Length() - 1)
return e
}
func Stack.
var stack = Stack()
stack.
stack.
print(stack.
print(stack.
stack.
print(stack.
{{out}}
Line 1,995 ⟶ 2,494:
=={{header|Déjà Vu}}==
<
push-to stack 1
Line 2,006 ⟶ 2,505:
if stack: #empty lists are falsy
error #this stack should be empty now!</
=={{header|Diego}}==
Diego has a <code>stack</code> object and posit:
<syntaxhighlight lang="diego">set_ns(rosettacode)_me();
add_stack({int},a)_values(1..4); // 1,2,3,4 (1 is first/bottom, 4 is last/top)
with_stack(a)_pop(); // 1,2,3
with_stack(a)_push()_v(5,6); // 1,2,3,5,6
add_var({int},b)_value(7);
with_stack(a)_push[b]; // 1,2,3,5,6,7
with_stack(a)_pluck()_at(2); // callee will return `with_stack(a)_err(pluck invalid with stack);`
me_msg()_stack(a)_top(); // "7"
me_msg()_stack(a)_last(); // "7"
me_msg()_stack(a)_peek(); // "7"
me_msg()_stack(a)_bottom(); // "1"
me_msg()_stack(a)_first(); // "1"
me_msg()_stack(a)_peer(); // "1"
me_msg()_stack(a)_isempty(); // "false"
with_stack(a)_empty();
with_stack(a)_msg()_isempty()_me(); // "true" (alternative syntax)
me_msg()_stack(a)_history()_all(); // returns th entire history of stack 'a' since its creation
reset_ns[];</syntaxhighlight>
<code>stack</code> is a derivative of <code>array</code>, so arrays can also be used as stacks.
=={{header|E}}==
The standard FlexList data structure provides operations for use as a stack.
<
# value: [].diverge()
Line 2,031 ⟶ 2,560:
? l.size().aboveZero()
# value: false</
Here's a stack implemented out of a reference to a linked list:
<
var store := null
def stack {
Line 2,062 ⟶ 2,591:
? s.empty()
# value: true</
=={{header|EasyLang}}==
<syntaxhighlight>
stack[] = [ ]
proc push v . .
stack[] &= v
.
func pop .
lng = len stack[]
if lng = 0
return 0
.
r = stack[lng]
len stack[] -1
return r
.
func empty .
return if len stack[] = 0
.
push 2
push 11
push 34
while empty = 0
print pop
.
</syntaxhighlight>
=={{header|EchoLisp}}==
Named stacks are native objects. The following demonstrates the available operations :
<
; build stack [0 1 ... 9 (top)] from a list
(list->stack (iota 10) 'my-stack)
Line 2,087 ⟶ 2,642:
⛔ error: #|user| : unbound variable : my-stack
(stack-top 'my-stack) → 7
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
STACK_ON_ARRAY
Line 2,134 ⟶ 2,689:
end
</syntaxhighlight>
=={{header|Elena}}==
<
{
var stack := new system'collections'Stack();
stack.push
var isEmpty := stack.Length == 0;
Line 2,148 ⟶ 2,703:
item := stack.pop()
}</
=={{header|Elisa}}==
This is a generic Stack component based on arrays. See how in Elisa [http://jklunder.home.xs4all.nl/elisa/part01/doc120.html generic components] are defined.
<
type Stack;
Stack (MaxSize = integer) -> Stack;
Line 2,172 ⟶ 2,727:
stack.index:=stack.index - 1;
stack.area[stack.index + 1] ];
end component GenericStack;</
Another example of a generic Stack component is based on an unlimited sequence. A sequence is a uni-directional list. See how Elisa defines [http://jklunder.home.xs4all.nl/elisa/part02/doc010.html sequences]. The component has the same interface as the array based version.
<
type Stack;
Stack(MaxSize = integer) -> Stack;
Line 2,198 ⟶ 2,753:
Pull ( stack ) = [ exception (Empty (stack), "Stack Underflow");
Head = head(stack.list); stack.list:=tail(stack.list); Head];
end component GenericStack;</
Both versions give the same answers to the following tests:
<
type Book = text;
BookStack = StackofBooks(50);
Line 2,214 ⟶ 2,769:
Pull (BookStack)?
***** Exception: Stack Underflow</
=={{header|Elixir}}==
{{trans|Erlang}}
<
def new, do: []
Line 2,229 ⟶ 2,784:
def top([h|_]), do: h
end</
Example:
Line 2,249 ⟶ 2,804:
=={{header|Erlang}}==
Erlang has no built-in stack, but its lists behave basically the same way. A stack module can be implemented as a simple wrapper around lists:
<
-export([empty/1, new/0, pop/1, push/2, top/1]).
Line 2,261 ⟶ 2,816:
push(H,T) -> [H|T].
top([H|_]) -> H.</
Note that as Erlang doesn't have mutable data structure (destructive updates), pop returns the popped element and the new stack as a tuple.
The module is tested this way:
<
{ok,stack}
2> Stack = stack:new().
Line 2,278 ⟶ 2,833:
false
7> stack:empty(stack:new()).
true</
=={{header|F_Sharp|F#}}==
Line 2,284 ⟶ 2,839:
A list-based immutable stack type could be implemented like this:
<
(?items) =
let items = defaultArg items []
Line 2,303 ⟶ 2,858:
let (x, stack3) = stack2.Pop()
printfn "%d" x
printfn "%A" (stack3.IsEmpty())</
=={{header|Factor}}==
Factor is a stack based language, but also provides stack "objects", because
all resizable sequences can be treated as stacks (see [http://docs.factorcode.org/content/article-sequences-stacks.html docs]). Typically, a vector is used:
<
[ 6 swap push ]
[ "hi" swap push ]
Line 2,319 ⟶ 2,874:
Let's pop it: "hi"
Vector is now: V{ 1 2 3 6 }
Top is: 6</
=={{header|Forth}}==
<
create here cell+ , cells allot ;
Line 2,336 ⟶ 2,891:
st empty? . \ 0 (false)
st pop . st pop . st pop . \ 3 2 1
st empty? . \ -1 (true)</
=={{header|Fortran}}==
This solution can easily be adapted to data types other than floating point numbers.
<
implicit none
Line 2,450 ⟶ 3,005:
end do
call my_stack%clearStack()
end program main</
=={{header|Free Pascal}}==
===Delphi adaptation===
Example taken and adapted from the Delphi entry.
<
{$IFDEF FPC}{$MODE DELPHI}{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}{$ENDIF}
{$ASSERTIONS ON}
Line 2,476 ⟶ 3,032:
lStack.Free;
end;
end.</
<pre>
Output:
3 2 1
</pre>
===Object version from scratch===
{{works with|Free Pascal|version 3.2.0 }}
<syntaxhighlight lang="pascal">
PROGRAM StackObject.pas;
{$IFDEF FPC}
Line 2,505 ⟶ 3,062:
What happens after retrieving the variable is TBD by you.
https://www.freepascal.org/advantage.var
(*)
Line 2,643 ⟶ 3,201:
END.
</
Output:
Line 2,675 ⟶ 3,233:
=={{header|FreeBASIC}}==
We first use a macro to define a generic Stack type :
<
' stack_rosetta.bi
Line 2,759 ⟶ 3,317:
End Function
#EndMacro</
We now use this type to create a Stack of Dog instances :
<
#Include "stack_rosetta.bi"
Line 2,810 ⟶ 3,368:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 2,823 ⟶ 3,381:
Is stack empty now : false
</pre>
=={{header|Frink}}==
Frink's <CODE>array</CODE> class has all of the methods to make it usable as a stack or a deque. The methods are called <CODE><I>array</I>.push[<I>x</I>]</CODE>, <CODE><I>array</I>.pop[]</CODE>, and <CODE><I>array</I>.isEmpty[]</CODE>
<syntaxhighlight lang="frink">a = new array
a.push[1]
a.push[2]
a.peek[]
while ! a.isEmpty[]
println[a.pop[]]</syntaxhighlight>
=={{header|Genie}}==
<
/*
Stack, in Genie, with GLib double ended Queues
Line 2,844 ⟶ 3,411:
print "stack size before clear: " + stack.get_length().to_string()
stack.clear()
print "After clear, stack.is_empty(): " + stack.is_empty().to_string()</
{{out}}
Line 2,856 ⟶ 3,423:
=={{header|Go}}==
Go slices make excellent stacks without defining any extra types, functions, or methods. For example, to keep a stack of integers, simply declare one as,
<syntaxhighlight lang
Use the built in append function to push numbers on the stack:
<
Use a slice expression with the built in len function to pop from the stack:
<
The test for an empty stack:
<
And to peek at the top of the stack:
<syntaxhighlight lang
It is idiomatic Go to use primitive language features where they are sufficient, and define helper functions or types and methods only as they make sense for a particular situation. Below is an example using a type with methods and idiomatic "ok" return values to avoid panics. It is only an example of something that might make sense in some situation.
<
import "fmt"
Line 2,918 ⟶ 3,485:
fmt.Println("nothing to pop")
}
}</
{{out}}
<pre>
Line 2,928 ⟶ 3,495:
top value: four
four popped. stack: [3]
</pre>
=={{header|GDScript}}==
In GDScript there is built-in Array class, that implements either 'push', 'pop', 'top' and 'empty' methods. Method names are:
<ul>
<li>push -> push_back</li>
<li>pop -> pop_back</li>
<li>top -> back</li>
<li>empty -> is_empty</li>
</ul>
<syntaxhighlight lang="gdscript">
extends Node2D
func _ready() -> void:
# Empty stack creation.
var stack : Array = []
# In Godot 4.2.1 nothing happens here.
stack.pop_back()
if stack.is_empty():
print("Stack is empty.")
stack.push_back(3)
stack.push_back("Value")
stack.push_back(1.5e32)
print(stack)
print("Last element is: " + str(stack.back()))
stack.pop_back()
print(stack)
print("Last element is: " + str(stack.back()))
if not stack.is_empty():
print("Stack is not empty.")
return
</syntaxhighlight>
{{out}}
<pre>
Stack is empty.
[3, "Value", 149999999999999999042044051849216]
Last element is: 149999999999999999042044051849216
[3, "Value"]
Last element is: Value
Stack is not empty.
</pre>
Line 2,934 ⟶ 3,546:
Of course, these stack semantics are not ''exclusive''. Elements of the list can still be accessed and manipulated in myriads of other ways.
If you need exclusive stack semantics, you can use the <code>java.util.Stack</code> class, as demonstrated in the [[Stack#Java|Java]] example.
<syntaxhighlight lang="groovy">def stack = []
assert stack.empty
Line 2,970 ⟶ 3,585:
assert stack.empty
try { stack.pop() } catch (NoSuchElementException e) { println e.message }</
{{out}}
Line 2,983 ⟶ 3,598:
=={{header|Haskell}}==
The Haskell solution is trivial, using a list. Note that <code>pop</code> returns both the element and the changed stack, to remain purely functional.
<
create :: Stack a
Line 3,000 ⟶ 3,615:
peek :: Stack a -> a
peek [] = error "Stack empty"
peek (x:_) = x</
We can make a stack that can be destructively popped by hiding the list inside a <code>State</code> monad.
<
type Stack a b = State [a] b
Line 3,023 ⟶ 3,638:
nonEmpty :: Stack a ()
nonEmpty = empty >>= flip when (fail "Stack empty")</
=={{header|Icon}} and {{header|Unicon}}==
Line 3,030 ⟶ 3,645:
The programmer is free to use any or all of the list processing functions on any problem.
The following illustrates typical stack usage:
<
stack := [] # new empty stack
push(stack,1) # add item
Line 3,045 ⟶ 3,660:
procedure top(x) #: return top element w/o changing stack
return x[1] # in practice, just use x[1]
end</
=={{header|Io}}==
aside from using built-in lists, a stack can be created using nodes like so:
<
next := nil
obj := nil
Line 3,069 ⟶ 3,684:
self node = nn
)
)</
=={{header|Ioke}}==
<
initialize = method(@elements = [])
pop = method(@elements pop!)
empty = method(@elements empty?)
push = method(element, @elements push!(element))
)</
=={{header|IS-BASIC}}==
<
110 NUMERIC STACK(1 TO N)
120 LET PTR=1
Line 3,102 ⟶ 3,717:
300 DEF TOP=STACK(PTR-1)
310 CALL PUSH(3):CALL PUSH(5)
320 PRINT POP+POP</
=={{header|J}}==
<
push=: monad def '0$stack=:stack,y'
pop=: monad def 'r[ stack=:}:stack[ r=.{:stack'
empty=: monad def '0=#stack'</
Example use:
<
pop ''
9
empty ''
1</
pop and empty ignore their arguments. In this implementation. push returns an empty list.
=={{header|Java}}==
The collections framework includes a Stack class. Let's test it:
<
public class StackTest {
Line 3,140 ⟶ 3,755:
stack.pop();
}
}</
{{out}}
<pre>New stack empty? true
Line 3,152 ⟶ 3,767:
Alternatively, you might implement a stack yourself...
<
private Node first = null;
public boolean isEmpty(){
Line 3,180 ⟶ 3,795:
}
}
}</
{{works with|Java|1.5}}
<
private Node first = null;
public boolean isEmpty(){
Line 3,210 ⟶ 3,825:
}
}
}</
=={{header|JavaScript}}==
The built-in Array class already has stack primitives.
<
stack.push(1)
stack.push(2,3);
print(stack.pop()); // 3
print(stack.length); // 2, stack empty if 0</
Here's a constructor that wraps the array:
<
this.data = new Array();
Line 3,227 ⟶ 3,842:
this.empty = function() {return this.data.length == 0}
this.peek = function() {return this.data[this.data.length - 1]}
}</
Here's an example using the revealing module pattern instead of prototypes.
<
function makeStack() {
var stack = [];
Line 3,254 ⟶ 3,869:
};
}
</syntaxhighlight>
=={{header|Jsish}}==
From Javascript entry. Being ECMAScript, Jsi supports stack primitives as part of the Array methods.
<
var stack = [];
puts('depth:', stack.length);
Line 3,272 ⟶ 3,887:
if (stack.length) printf('not '); printf('empty\n');
puts('depth:', stack.length);</
{{out}}
Line 3,284 ⟶ 3,899:
empty
depth: 0</pre>
=={{header|jq}}==
For most purposes, jq's arrays can be used for stacks if needed, without much further ado.
However, since the present task requires the definition of special stack-oriented operations,
we shall start with the following definitions:
<syntaxhighlight lang=jq>
# create a Stack
def Stack: {stack: []};
# check an object is a Stack
def isStack:
type == "object" and has("stack") and (.stack|type) == "array";
def pop:
if .stack|length == 0 then "pop: stack is empty" | error
else {stack: .stack[1:], item: .stack[0]]
end;
def push($x):
.stack = [$x] + .stack | .item = null;
def size:
.stack | length;
def isEmpty:
size == 0;
</syntaxhighlight>
Depending on context, additional code to check for or to enforce
type discipline could be added, but is omitted for simplicity here.
If using the C implementation of jq, the function names could also
be prefixed with "Stack::" to distinguish them as stack-oriented
operations.
For some purposes, this approach may be sufficient, but it can easily
become cumbersome if a sequence of operations must be performed
while also producing outputs that reflect intermediate states.
Suppose for example that we wish to create a stack, push some value,
and then pop the stack, obtaining the popped value as the final
result. This could be accomplished by the pipe:
<syntaxhighlight lang=jq>
Stack | push(3) | pop | .item
</syntaxhighlight>
Now suppose we also wish to record the size of the stack after each of these three operations.
One way to do this would be to write:
<syntaxhighlight lang=jq>
Stack
| size, (push(3)
| size, (pop
| size, .item ))
</syntaxhighlight>
Unfortunately this approach is error-prone and can quickly become tedious, so
we introduce an "observer" function that can "observe" intermediate states following any operation.
With observer/2 as defined below, we can instead write:
<syntaxhighlight lang=jq>
null
| observe(Stack; size)
| observe(push(3); size)
| observe(pop; size)
| .emit, item
</syntaxhighlight>
The idea is that each call to `observe` updates the "emit" slot, so that
all the accumulated messages are available at any point in the pipeline.
<syntaxhighlight lang=jq>
# Input: an object
# Output: the updated object with .emit filled in from `update|emit`.
# `emit` may produce a stream of values, which need not be strings.
def observe(update; emit):
def s(stream): reduce stream as $_ (null;
if $_ == null then .
elif . == null then "\($_)"
else . + "\n\($_)"
end);
.emit as $x
| update
| .emit = s($x // null, emit);
</syntaxhighlight>
=={{header|Julia}}==
Line 3,289 ⟶ 3,987:
The built-in <code>Array</code> class already has efficient (linear amortized time) stack primitives.
<
@show push!(stack, 1) # [1]
@show push!(stack, 2) # [1, 2]
Line 3,296 ⟶ 3,994:
@show length(stack) # 2
@show empty!(stack) # []
@show isempty(stack) # true</
=={{header|K}}==
<
push:{stack::x,stack}
pop:{r:*stack;stack::1_ stack;r}
Line 3,324 ⟶ 4,022:
empty[]
1
</syntaxhighlight>
=={{header|Kotlin}}==
Rather than use the java.util.Stack<E> class, we will write our own simple Stack<E> class for this task:
<
class Stack<E> {
Line 3,372 ⟶ 4,070:
println(e.message)
}
}</
{{out}}
Line 3,384 ⟶ 4,082:
Can't pop elements from an empty stack
</pre>
=={{header|Lambdatalk}}==
The APIs of stacks and queues are built on lambdatalk array primitives, [A.new, A.disp, A.join, A.split, A.array?, A.null?, A.empty?, A.in?, A.equal?, A.length, A.get, A.first, A.last, A.rest, A.slice, A.duplicate, A.reverse, A.concat, A.map, A.set!, A.addlast!, A.sublast!, A.addfirst!, A.subfirst!, A.reverse!, A.sort!, A.swap!, A.lib]. Note that the [A.addlast!, A.sublast!, A.addfirst!, A.subfirst!] primitives are the standard [push!, shift!, pop!, unshift!] ones.
<syntaxhighlight lang="scheme">
{def stack.add
{lambda {:v :s}
{let { {_ {A.addfirst! :v :s}}}
} ok}}
-> stack.add
{def stack.get
{lambda {:s}
{let { {:v {A.first :s}}
{_ {A.subfirst! :s}}
} :v}}}
-> stack.get
{def stack.peek
{lambda {:s}
{A.first :s}}}
-> stack.peek
{def stack.empty?
{lambda {:s}
{A.empty? :s}}}
-> stack.empty?
{def S {A.new}} -> S []
{stack.add 1 {S}} -> ok [1]
{stack.add 2 {S}} -> ok [2,1]
{stack.add 3 {S}} -> ok [3,2,1]
{stack.empty? {S}} -> false
{stack.get {S}} -> 3 [2,1]
{stack.add 4 {S}} -> ok [4,2,1]
{stack.peek {S}} -> 4 [4,2,1]
{stack.get {S}} -> 4 [2,1]
{stack.get {S}} -> 2 [1]
{stack.get {S}} -> 1 []
{stack.get {S}} -> undefined
{stack.empty? {S}} -> true
</syntaxhighlight>
=={{header|lang5}}==
<
: empty? dup execute length if 0 else -1 then swap drop ;
: pop dup execute length 1 - extract swap drop ;
Line 3,399 ⟶ 4,140:
pop . s. cr # 2 [ 1 ]
pop drop
empty? . # -1</
=={{header|Lasso}}==
Lasso Arrays natively supports push and pop.
<
#a->push('a')
Line 3,413 ⟶ 4,154:
#a->pop // b
#a->pop // a
#a->pop // null</
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
global stack$
stack$=""
Line 3,455 ⟶ 4,196:
empty =(stack$="")
end function
</syntaxhighlight>
=={{header|Lingo}}==
<
property _tos
Line 3,480 ⟶ 4,221:
on empty (me)
return voidP(me.peek())
end</
=={{header|Logo}}==
[[UCB Logo]] has built-in methods for treating lists as stacks. Since they are destructive, they take the name of the stack rather than the list itself.
<
push "stack 1
push "stack 2
push "stack 3
print pop "stack ; 3
print empty? :stack ; false</
=={{header|Logtalk}}==
A stack can be trivially represented using the built-in representation for lists:
<
:- object(stack).
Line 3,506 ⟶ 4,247:
:- end_object.
</syntaxhighlight>
=={{header|LOLCODE}}==
{{trans|UNIX Shell}}
<
HOW IZ I Init YR Stak
Stak HAS A Length ITZ 0
Line 3,545 ⟶ 4,286:
IM OUTTA YR Loop
KTHXBYE</
{{Out}}
Line 3,555 ⟶ 4,296:
=={{header|Lua}}==
Tables have stack primitives by default:
<
table.insert(stack,3)
print(table.remove(stack)) --> 3</
=={{header|M2000 Interpreter}}==
A Stack object can be used as LIFO or FIFO. Push statement push to top of stack. Read pop a value to a variable from top of stack. StackItem(1) read top item without modified stack. Data statement append items to bottom.
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
a=Stack
Line 3,577 ⟶ 4,318:
}
Checkit
</syntaxhighlight>
Every module and function has a "current" stack. Number is a read only variable, which pop a value from current stack (or raise error if not number is in top of stack).
Line 3,584 ⟶ 4,325:
Return/Execution stack is hidden and different from stack of values.
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
Read a, b
Line 3,612 ⟶ 4,353:
Print alfa(1,2,3,4)=2.5
</syntaxhighlight>
=={{header|Maple}}==
<
s := stack:-new(a, b):
Line 3,627 ⟶ 4,368:
empty(s);
pop(s);
empty(s);</
{{out}}
<pre> c
Line 3,642 ⟶ 4,383:
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
SetAttributes[Push, HoldAll];[a_, elem_] := AppendTo[a, elem]
SetAttributes[Pop, HoldAllComplete];
Line 3,655 ⟶ 4,396:
->4
Peek[stack]
->3</
=={{header|MATLAB}} / {{header|Octave}}==
Here is a simple implementation of a stack, that works in Matlab and Octave. It is closely related to the queue/fifo example.
<
% push
Line 3,671 ⟶ 4,412:
% empty
isempty(mystack)</
Below is another solution, that encapsulates the fifo within the object-orientated "class" elements supported by Matlab. The given implementation is exactly the same as the MATLAB FIFO example, except that the "push()" function is modified to add stuff to the end of the queue instead of the beginning. This is a naive implementation, for rigorous applications this should be modified to initialize the LIFO to a buffered size, so that the "pop()" and "push()" functions don't resize the cell array that stores the LIFO's elements, every time they are called.
To use this implementation you must save this code in a MATLAB script file named "LIFOQueue.m" which must be saved in a folder named @LIFOQueue in your MATLAB directory.
<
classdef LIFOQueue
Line 3,756 ⟶ 4,497:
end %methods
end</
Sample Usage:
<
myLIFO =
Line 3,787 ⟶ 4,528:
ans =
0</
=={{header|Maxima}}==
<
load(basic)$
Line 3,800 ⟶ 4,541:
emptyp(a);
length(a);</
=={{header|Mercury}}==
Line 3,806 ⟶ 4,547:
Efficient, generic stacks are provided as part of the standard library in Mercury. For sake of illustration, here is how a simple stack could be implemented.
<
:- interface.
Line 3,838 ⟶ 4,579:
!:Stack = sstack(Elems).
:- end_module sstack.</
It should be noted that this is purely an illustrative example of a very simple stack.
Line 3,849 ⟶ 4,590:
Note also that while pop/3 has three parameters, the function implementation looks like it has two. This is because the !Stack "parameter" is actually a ''pair'' of parameters using Mercury's state variable notation. !Stack is, in effect, two variables: !.Stack and !:Stack, input and output respectively. Using state variable notation here is a bit of overkill but again was brought in for pedagogical reasons to show the syntax.
=={{header|MIPS Assembly}}==
<syntaxhighlight lang="mips">addi sp,sp,-4
sw t0,0(sp) ;push
lw t0,0(sp)
addi sp,sp,4 ;pop
lw t0,0(sp) ;top</syntaxhighlight>
"Empty" requires you to know the starting value of <code>SP</code>. Since it's hardware-dependent, there's no one answer for this part of the task.
=={{header|MiniScript}}==
<
// and any other number is true.
// therefore the .len function works as the inverse of a .empty function
Line 3,864 ⟶ 4,617:
else
print "Stack is empty"
end if</
{{out}}
<pre>
Line 3,875 ⟶ 4,628:
=={{header|Nanoquery}}==
<
declare internalList
Line 3,897 ⟶ 4,650:
return len(internalList) = 0
end
end</
=={{header|Nemerle}}==
Mutable stacks are available in <tt>System.Collections</tt>, <tt>System.Collections.Generic</tt> and <tt>Nemerle.Collections</tt> depending on what functionality beyond the basics you want. An immutable stack could be implemented fairly easily, as, for example, this quick and dirty list based implementation.
<
{
private stack : list[T];
Line 3,934 ⟶ 4,687:
stack.Length == 0
}
}</
=={{header|NetRexx}}==
<
* 13.08.2013 Walter Pachl translated from REXX version 2
**********************************************************************/
Line 3,978 ⟶ 4,731:
method empty(stk) static
Return stk[0]=0</
{{out}}
<pre>
Line 3,994 ⟶ 4,747:
If we want a stack type limited to the four or five functions of the task, it is possible to define a distinct generic type <code>Stack[T]</code> derived from <code>seq[T]</code>. The code will be typically as follows. Note that we have defined a procedure <code>top</code> to get the value of the top item, another <code>mtop</code> to get a mutable reference to the top item and also a procedure <code>mtop=</code> to assign directly a value to the top item.
<
func initStack[T](initialSize = 32): Stack[T] =
Line 4,035 ⟶ 4,788:
echo s.top
s.mtop = 5
echo s.top</
{{out}}
Line 4,045 ⟶ 4,798:
=={{header|Oberon-2}}==
{{Works with|oo2c version 2}}
<
MODULE Stacks;
IMPORT
Line 4,112 ⟶ 4,865:
Test
END Stacks.
</syntaxhighlight>
{{out}}
<pre>
Line 4,121 ⟶ 4,874:
</pre>
{{works with|AOS}}
<
MODULE Stacks; (** AUTHOR ""; PURPOSE ""; *)
Line 4,205 ⟶ 4,958:
END Test;
END Stacks.
</syntaxhighlight>
{{out}}
<pre>
Line 4,215 ⟶ 4,968:
=={{header|Objeck}}==
Class library support for Stack/IntStack/FloatStack
<
stack->Push(13);
stack->Push(7);
(stack->Pop() + stack->Pop())->PrintLine();
stack->IsEmpty()->PrintLine();</
=={{header|Objective-C}}==
Using a NSMutableArray:
<
[stack addObject:value]; // pushing
Line 4,230 ⟶ 4,983:
[stack removeLastObject]; // popping
[stack count] == 0 // is empty?</
=={{header|OCaml}}==
Implemented as a singly-linked list, wrapped in an object:
<
class ['a] stack =
Line 4,251 ⟶ 5,004:
method is_empty =
lst = []
end</
=={{header|Oforth}}==
Line 4,257 ⟶ 5,010:
Stack is already defined at startup.
<
Stack method: push self add ;
Stack method: pop self removeLast ;
Stack method: top self last ;</
Usage :
<
| s |
Stack new ->s
Line 4,273 ⟶ 5,026:
s pop println
s pop println
s isEmpty ifTrue: [ "Stack is empty" println ] ;</
{{out}}
Line 4,286 ⟶ 5,039:
=={{header|Ol}}==
Simplest stack can be implemented using 'cons' and 'uncons' primitives.
<
(define stack #null)
(print "stack is: " stack)
Line 4,329 ⟶ 5,082:
(print "stack: " stack)
(print "is stack empty: " (eq? stack #null))
</syntaxhighlight>
{{out}}
<pre>
Line 4,364 ⟶ 5,117:
But in real programs may be useful a more complex stack implementation based on coroutines (ol is a purely functional lisp, so it does not support mutators like 'set!').
<
(fork-server 'stack (lambda ()
(let this ((me '()))
Line 4,386 ⟶ 5,139:
(mail 'stack ['push value]))
(define (pop)
(
(define (empty)
(
(for-each (lambda (n)
Line 4,402 ⟶ 5,155:
(loop))))
(print "done.")
</syntaxhighlight>
{{out}}
Line 4,427 ⟶ 5,180:
=={{header|ooRexx}}==
The ooRexx queue class functions as a stack as well (it is a dequeue really).
<syntaxhighlight lang="oorexx">
stack = .queue~of(123, 234) -- creates a stack with a couple of items
stack~push("Abc") -- pushing
Line 4,434 ⟶ 5,187:
-- the is empty test
if stack~isEmpty then say "The stack is empty"
</syntaxhighlight>
=={{header|OxygenBasic}}==
The real stack is freely available!
<
function f()
sys a=1,b=2,c=3,d=4
Line 4,459 ⟶ 5,212:
f
</syntaxhighlight>
=={{header|Oz}}==
A thread-safe, list-based stack. Implemented as a module:
<
export
New
Line 4,493 ⟶ 5,246:
@Stack == nil
end
end</
There is also a stack implementation in the [http://www.mozart-oz.org/home/doc/mozart-stdlib/adt/stack.html standard library].
=={{header|PARI/GP}}==
<
pop()={
if(#v,
Line 4,514 ⟶ 5,267:
error("Stack underflow")
)
};</
=={{header|Pascal}}==
This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects).
<
type
pStackNode = ^tStackNode;
Line 4,572 ⟶ 5,325:
PopFromStack := node^.data;
dispose(node);
end;</
=={{header|Perl}}==
Perl comes prepared to treat its arrays as stacks, giving us the push and pop functions for free. To add empty, we basically give a new name to "not":
<
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">-- comparing a simple implementation against using the builtins:</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">push_</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">what</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</span><span style="color: #0000FF;">,</span><span style="color: #000000;">what</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">pop_</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">what</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[$]</span>
<span style="color: #000000;">stack</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">stack</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">what</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">empty_</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">stack</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: #0000FF;">?</span><span style="color: #000000;">empty_</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- 1</span>
<span style="color: #000000;">push_</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">empty_</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- 0</span>
<span style="color: #000000;">push_</span><span style="color: #0000FF;">(</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">pop_</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- 6</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">pop_</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- 5</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">empty_</span><span style="color: #0000FF;">()</span> <span style="color: #000080;font-style:italic;">-- 1</span>
<span style="color: #0000FF;">?</span><span style="color: #008000;">"===builtins==="</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (latest bugfixes, plus top renamed as peep, for p2js)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">sid</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_stack</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">stack_empty</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 1</span>
<span style="color: #7060A8;">push</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">stack_empty</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 0</span>
<span style="color: #7060A8;">push</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">,</span><span style="color: #000000;">6</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">--?peep(sid) -- 6 (leaving it there)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">pop</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 6</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">pop</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 5</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">stack_empty</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sid</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- 1</span>
<!--</syntaxhighlight>-->
Note you get true/false rather than 1/0 under pwa/p2js (use printf(%t) for consistent results)
=={{header|PHP}}==
PHP arrays behave like a stack:
<
empty( $stack ); // true
Line 4,690 ⟶ 5,386:
echo array_pop( $stack ); // outputs "2"
echo array_pop( $stack ); // outputs "1"</
=={{header|PicoLisp}}==
The built-in functions [http://software-lab.de/doc/refP.html#push push] and
[http://software-lab.de/doc/refP.html#pop pop] are used to maintain a stack (of any type).
<
(push 'Stack 2)
(push 'Stack 1)</
<pre>: Stack
-> (1 2 3)
Line 4,717 ⟶ 5,413:
other things contains a stack.
<syntaxhighlight lang="pike">
object s = ADT.Stack();
s->push("a");
Line 4,724 ⟶ 5,420:
s->top(), s->pop(), s->pop());
s->reset(); // Empty the stack
</syntaxhighlight>
{{Out}}
<pre>
Line 4,731 ⟶ 5,427:
=={{header|PL/I}}==
<
declare s float controlled;
Line 4,769 ⟶ 5,465:
free s;
end;
/* The values are printed in the reverse order, of course. */</
=={{header|PostScript}}==
{{libheader|initlib}}
<
/push {exch cons}.
/pop {uncons exch pop}.
Line 4,783 ⟶ 5,479:
=false
[] empty?
=true</
=={{header|PowerShell}}==
A new stack:
<syntaxhighlight lang="powershell">
$stack = New-Object -TypeName System.Collections.Stack
# or
$stack = [System.Collections.Stack] @()
</syntaxhighlight>
Push some stuff on the stack:
<syntaxhighlight lang="powershell">
1, 2, 3, 4 | ForEach-Object {$stack.Push($_)}
</syntaxhighlight>
Show stack as a string:
<syntaxhighlight lang="powershell">
$stack -join ", "
</syntaxhighlight>
{{Out}}
<pre>
Line 4,805 ⟶ 5,501:
</pre>
Pop the top level of the stack:
<syntaxhighlight lang="powershell">
$stack.Pop()
</syntaxhighlight>
{{Out}}
<pre>
Line 4,813 ⟶ 5,509:
</pre>
Show stack as a string:
<syntaxhighlight lang="powershell">
$stack -join ", "
</syntaxhighlight>
{{Out}}
<pre>
Line 4,821 ⟶ 5,517:
</pre>
Get a copy of the top level of the stack:
<syntaxhighlight lang="powershell">
$stack.Peek()
</syntaxhighlight>
{{Out}}
<pre>
Line 4,829 ⟶ 5,525:
</pre>
The stack:
<syntaxhighlight lang="powershell">
$stack
</syntaxhighlight>
{{Out}}
<pre>
Line 4,841 ⟶ 5,537:
=={{header|Prolog}}==
Prolog is a particularly silly language to implement stack functions in, as the built-in lists can be treated as stacks in an ad hoc manner. Nonetheless, in the name of completeness:
<
% True if NEW is [ELEMENT|STACK]
push(ELEMENT,STACK,[ELEMENT|STACK]).
Line 4,851 ⟶ 5,547:
% empty( STACK )
% True if STACK is empty
empty([]).</
=={{header|PureBasic}}==
For LIFO function PureBasic normally uses linked lists.
Usage as described above could look like;
<
Procedure Push_LIFO(n)
Line 4,893 ⟶ 5,589:
While Not Empty_LIFO()
Debug Pop_LIFO()
Wend</
{{out}}
Line 4,906 ⟶ 5,602:
The faster and Pythonic way is using a deque (available from 2.4).
A regular list is a little slower.
<
stack = deque()
stack.append(value) # pushing
value = stack.pop()
not stack # is empty?</
If you need to expose your stack to the world, you may want to create a simpler wrapper:
<
class Stack:
Line 4,922 ⟶ 5,618:
return self._items.pop()
def __nonzero__(self):
return bool(self._items)</
Here is a stack implemented as linked list - with the same list interface.
<
def __init__(self):
self._first = None
Line 4,935 ⟶ 5,631:
raise IndexError, "pop from empty stack"
value, self._first = self._first
return value</
Notes:
Using list interface - append, __nonzero__ make it easier to use, cleanup the client code, and allow changing the implementation later without affecting the client code.
For example, instead of:
<syntaxhighlight lang
You can write:
<syntaxhighlight lang
Quick testing show that deque is about 5 times faster then the wrapper linked list implementations. This may be important if your stack is used in tight loops.
Line 4,949 ⟶ 5,645:
Quackery is a stack based language. In addition to ''the stack'' (i.e. the Quackery data stack) and the call stack, named ancillary stacks can be created with <code>[ stack ] is <name-of-stack></code>. Pushing to and popping from ancillary stacks is done with the words <code>put</code> and <code>take</code>. A word to test if an ancillary stack is empty can be defined as <code>[ size 1 = ] is isempty</code>. (The word <code>empty</code> already has a meaning in Quackery.) The word <code>share</code> returns the topmost element of an ancillary stack without changing the ancillary stack. Other ancillary stack operations are also available.
<
[ stack ] is mystack ( --> s )
Line 4,963 ⟶ 5,659:
mystack take echo say " has been removed from mystack" cr cr
mystack isempty if [ say "mystack is empty" cr cr ]
say "you are in a maze of twisty little passages, all alike"</
{{out}}
Line 4,984 ⟶ 5,680:
{{libheader|proto}}
See [[FIFO]] for functional and object oriented implementations of a First-In-First-Out object, with similar code.
<
stack <- proto(expr = {
Line 5,037 ⟶ 5,733:
stack$pop()
# Error in get("pop", env = stack, inherits = TRUE)(stack, ...) :
# can't pop from an empty list</
=={{header|Racket}}==
Line 5,043 ⟶ 5,739:
Quick functional version:
<syntaxhighlight lang="racket">
#lang racket
(define stack '())
Line 5,049 ⟶ 5,745:
(define (pop stack) (values (car stack) (cdr stack)))
(define (empty? stack) (null? stack))
</syntaxhighlight>
And a destructive object:
<syntaxhighlight lang="racket">
(struct stack ([items #:auto]) #:mutable #:auto-value '())
(define (push! x stack)
Line 5,062 ⟶ 5,758:
(define (empty? stack)
(null? (stack-items stack)))
</syntaxhighlight>
=={{header|Raku}}==
Line 5,068 ⟶ 5,764:
Raku still has the stack functions from Perl 5, but now they also can be accessed by object notation:
<syntaxhighlight lang="raku"
@stack.push($elem); # add $elem to the end of @stack
$elem = @stack.pop; # get the last element back
@stack.elems == 0 # true, because the stack is empty
not @stack # also true because @stack is false</
=={{header|Raven}}==
Use built in ''stack'' type:
<
1 s push
s pop</
Word ''empty'' is also built in:
<
=={{header|REBOL}}==
<
Title: "Stack"
URL: http://rosettacode.org/wiki/Stack
Line 5,116 ⟶ 5,812:
assert ['test = v/pop]
assert ['a = v/pop]
assert [not v/empty]</
Sample run:
<pre>Simple integers:
Line 5,132 ⟶ 5,828:
=={{header|Retro}}==
<
: push ( na- ) dup ++ dup @ + ! ;
: pop ( a-n ) dup @ over -- + @ ;
Line 5,146 ⟶ 5,842:
st top putn
st pop putn st pop putn st pop putn
st empty? putn</
=={{header|REXX}}==
===version 1===
<
push y /*pushes 123 onto the stack. */
pull g /*pops last value stacked & removes it. */
Line 5,156 ⟶ 5,852:
exit /*stick a fork in it, we're done. */
empty: return queued() /*subroutine returns # of stacked items.*/</
===version 2===
<
* supports push, pull, and peek
* 11.08.2013 Walter Pachl
Line 5,200 ⟶ 5,896:
empty: Procedure Expose stk.
Return stk.0=0</
{{out}}
<pre>
Line 5,213 ⟶ 5,909:
=={{header|Ring}}==
<
# Project : Stack
Line 5,231 ⟶ 5,927:
see "Pop: stack is empty" + nl
ok
</syntaxhighlight>
Output:
<pre>
Line 5,245 ⟶ 5,941:
</pre>
=={{header|RPL}}==
The RPL interpreter is based on a stack, with which the user interacts.
*the push operation is performed by the <code>DUP</code> instruction
*the pop operation by <code>DROP</code>
*<code>DEPTH</code> provides the stack size. To test the emptiness of the stack, the following program can be created as an user-defined instruction:
≪ DEPTH NOT ≫ 'EMPTY?' STO
=={{header|Ruby}}==
Using an Array, there are already methods Array#push, Array#pop and Array#empty?.
<
stack.push(value) # pushing
value = stack.pop # popping
stack.empty? # is empty?</
If you need to expose your stack to the world, you may want to create a simpler wrapper. Here is a wrapper class ''Stack'' that wraps ''Array'' but only exposes stack methods.
<
# A stack contains elements in last-in, first-out order.
Line 5,321 ⟶ 6,023:
end
alias inspect to_s
end</
<
p s.empty? # => true
p s.size # => 0
Line 5,341 ⟶ 6,043:
p s = Stack[:a, :b, :c] # => Stack[:a, :b, :c]
p s << :d # => Stack[:a, :b, :c, :d]
p s.pop # => :d</
Just meeting the requirements of a push, pop and empty method:
<
class Stack
Line 5,355 ⟶ 6,057:
def_delegators :@stack, :push, :pop, :empty?
end
</syntaxhighlight>
(push takes multiple arguments; pop takes an optional argument which specifies how many to pop)
=={{header|Run BASIC}}==
<
global stack$
global stackEnd
Line 5,399 ⟶ 6,101:
FUNCTION mt$()
stackEnd = 0
END FUNCTION</
{{out}}
<pre>Pushed A stack has 1
Line 5,415 ⟶ 6,117:
One could just use a vector (<code>Vec<T></code>) which is part of the standard library
<
let mut stack = Vec::new();
stack.push("Element1");
Line 5,426 ⟶ 6,128:
assert_eq!(Some("Element1"), stack.pop());
assert_eq!(None, stack.pop());
}</
===Simple implementation===
Simply uses a singly-linked list.
<
pub struct Stack<T> {
Line 5,538 ⟶ 6,240:
}
}
}</
=={{header|Sather}}==
This one uses a builtin linked list to keep the values pushed onto the stack.
<
private attr stack :LLIST{T};
Line 5,574 ⟶ 6,276:
return stack.is_empty;
end;
end;</
<
main is
s ::= #STACK{INT};
Line 5,589 ⟶ 6,291:
until!(s.is_empty); end;
end;
end;</
Sather library has the abstract class <code>$STACK{T}</code>, but using this forces us to implement other methods too.
=={{header|Scala}}==
The Do it yourself approach:
<
private var items = List[T]()
Line 5,610 ⟶ 6,312:
def push(value: T) = items = value +: items
}</
Or use the standard Scala library.
Slightly modified to meet to requirements of this task.
<
class Stack[T] extends Stak[T] {
Line 5,621 ⟶ 6,323:
}
def peek: T = this.head
}</
val stack = new Stack[String]
Line 5,633 ⟶ 6,335:
assert(stack.pop() == "Peter Pan")
println("Completed without errors")
}</
=={{header|Scheme}}==
This version uses primitive message passing.
<
(let ((st '()))
(lambda (message . args)
Line 5,651 ⟶ 6,353:
(set! st (cdr st))
result)))
(else 'badmsg)))))</
=={{header|Seed7}}==
<
const func type: stack (in type: baseType) is func
Line 5,694 ⟶ 6,396:
writeln(pop(s) = 10);
writeln(empty(s));
end func;</
=={{header|SenseTalk}}==
<
repeat with each item of 1 .. 10
push it into stack
Line 5,705 ⟶ 6,407:
pop stack
put it
end repeat</
=={{header|Sidef}}==
Using a built-in array:
<
stack.push(42); # pushing
say stack.pop; # popping
say stack.is_empty; # is_emtpy?</
Creating a Stack class:
<
method pop { stack.pop };
method push(item) { stack.push(item) };
Line 5,724 ⟶ 6,426:
stack.push(42);
say stack.pop; # => 42
say stack.empty; # => true</
=={{header|Slate}}==
From Slate's standard library:
<
"An abstraction over ExtensibleArray implementations to follow the stack
protocol. The convention is that the Sequence indices run least-to-greatest
Line 5,749 ⟶ 6,451:
s@(Stack traits) bottom
[s first].</
=={{header|Smalltalk}}==
Smalltalk has a built-in Stack class, instances of which you can send messages:
<
s := Stack new.
s push: 1.
Line 5,760 ⟶ 6,462:
s pop.
s top. "2"
</syntaxhighlight>
=={{header|Standard ML}}==
Line 5,766 ⟶ 6,468:
The signature for a module supplying a stack interface, with a couple added functions.
<
sig
type 'a stack
Line 5,781 ⟶ 6,483:
val map : ('a -> 'b) -> 'a stack -> 'b stack
val app : ('a -> unit) -> 'a stack -> unit
end</
An implementation of the <code>STACK</code> signature, using immutable lists.
<
struct
type 'a stack = 'a list
Line 5,806 ⟶ 6,508:
fun map f st = List.map f st
fun app f st = List.app f st
end</
=={{header|Stata}}==
Line 5,813 ⟶ 6,515:
=={{header|Swift}}==
Generic stack.
<
var items = [T]()
var empty:Bool {
Line 5,838 ⟶ 6,540:
println(stack.peek())
stack.pop()
println(stack.empty)</
{{out}}
<pre>
Line 5,847 ⟶ 6,549:
=={{header|Tailspin}}==
<
processor Stack
@: $;
Line 5,887 ⟶ 6,589:
' -> !OUT::write
'$myStack::empty;' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 5,900 ⟶ 6,602:
=={{header|Tcl}}==
Here's a simple implementation using a list:
<
upvar 1 $stackvar stack
lappend stack $value
Line 5,930 ⟶ 6,632:
peek S ;# ==> bar
pop S ;# ==> bar
peek S ;# ==> foo</
{{tcllib|struct::stack}}
<
struct::stack S
S size ;# ==> 0
Line 5,941 ⟶ 6,643:
S peek ;# ==> d
S pop 4 ;# ==> d c b a
S size ;# ==> 0</
=={{header|Uiua}}==
<syntaxhighlight lang="Uiua">
[3] # Since UIUA is a stack language, everything is pushed on the stack
x ← # stores the top of the stack into the variable x
? # ? checks the stack, it is now empty
</syntaxhighlight>
=={{header|UnixPipes}}==
<
push() { echo $1 >> stack; }
pop() {
Line 5,954 ⟶ 6,667:
}
empty() { head -n -1 stack |wc -l; }
stack_top() { tail -1 stack; }</
test it:
<
% pop;pop;pop;pop
them
us
you
me</
=={{header|UNIX Shell}}==
Line 5,969 ⟶ 6,682:
Here's a simple single-stack solution:
<
if [[ -n $KSH_VERSION ]]; then
set -A stack
Line 6,001 ⟶ 6,714:
while ! empty; do
pop
done</
{{Out}}
Line 6,012 ⟶ 6,725:
You can generalize it to multiple stacks with some judicious use of the twin evils of pass-by-name and <tt>eval</tt>:
<
if [[ -n $KSH_VERSION ]]; then
eval 'set -A '"$1"
Line 6,043 ⟶ 6,756:
while ! empty mystack; do
pop mystack
done</
{{Out}}
Line 6,054 ⟶ 6,767:
=={{header|VBA}}==
Define a class Stack in a class module with that name.
<
'uses a dynamic array of Variants to stack the values
Line 6,090 ⟶ 6,803:
Property Get Size() As Integer
Size = myStackHeight
End Property</
Usage example:
<
Public Sub stacktest()
Dim aStack As New Stack
Line 6,112 ⟶ 6,825:
.Pop
End With
End Sub</
{{out}}
<pre>
Line 6,126 ⟶ 6,839:
=={{header|VBScript}}==
===Stack class===
<
dim tos
dim stack()
Line 6,181 ⟶ 6,894:
wscript.echo s.pop
if s.stackempty then exit for
next</
{{out}} (changes every time)
<pre>-1
Line 6,205 ⟶ 6,918:
0.7055475</pre>
===Using an ArrayList.===
<
Option Explicit
Line 6,243 ⟶ 6,956:
Function empty_(s)
empty_ = s.Count = 0
End Function 'empty_ </
{{out}}
<pre>
Line 6,256 ⟶ 6,969:
</pre>
=={{header|V (Vlang)}}==
<
max_depth = 256
)
Line 6,309 ⟶ 7,022:
stack.pop() or { return }
}
</syntaxhighlight>
{{out}}
<pre>Stack is empty? Yes
Line 6,324 ⟶ 7,037:
Stacks as user-defined objects backed by a list.
<
(tag 'stack nil)
Line 6,334 ⟶ 7,047:
def (empty? s) :case (isa stack s)
(empty? rep.s)</
Example usage:
Line 6,360 ⟶ 7,073:
{{libheader|Wren-seq}}
This uses the Stack class in the above module.
<
var s = Stack.new()
Line 6,372 ⟶ 7,085:
s.clear()
System.print("Stack cleared")
System.print("Is stack now empty? %((s.isEmpty) ? "yes" : "no")")</
{{out}}
Line 6,385 ⟶ 7,098:
=={{header|X86 Assembly}}==
<
; x86_64 linux nasm
Line 6,468 ⟶ 7,181:
mov rdi, 1
syscall
</syntaxhighlight>
=={{header|XLISP}}==
This is a fairly straightforward implementation, representing a stack as a linked list inside an object.
<
(instance-variables vals))
Line 6,488 ⟶ 7,201:
(define-method (stack 'emptyp)
(null vals))</
A sample REPL session:
<
[1] (define st (stack 'new))
Line 6,512 ⟶ 7,225:
#T
[8] </
=={{header|XPL0}}==
<
int Stack(100), SP;
Line 6,543 ⟶ 7,256:
while not Empty do [IntOut(0, Pop); ChOut(0, ^ )];
CrLf(0);
]</
{{out}}
Line 6,552 ⟶ 7,265:
=={{header|Yabasic}}==
<
dim stack(limit)
Line 6,592 ⟶ 7,305:
print "Pop ", pop()
</syntaxhighlight>
=={{header|Z80 Assembly}}==
The stack can be initialized by loading it directly with an immediate value. Z80-based home computers such as the Amstrad CPC and ZX Spectrum do this for you. Messing with the stack on those systems is a bad idea, since an assembly program stored on a floppy disk or cassette tape begins with the return address of BASIC on top of the stack. However, on embedded systems like the Game Boy or the Sega Master System, this step is a must, as the CPU does ''not'' have an initial stack pointer value in its vector table and thus does not guarantee the value of SP upon startup. Unlike the 6502, the Z80's stack does not have a fixed size or memory location, and is only limited by the address space of the CPU. From a practical standpoint, however, it's very unlikely you'll need more than 256 bytes.
<syntaxhighlight lang="z80">LD SP,&FFFF</syntaxhighlight>
Registers must be pushed in pairs. If you push/pop the accumulator, the processor flags go with it. This can make certain functions difficult to write without using a temporary variable to hold the accumulator, which doesn't allow for recursion or arbitrary nesting.
<syntaxhighlight lang="z80">push af
push bc
push de
push hl</syntaxhighlight>
Popping is very similar. To properly pop values, they must be popped in the reverse order they were pushed.
<
pop de
pop bc
pop af</
The stack is empty if its value equals the original starting value of the stack pointer. This is a little difficult, since the stack doesn't necessarily start in a fixed location like it does on the 6502. There are two ways to do this:
<syntaxhighlight lang="z80">ld (&nnnn),SP ;&nnnn represents a memory location that the programmer will later read from to use as a
;comparison for the current stack pointer</syntaxhighlight>
<syntaxhighlight lang="z80">ld hl,0
add hl,sp ;the z80 doesn't allow you to load SP directly into HL, so this is the quickest way</syntaxhighlight>
From there it's a matter of comparing this value to the current stack pointer, which in itself is tricky since the built-in compare instruction forces you to use the accumulator as one of the operands, and works natively in terms of 8-bit values.
Peek can be achieved with the <code>EX (SP),HL</code> command which exchanges HL with the top item of the stack.
On the Game Boy, the stack can also be manually adjusted by a signed 8-bit constant. A Zilog Z80 cannot do this in a single command. The code below only works on a Game Boy or any other hardware running on a Sharp LR35902 CPU:
<syntaxhighlight lang="z80"> ADD SP,&FE ;subtract two from the stack pointer. Remember that the stack grows "down" in memory.</syntaxhighlight>
It should be noted that although the "heap" and the "stack" are considered separate areas of memory by the programmer, in the eyes of the CPU there is no boundary between them. The CPU doesn't care if you push enough words onto the stack so that the stack pointer is now pointing to the heap, or even ROM space. Most of the time this isn't an issue, as long as your push/pop operations are properly balanced. It's just something to look out for.
=={{header|zkl}}==
Lists have stack methods so this class is somewhat reduntant
<
var [const] stack=L();
fcn push(x){stack.append(x); self}
Line 6,617 ⟶ 7,350:
fcn empty {(not stack.len())}
var [proxy] isEmpty = empty;
}</
{{out}}
<pre>
|