Stack

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

Data Structure
This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.

A stack is a container of elements with last in, first out access policy. Sometimes it also called LIFO. The stack is accessed through its top. The basic stack operations are:

• push stores a new element onto the stack top;
• pop returns the last pushed stack element, while removing it from the stack;
• empty tests if the stack contains no elements.

Sometimes the last pushed stack element is made accessible for immutable access (for read) or mutable access (for write):

• top (sometimes called peek to keep with the p theme) returns the topmost element without modifying the stack.

Stacks allow a very simple hardware implementation. They are common in almost all processors. In programming stacks are also very popular for their way (LIFO) of resource management, usually memory. Nested scopes of language objects are naturally implemented by a stack (sometimes by multiple stacks). This is a classical way to implement local variables of a reentrant or recursive subprogram. Stacks are also used to describe a formal computational framework. See stack machine. Many algorithms in pattern matching, compiler construction (e.g. recursive descent parsers), and machine learning (e.g. based on tree traversal) have a natural representation in terms of stacks.

Create a stack supporting the basic operations: push, pop, empty.

ActionScript

In ActionScript an Array object provides stack functionality. <lang actionscript>var stack:Array = new Array(); stack.push(1); stack.push(2); trace(stack.pop()); // outputs "2" trace(stack.pop()); // outputs "1"</lang>

Ada

This is a generic stack implementation. <lang ada>generic

  type Element_Type is private; 

package Generic_Stack is

  type Stack is private; 
  procedure Push (Item : Element_Type; Onto : in out Stack); 
  procedure Pop (Item : out Element_Type; From : in out Stack); 
  function Create return Stack;
  Stack_Empty_Error : exception;

private

  type Node; 
  type Stack is access Node; 
  type Node is record 
     Element : Element_Type;  
     Next    : Stack        := null;  
  end record; 

end Generic_Stack;</lang> <lang ada>with Ada.Unchecked_Deallocation;

package body Generic_Stack is

  ------------
  -- Create --
  ------------
  
  function Create return Stack is
  begin
     return (null);
  end Create;

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

  procedure Push(Item : Element_Type; Onto : in out Stack) is
     Temp : Stack := new Node;
  begin
     Temp.Element := Item;
     Temp.Next := Onto;
     Onto := Temp; 
  end Push;

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

  procedure Pop(Item : out Element_Type; From : in out Stack) is
     procedure Free is new Ada.Unchecked_Deallocation(Node, Stack);
     Temp : Stack := From;
  begin
     if Temp = null then
        raise Stack_Empty_Error;
     end if;
     Item := Temp.Element;
     From := Temp.Next;
     Free(Temp);
  end Pop;

end Generic_Stack;</lang>

ALGOL 68

ALGOL 68 uses "HEAP" variables for new LINKs in a linked list. Generally ALGOL 68's garbage collector should recover the LINK memory some time after a value is popped. <lang algol68>MODE VALUE = STRING; # type of a LINK in this STACK #

MODE LINK = STRUCT(VALUE value, REF LINK next); MODE STACK = STRUCT(REF LINK first);

STRUCT (

   PROC (REF STACK)VOID init,
   PROC (REF STACK)BOOL non zero,
   PROC (REF STACK, VALUE)VOID append,
   PROC (REF STACK)VALUE pop,
   PROC (REF STACK)STRING repr,
   PROC (REF STACK, STRING)BOOL index error mended

) class stack = (

 # PROC init = # (REF STACK self)VOID:
       first OF self := NIL,
 # PROC non zero = # (REF STACK self)BOOL:
       REF LINK(first OF self) ISNT NIL ,
 # PROC append = # (REF STACK self, VALUE value)VOID:
       first OF self := HEAP LINK := (value, first OF self),
 # PROC pop = # (REF STACK self)VALUE: (
       IF first OF self IS NIL THEN
           STRING message = "pop from empty stack";
           IF NOT (index error mended OF class stack)(self, message) THEN
               raise index error(message)
           FI
       FI;
       VALUE out = value OF first OF self;
       first OF self := next OF first OF self;
       out
   ),
 # PROC repr = # (REF STACK self)STRING: (
       STRING out := "(",
              sep := "";
       REF LINK this := first OF self;
       WHILE REF LINK(this) ISNT NIL DO
         out +:= sep + """" + value OF this + """";
         sep := ", ";
         this := next OF this
       OD;
       out+")"
   ),
 # PROC index error mended = # (REF STACK self, STRING message)BOOL: 
       FALSE # no mend applied #

);

PROC raise index error := (STRING message)VOID: stop;

STACK stack; (init OF class stack)(stack);

[]STRING sample = ("Was", "it", "a", "cat", "I", "saw");

FOR i TO UPB sample DO

 (append OF class stack)(stack, sample[i])

OD;

print(((repr OF class stack)(stack), newline))</lang> Output:

("saw", "I", "cat", "a", "it", "Was")

AutoHotkey

<lang AutoHotkey>msgbox % stack("push", 4) msgbox % stack("push", 5) msgbox % stack("peek") msgbox % stack("pop") msgbox % stack("peek") msgbox % stack("empty") msgbox % stack("pop") msgbox % stack("empty") return

stack(command, value = 0) {

 static 

if !pointer pointer = 10000

 if (command = "push")
 {
 _p%pointer% := value
 pointer -= 1 
 return value
 }
 if (command = "pop")
 {
   pointer += 1
   return _p%pointer%
 }
 if (command = "peek")

{ next := pointer + 1 return _p%next% }

 if (command = "empty")
 {
  if (pointer == 10000)
   return "empty"

else return 0

 }

}</lang>

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.

<lang dos> @echo off setlocal enableDelayedExpansion

LIFO stack usage

Define the stack

call :newStack myStack

Push some values onto the stack

for %%A in (value1 value2 value3) do call :pushStack myStack %%A

Test if stack is empty by examining the top "attribute"

if myStack.top==0 (echo myStack is empty) else (echo myStack is NOT empty)

Peek at the top stack value

call:peekStack myStack val && echo a peek at the top of myStack shows !val!

Pop the top stack value

call :popStack myStack val && echo popped myStack value=!val!

Push some more values onto the stack

for %%A in (value4 value5 value6) do call :pushStack myStack %%A

Process the remainder of the stack

processStack

call :popStack myStack val || goto :stackEmpty echo popped myStack value=!val! goto :processStack

stackEmpty

Test if stack is empty using the empty "method"/"macro". Use of the

second IF statement serves to demonstrate the negation of the empty

"method". A single IF could have been used with an ELSE clause instead.

if %myStack.empty% echo myStack is empty if not %myStack.empty% echo myStack is NOT empty exit /b

LIFO stack definition

newStack stackName

set /a %~1.top=0

Define an empty "method" for this stack as a sort of macro

set "%~1.empty=^!%~1.top^! == 0" exit /b

pushStack stackName value

set /a %~1.top+=1 set %~1.!%~1.top!=%2 exit /b

popStack stackName returnVar

Sets errorlevel to 0 if success

Sets errorlevel to 1 if failure because stack was empty

if !%~1.top! equ 0 exit /b 1 for %%N in (!%~1.top!) do (

 set %~2=!%~1.%%N!
 set %~1.%%N=

) set /a %~1.top-=1 exit /b 0

peekStack stackName returnVar

Sets errorlevel to 0 if success

Sets errorlevel to 1 if failure because stack was empty

if !%~1.top! equ 0 exit /b 1 for %%N in (!%~1.top!) do set %~2=!%~1.%%N! exit /b 0 </lang>

Bracmat

A stack is easiest implemented as a dotted list top.top-1.top-2.[...].. In the example below we also introduce a 'class' stack, instantiated in the 'object' Stack. The class has a member variable S and methods push,pop, top and empty. As a side note, . is to .. as C's . is to ->. In a method's body, its refers to the object itself. (Analogous to (*this) in C++.) <lang>( ( stack

 =   (S=)
     (push=.(!arg.!(its.S)):?(its.S))
     ( pop
     = top.!(its.S):(%?top.?(its.S))&!top
     )
     (top=top.!(its.S):(%?top.?)&!top)
     (empty=.!(its.S):)
 )

& new$stack:?Stack & (Stack..push)$(2*a) & (Stack..push)$pi & (Stack..push)$ & (Stack..push)$"to be or" & (Stack..push)$"not to be" & out$((Stack..pop)$|"Cannot pop (a)") & out$((Stack..top)$|"Cannot pop (b)") & out$((Stack..pop)$|"Cannot pop (c)") & out$((Stack..pop)$|"Cannot pop (d)") & out$((Stack..pop)$|"Cannot pop (e)") & out$((Stack..pop)$|"Cannot pop (f)") & out$((Stack..pop)$|"Cannot pop (g)") & out$((Stack..pop)$|"Cannot pop (h)") & out

 $ ( str
   $ ( "Stack is "
       ((Stack..empty)$&|not)
       " empty"
     )
   )

& );</lang> Output: <lang>not to be to be or to be or

pi 2*a Cannot pop (g) Cannot pop (h) Stack is empty</lang>

C

Macro expanding to type flexible stack routines. <lang c>#include <stdio.h>

1. include <stdlib.h>

/* to read expanded code, run through cpp | indent -st */

1. define DECL_STACK_TYPE(type, name) \

typedef struct stk_##name##_t{type *buf; size_t alloc,len;}*stk_##name; \ stk_##name stk_##name##_create(size_t init_size) { \ stk_##name s; if (!init_size) init_size = 4; \ s = malloc(sizeof(struct stk_##name##_t)); \ if (!s) return 0; \ s->buf = malloc(sizeof(type) * init_size); \ if (!s->buf) { free(s); return 0; } \ s->len = 0, s->alloc = init_size; \ return s; } \ int stk_##name##_push(stk_##name s, type item) { \ type *tmp; \ if (s->len >= s->alloc) { \ tmp = realloc(s->buf, s->alloc*2*sizeof(type)); \ if (!tmp) return -1; s->buf = tmp; \ s->alloc *= 2; } \ s->buf[s->len++] = item; \ return s->len; } \ type stk_##name##_pop(stk_##name s) { \ type tmp; \ if (!s->len) abort(); \ tmp = s->buf[--s->len]; \ if (s->len * 2 <= s->alloc && s->alloc >= 8) { \ s->alloc /= 2; \ s->buf = realloc(s->buf, s->alloc * sizeof(type));} \ return tmp; } \ void stk_##name##_delete(stk_##name s) { \ free(s->buf); free(s); }

1. define stk_empty(s) (!(s)->len)
2. define stk_size(s) ((s)->len)

DECL_STACK_TYPE(int, int)

int main(void) { int i; stk_int stk = stk_int_create(0);

printf("pushing: "); for (i = 'a'; i <= 'z'; i++) { printf(" %c", i); stk_int_push(stk, i); }

printf("\nsize now: %d", stk_size(stk)); printf("\nstack is%s empty\n", stk_empty(stk) ? "" : " not");

printf("\npoppoing:"); while (stk_size(stk)) printf(" %c", stk_int_pop(stk)); printf("\nsize now: %d", stk_size(stk)); printf("\nstack is%s empty\n", stk_empty(stk) ? "" : " not");

/* stk_int_pop(stk); <-- will abort() */ stk_int_delete(stk); return 0; }</lang>

Or

<lang c>#include <stdio.h>

1. include <stdlib.h>
2. include <stddef.h>
3. include <stdbool.h>

1. define check_pointer(p) if (!p) {puts("Out of memory."); exit(EXIT_FAILURE);}

1. define MINIMUM_SIZE 1

/* Minimal stack size (expressed in number of elements) for which
space is allocated. It should be at least 1. */

1. define GROWTH_FACTOR 2

/* How much more memory is allocated each time a stack grows
out of its allocated segment. */

typedef int T;

// The type of the stack elements.

typedef struct

{T *bottom;
 T *top;
 T *allocated_top;} stack;

stack * new(void) /* Creates a new stack. */

{stack *s = malloc(sizeof(stack));
 check_pointer(s);
 s->bottom = malloc(MINIMUM_SIZE * sizeof(T));
 check_pointer(s->bottom);
 s->top = s->bottom - 1;
 s->allocated_top = s->bottom + MINIMUM_SIZE - 1;
 return s;}

void destroy(stack *s) /* Frees all the memory used for a stack. */

{free(s->bottom);
 free(s);}

bool empty(stack *s) /* Returns true iff there are no elements on the stack. This is different from the stack not having enough memory reserved for even one element, which case is never allowed to arise. */

{return s->top < s->bottom ? true : false;}

void push(stack *s, T x) /* Puts a new element on the stack, enlarging the latter's memory allowance if necessary. */

{if (s->top == s->allocated_top)
    {ptrdiff_t qtty = s->top - s->bottom + 1;
     ptrdiff_t new_qtty = GROWTH_FACTOR * qtty;
     s->bottom = realloc(s->bottom, new_qtty * sizeof(T));
     check_pointer(s->bottom);
     s->top = s->bottom + qtty - 1;
     s->allocated_top = s->bottom + new_qtty - 1;}
 *(++s->top) = x;}

T pop(stack *s) /* Removes and returns the topmost element. The result of popping an empty stack is undefined. */

{return *(s->top--);}

void compress(stack *s) /* Frees any memory the stack isn't actually using. The allocated portion still isn't allowed to shrink smaller than MINIMUM_SIZE. If all the stack's memory is in use, nothing happens. */

{if (s->top == s->allocated_top) return;
 ptrdiff_t qtty = s->top - s->bottom + 1;
 if (qtty < MINIMUM_SIZE) qtty = MINIMUM_SIZE;
 size_t new_size = qtty * sizeof(T);
 s->bottom = realloc(s->bottom, new_size);
 check_pointer(s->bottom);
 s->allocated_top = s->bottom + qtty - 1;}</lang>

C#

<lang csharp>// Non-Generic Stack System.Collections.Stack stack = new System.Collections.Stack(); stack.Push( obj ); bool isEmpty = stack.Count == 0; object top = stack.Peek(); // Peek without Popping. top = stack.Pop();

// Generic Stack System.Collections.Generic.Stack<Foo> stack = new System.Collections.Generic.Stack<Foo>(); stack.Push(new Foo()); bool isEmpty = stack.Count == 0; Foo top = stack.Peek(); // Peek without Popping. top = stack.Pop();</lang>

C++

Library: STL

The C++ standard library already provides a ready-made stack class. You get it by writing

<lang cpp>#include <stack></lang>

and then using the std::stack 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):

<lang cpp>#include <deque> template <class T, class Sequence = std::deque<T> > class stack {

 friend bool operator== (const stack&, const stack&);
 friend bool operator<  (const stack&, const stack&);

public:

 typedef typename Sequence::value_type      value_type;
 typedef typename Sequence::size_type       size_type;
 typedef          Sequence                  container_type;
 typedef typename Sequence::reference       reference;
 typedef typename Sequence::const_reference const_reference;

protected:

 Sequence seq;

public:

 stack() : seq() {}
 explicit stack(const Sequence& s0) : seq(s0) {}
 bool empty() const { return seq.empty(); }
 size_type size() const { return seq.size(); }
 reference top() { return seq.back(); }
 const_reference top() const { return seq.back(); }
 void push(const value_type& x) { seq.push_back(x); }
 void pop() { seq.pop_back(); }

};

template <class T, class Sequence> bool operator==(const stack<T,Sequence>& x, const stack<T,Sequence>& y) {

 return x.seq == y.seq;

} template <class T, class Sequence> bool operator<(const stack<T,Sequence>& x, const stack<T,Sequence>& y) {

 return x.seq < y.seq;

}

template <class T, class Sequence> bool operator!=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) {

 return !(x == y);

} template <class T, class Sequence> bool operator>(const stack<T,Sequence>& x, const stack<T,Sequence>& y) {

 return y < x;

} template <class T, class Sequence> bool operator<=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) {

 return !(y < x);

} template <class T, class Sequence> bool operator>=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) {

 return !(x < y);

}</lang>

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.

<lang lisp>(deftype Stack [elements])

(def stack (Stack (ref ())))

(defn push-stack

 "Pushes an item to the top of the stack."
 [x] (dosync (alter (:elements stack) conj x)))

(defn pop-stack

 "Pops an item from the top of the stack."
 [] (let [fst (first (deref (:elements stack)))] 
      (dosync (alter (:elements stack) rest)) fst))

(defn top-stack

 "Shows what's on the top of the stack."
 [] (first (deref (:elements stack))))

(defn empty-stack?

 "Tests whether or not the stack is empty."
 [] (= () (deref (:elements stack))))</lang>

We can make this a bit smaller and general by using defprotocol along with deftype. Here is a revised version using defprotocol.

<lang lisp> (defprotocol StackOps

 (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.")
 (top-stack [this] "Shows what's on the top of the stack.")
 (empty-stack? [this] "Tests whether or not the stack is empty."))

(deftype Stack [elements]

 StackOps
  (push-stack [x] (dosync (alter elements conj x)))
  (pop-stack [] (let [fst (first (deref elements))]

(dosync (alter elements rest)) fst))

  (top-stack [] (first (deref elements)))
  (empty-stack? [] (= () (deref elements))))

(def stack (Stack (ref ())))</lang>

CoffeeScript

<lang CoffeeScript> stack = [] stack.push 1 stack.push 2 console.log stack console.log stack.pop() console.log stack </lang>

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.

<lang lisp>(defstruct stack

 elements)

(defun stack-push (element stack)

 (push element (stack-elements stack)))

(defun stack-pop (stack)(deftype Stack [elements])

(defun stack-empty (stack)

 (endp (stack-elements stack)))

(defun stack-top (stack)

 (first (stack-elements stack)))

(defun stack-peek (stack)

 (stack-top stack))</lang>

D

Stack class implemented using a dynamic array. <lang d>class Stack(T) {

   private T[] content;

   void push(T top) { content ~= top; }

   T pop() {
       if (empty)
           throw new Exception("Stack Empty");
       T top = content[$ - 1];
       content.length -= 1;
       return top;
   }

   bool empty() { return content.length == 0; }

}

void main() {

   auto s = new Stack!int();
   s.push(10);
   s.push(20);
   assert(s.pop() == 20);
   assert(s.pop() == 10);
   assert(s.empty());

}</lang>

Delphi

<lang Delphi>program Stack;

{$APPTYPE CONSOLE}

uses Generics.Collections;

var

 lStack: TStack<Integer>;

begin

 lStack := TStack<Integer>.Create;
 try
   lStack.Push(1);
   lStack.Push(2);
   lStack.Push(3);
   Assert(lStack.Peek = 3); // 3 should be at the top of the stack

   Writeln(lStack.Pop); // 3
   Writeln(lStack.Pop); // 2
   Writeln(lStack.Pop); // 1
   Assert(lStack.Count = 0); // should be empty
 finally
   lStack.Free;
 end;

end.</lang>

E

The standard FlexList data structure provides operations for use as a stack.

<lang e>? def l := [].diverge()

1. value: [].diverge()

? l.push(1) ? l.push(2) ? l

1. value: [1, 2].diverge()

? l.pop()

1. value: 2

? l.size().aboveZero()

1. value: true

? l.last()

1. value: 1

? l.pop()

1. value: 1

? l.size().aboveZero()

1. value: false</lang>

Here's a stack implemented out of a reference to a linked list:

<lang e>def makeStack() {

   var store := null
   def stack {
       to push(x) { store := [x, store] }
       to pop() { def [x, next] := store; store := next; return x }
       to last() { return store[0] }
       to empty() { return (store == null) }
   }
   return stack

}

? def s := makeStack()

1. value: <stack>

? s.push(1) ? s.push(2) ? s.last()

1. value: 2

? s.pop()

1. value: 2

? s.empty()

1. value: false

? s.pop()

1. value: 1

? s.empty()

1. value: true</lang>

Elisa

This is a generic Stack component based on arrays. See how in Elisa generic components are defined. <lang Elisa >

component GenericStack ( Stack, Element );
type Stack;
     Stack (MaxSize = integer) -> Stack;
     Empty ( Stack )           -> boolean;
     Full ( Stack )            -> boolean;
     Push ( Stack, Element)    -> nothing;
     Pull ( Stack )            -> Element;

begin

     Stack(MaxSize) =
            Stack:[ MaxSize; index:=0; area=array (Element, MaxSize) ];
     Empty( stack ) = (stack.index <= 0);
     Full ( stack ) = (stack.index >= stack.MaxSize);
     Push ( stack, element ) = 
                  [ exception (Full (stack), "Stack Overflow");
                    stack.index:=stack.index + 1; 
                    stack.area[stack.index]:=element ];
     Pull ( stack ) = 
                  [ exception (Empty (stack), "Stack Underflow");
                    stack.index:=stack.index - 1; 
                    stack.area[stack.index + 1] ];

end component GenericStack; </lang > Another example of a generic Stack component is based on an unlimited sequence. A sequence is a uni-directional list. See how Elisa defines sequences. The component has the same interface as the array based version. <lang Elisa> component GenericStack ( Stack, ElementType );

type Stack;
     Stack(MaxSize = integer)  -> Stack;
     Empty( Stack )            -> boolean;
     Full ( Stack )            -> boolean;
     Push ( Stack, ElementType)-> nothing;
     Pull ( Stack )            -> ElementType;

begin

     type sequence = term;
     ElementType & sequence => sequence;
     nil = null (sequence);

     head (sequence) -> ElementType;
     head (X & Y) = ElementType:X;

     tail (sequence) -> sequence;
     tail (X & Y) = Y;

     Stack (Size) = Stack:[ list = nil ];
     Empty ( stack ) = (stack.list == nil);
     Full ( stack ) = false;
     Push ( stack, ElementType ) = [ stack.list:= ElementType & stack.list ];
     Pull ( stack ) = [ exception (Empty (stack), "Stack Underflow");
                        Head = head(stack.list); stack.list:=tail(stack.list); Head];

end component GenericStack; </lang > Both versions give the same answers to the following tests: <lang Elisa> use GenericStack (StackofBooks, Book); type Book = text; BookStack = StackofBooks(50);

Push (BookStack, "Peter Pan"); Push (BookStack, "Alice in Wonderland");

Pull (BookStack)? "Alice in Wonderland"

Pull (BookStack)? "Peter Pan"

Pull (BookStack)?

• • • • • Exception: Stack Underflow

</lang>

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: <lang erlang>-module(stack). -export([empty/1, new/0, pop/1, push/2, top/1]).

new() -> [].

empty([]) -> true; empty(_) -> false.

pop([H|T]) -> {H,T}.

push(H,T) -> [H|T].

top([H|_]) -> H.</lang>

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: <lang erlang>1> c(stack). {ok,stack} 2> Stack = stack:new(). [] 3> NewStack = lists:foldl(fun stack:push/2, Stack, [1,2,3,4,5]). [5,4,3,2,1] 4> stack:top(NewStack). 5 5> {Popped, PoppedStack} = stack:pop(NewStack). {5,[4,3,2,1]} 6> stack:empty(NewStack). false 7> stack:empty(stack:new()). true</lang>

Factor

Factor is a stack based language, but also provides stack "objects", because all resizable sequences can be treated as stacks (see docs). Typically, a vector is used:

V{ 1 2 3 } {
[ 6 swap push ]
[ "hi" swap push ]
[ "Vector is now: " write . ]
[ "Let's pop it: " write pop . ]
[ "Vector is now: " write . ]
[ "Top is: " write last . ] } cleave

Vector is now: V{ 1 2 3 6 "hi" }
Let's pop it: "hi"
Vector is now: V{ 1 2 3 6 }
Top is: 6

Forth

<lang forth>: stack ( size -- )

 create here cell+ ,  cells allot ;

push ( n st -- ) tuck @ ! cell swap +! ;

pop ( st -- n ) -cell over +! @ @ ;

empty? ( st -- ? ) dup @ - cell+ 0= ;

10 stack st

1 st push 2 st push 3 st push st empty? . \ 0 (false) st pop . st pop . st pop . \ 3 2 1 st empty? . \ -1 (true)</lang>

Fortran

This solution can easily be adapted to data types other than integer.

<lang fortran> module stack

 public

 ! Define the data-structure to hold the data
 type stack_var
    integer, allocatable :: data(:)
    integer              :: size = 0
 end type stack_var

 ! Set the size of allocated memory blocks
 integer, parameter, private :: block_size = 10

contains

 ! Push ----------------------------------------------------------------------
 subroutine push(s, e)
   type(stack_var), intent(inout) :: s
   integer, intent(in)            :: e
   integer, allocatable :: wk(:)
   if (.not. allocated(s%data)) then
      ! Allocate space if not yet done
      allocate(s%data(block_size))

   elseif (s%size == size(s%data)) then
      ! Grow the allocated space
      allocate(wk(size(s%data)+block_size))
      wk(1:s%size) = s%data
      call move_alloc(wk,s%data)

   end if

   ! Store the data in the stack
   s%size = s%size + 1
   s%data(s%size) = e
 end subroutine push

 ! Pop -----------------------------------------------------------------------
 function pop(s)
   integer :: pop
   type(stack_var), intent(inout) :: s
   if (s%size == 0 .or. .not. allocated(s%data)) then
      pop = 0
      return
   end if
   pop = s%data(s%size)
   s%size = s%size - 1
 end function pop

 ! Peek ----------------------------------------------------------------------
 integer function peek(s)
   type(stack_var), intent(inout) :: s
   if (s%size == 0 .or. .not. allocated(s%data)) then
      peek = 0
      return
   end if
   peek = s%data(s%size)
 end function peek

 ! Empty ---------------------------------------------------------------------
 logical function empty(s)
   type(stack_var), intent(inout) :: s
   empty = (s%size == 0 .or. .not. allocated(s%data))
 end function empty

end module stack

program tstack

 use stack
 implicit none
 type(stack_var) :: s
 integer         :: v

 call push(s,1)
 call push(s,2)
 call push(s,3)
 call push(s,4)

 do
    if (empty(s)) exit
    v = pop(s)
    write(*,'(a,i0)') 'Popped value off stack = ',v
 end do

end program tstack </lang>

F#

.NET provides a mutable stack type in System.Collections.Generic.Stack.

A list-based immutable stack type could be implemented like this: <lang fsharp>type Stack<'a> //'//(workaround for syntax highlighting problem)

 (?items) =
 let items = defaultArg items []

 member x.Push(A) = Stack(A::items)

 member x.Pop() =
   match items with
     | x::xr ->  (x, Stack(xr))
     | [] -> failwith "Stack is empty."

 member x.IsEmpty() = items = []

// example usage let anEmptyStack = Stack<int>() let stack2 = anEmptyStack.Push(42) printfn "%A" (stack2.IsEmpty()) let (x, stack3) = stack2.Pop() printfn "%d" x printfn "%A" (stack3.IsEmpty())</lang>

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, <lang go>var intStack []int</lang> Use the built in append function to push numbers on the stack: <lang go>intStack = append(intStack, 7)</lang> Use a slice expression with the built in len function to pop from the stack: <lang go>popped, intStack = intStack[len(intStack)-1], intStack[:len(intStack)-1]</lang> The test for an empty stack: <lang go>len(intStack) == 0</lang> And to peek at the top of the stack: <lang go>intStack[len(intStack)-1]</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. <lang go>package main

import "fmt"

type stack []interface{}

func (k *stack) push(s interface{}) {

   *k = append(*k, s)

}

func (k *stack) pop() (s interface{}, ok bool) {

   if k.empty() {
       return
   }
   last := len(*k) - 1
   s = (*k)[last]
   *k = (*k)[:last]
   return s, true

}

func (k *stack) peek() (s interface{}, ok bool) {

   if k.empty() {
       return
   }
   last := len(*k) - 1
   s = (*k)[last]
   return s, true

}

func (k *stack) empty() bool {

   return len(*k) == 0

}

func main() {

   var s stack
   fmt.Println("new stack:", s)
   fmt.Println("empty?", s.empty())
   s.push(3)
   fmt.Println("push 3. stack:", s)
   fmt.Println("empty?", s.empty())
   s.push("four")
   fmt.Println(`push "four" stack:`, s)
   if top, ok := s.peek(); ok {
       fmt.Println("top value:", top)
   } else {
       fmt.Println("nothing on stack")
   }
   if popped, ok := s.pop(); ok {
       fmt.Println(popped, "popped.  stack:", s)
   } else {
       fmt.Println("nothing to pop")
   }

}</lang> Output:

new stack: []
empty? true
push 3. stack: [3]
empty? false
push "four" stack: [3 four]
top value: four
four popped.  stack: [3]

Groovy

In Groovy, all lists have stack semantics, including "push()" and "pop()" methods, an "empty" property, and a "last()" method as a stand-in for "top/peek" semantics. Calling "pop()" on an empty list throws an exception.

Of course, these stack semantics are not exclusive. Elements of the list can still be accessed and manipulated in myriads of other ways.

<lang groovy>def stack = [] assert stack.empty

stack.push(55) stack.push(21) stack.push('kittens') assert stack.last() == 'kittens' assert stack.size() == 3 assert ! stack.empty

println stack

assert stack.pop() == "kittens" assert stack.size() == 2

println stack

stack.push(-20)

println stack

stack.push( stack.pop() * stack.pop() ) assert stack.last() == -420 assert stack.size() == 2

println stack

stack.push(stack.pop() / stack.pop()) assert stack.size() == 1

println stack

println stack.pop() assert stack.size() == 0 assert stack.empty

try { stack.pop() } catch (NoSuchElementException e) { println e.message }</lang>

Output:

[55, 21, kittens]
[55, 21]
[55, 21, -20]
[55, -420]
[-7.6363636364]
-7.6363636364
Cannot pop() an empty List

Haskell

The Haskell solution is trivial, using a list. Note that pop returns both the element and the changed stack, to remain purely functional.

<lang haskell>type Stack a = [a]

create :: Stack a create = []

push :: a -> Stack a -> Stack a push = (:)

pop :: Stack a -> (a, Stack a) pop [] = error "Stack empty" pop (x:xs) = (x,xs)

empty :: Stack a -> Bool empty = null

peek :: Stack a -> a peek [] = error "Stack empty" peek (x:_) = x</lang>

We can make a stack that can be destructively popped by hiding the list inside a State monad.

<lang haskell>import Control.Monad.State

type Stack a b = State [a] b

push :: a -> Stack a () push = modify . (:)

pop :: Stack a a pop = do

   nonEmpty
   x <- peek
   modify tail
   return x

empty :: Stack a Bool empty = gets null

peek :: Stack a a peek = nonEmpty >> gets head

nonEmpty :: Stack a () nonEmpty = empty >>= flip when (fail "Stack empty")</lang>

Icon and Unicon

Stacks (and double ended queues) are built into Icon and Unicon as part of normal list access. In addition to 'push' and 'pop', there are the functions 'put', 'get' (alias for pop), 'pull', list element addressing, and list sectioning (like sub-strings). Unicon extended 'insert' and 'delete' to work with lists. The programmer is free to use any or all of the list processing functions on any problem. The following illustrates typical stack usage: <lang Icon>procedure main() stack := [] # new empty stack push(stack,1) # add item push(stack,"hello",table(),set(),[],5) # add more items of mixed types in order left to right y := top(stack) # peek x := pop(stack) # remove item write("The stack is ",if isempty(stack) then "empty" else "not empty") end

procedure isempty(x) #: test if a datum is empty, return the datum or fail (task requirement) if *x = 0 then return x # in practice just write *x = 0 or *x ~= 0 for is/isn't empty end

procedure top(x) #: return top element w/o changing stack return x[1] # in practice, just use x[1] end</lang>

Io

aside from using built-in lists, a stack can be created using nodes like so: <lang io> Node := Object clone do(

   next := nil
   obj := nil

)

Stack := Object clone do(

   node := nil
   
   pop := method(
       obj := node obj
       node = node next
       obj
   )
   
   push := method(obj,
       nn := Node clone
       nn obj = obj
       nn next = self node
       self node = nn
   )

) </lang>

Ioke

<lang ioke>Stack = Origin mimic do(

 initialize = method(@elements = [])
 pop = method(@elements pop!)
 empty = method(@elements empty?)
 push = method(element, @elements push!(element))

)</lang>

J

<lang J> stack=: push=: monad def '0$stack=:stack,y' pop=: monad def 'r[ stack=:}:stack[ r=.{:stack' empty=: monad def '0=#stack'</lang>

Example use:

<lang J> push 9

  pop 

9

  empty 

1</lang>

pop and empty ignore their arguments. In this implementation. push returns an empty list.

Java

<lang java>public class Stack{

   private Node first = null;
   public boolean isEmpty(){
       return first == null;
   }
   public Object Pop(){
       if(isEmpty()) 
           throw new Exception("Can't Pop from an empty Stack.");
       else{
           Object temp = first.value;
           first = first.next;
           return temp;
       }
   }
   public void Push(Object o){
       first = new Node(o, first);
   }
   class Node{
       public Node next;
       public Object value;
       public Node(Object value){
           this(value, null); 
       }
       public Node(Object value, Node next){
           this.next = next;
           this.value = value;
       }
   }

}</lang>

Works with: Java version 1.5

<lang java5>public class Stack<T>{

   private Node first = null;
   public boolean isEmpty(){
       return first == null;
   }
   public T Pop(){
       if(isEmpty()) 
           throw new Exception("Can't Pop from an empty Stack.");
       else{
           T temp = first.value;
           first = first.next;
           return temp;
       }
   }
   public void Push(T o){
       first = new Node(o, first);
   }
   class Node{
       public Node next;
       public T value;
       public Node(T value){
           this(value, null); 
       }
       public Node(T value, Node next){
           this.next = next;
           this.value = value;
       }
   }

}</lang>

JavaScript

The built-in Array class already has stack primitives. <lang javascript>var stack = []; stack.push(1) stack.push(2,3); print(stack.pop()); // 3 print(stack.length); // 2, stack empty if 0</lang> Here's a constructor that wraps the array: <lang javascript>function Stack() {

   this.data = new Array();

   this.push  = function(element) {this.data.push(element)}
   this.pop   = function() {return this.data.pop()}
   this.empty = function() {return this.data.length == 0}
   this.peek  = function() {return this.data[0]}

}</lang>

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. <lang logo>make "stack [] push "stack 1 push "stack 2 push "stack 3 print pop "stack  ; 3 print empty? :stack ; false</lang>

Lua

Tables have stack primitives by default:

<lang lua> stack = {} table.insert(stack,3) print(table.remove(stack)) --> 3</lang>

Mathematica

<lang Mathematica>EmptyQ[a_] := If[Length[a] == 0, True, False] SetAttributes[Push, HoldAll];[a_, elem_] := AppendTo[a, elem] SetAttributes[Pop, HoldAllComplete]; Pop[a_] := If[EmptyQ[a], False, b = Last[a]; Set[a, Most[a]]; b] Peek[a_] := If[EmptyQ[a], False, Last[a]]

Example use: stack = {};Push[stack, 1]; Push[stack, 2]; Push[stack, 3]; Push[stack, 4]; Peek[stack] ->4 Pop[stack] ->4 Peek[stack] ->3</lang>

MATLAB / Octave

Here is a simple implementation of a stack, that works in Matlab and Octave. It is closely related to the queue/fifo example. <lang matlab>mystack = {};

% push mystack{end+1} = x;

%pop x = mystack{end}; mystack{end} = [];

%peek,top x = mystack{end};

% empty isempty(mystack)</lang>

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. <lang MATLAB>%This class impliments a standard LIFO queue. classdef LIFOQueue

   properties  
       queue
   end
   
   methods
        
       %Class constructor
       function theQueue = LIFOQueue(varargin)
           
           if isempty(varargin) %No input arguments
               
               %Initialize the queue state as empty
               theQueue.queue = {};
           elseif (numel(varargin) > 1) %More than 1 input arg
               
               %Make the queue the list of input args
               theQueue.queue = varargin;
           elseif iscell(varargin{:}) %If the only input is a cell array
               
               %Make the contents of the cell array the elements in the queue 
               theQueue.queue = varargin{:};
           else %There is one input argument that is not a cell
               
               %Make that one arg the only element in the queue
               theQueue.queue = varargin;
           end
           
       end        
       
       %push() - pushes a new element to the end of the queue
       function push(theQueue,varargin)
           
           if isempty(varargin)
               theQueue.queue(end+1) = {[]};
           elseif (numel(varargin) > 1) %More than 1 input arg
               
               %Make the queue the list of input args
               theQueue.queue( end+1:end+numel(varargin) ) = varargin;
           elseif iscell(varargin{:}) %If the only input is a cell array
               
               %Make the contents of the cell array the elements in the queue 
               theQueue.queue( end+1:end+numel(varargin{:}) ) = varargin{:};
           else %There is one input argument that is not a cell
               
               %Make that one arg the only element in the queue
               theQueue.queue{end+1} = varargin{:};                
           end
           
           %Makes changes to the queue permanent
           assignin('caller',inputname(1),theQueue);  
           
       end
       
       %pop() - pops the first element off the queue
       function element = pop(theQueue)
          
           if empty(theQueue)
               error 'The queue is empty'
           else
               %Returns the first element in the queue
               element = theQueue.queue{end};
               
               %Removes the first element from the queue
               theQueue.queue(end) = [];
               
               %Makes changes to the queue permanent
               assignin('caller',inputname(1),theQueue);
           end
       end
       
       %empty() - Returns true if the queue is empty
       function trueFalse = empty(theQueue)
          
           trueFalse = isempty(theQueue.queue);
           
       end
       
   end %methods

end</lang>

Sample Usage: <lang MATLAB>>> myLIFO = LIFOQueue(1,'fish',2,'fish','red fish','blue fish')

myLIFO =

LIFOQueue

>> myLIFO.pop()

ans =

blue fish

>> myLIFO.push('Cat Fish') >> myLIFO.pop()

ans =

Cat Fish

>> myLIFO.pop()

ans =

red fish

>> empty(myLIFO)

ans =

    0</lang>

Objeck

Class library support for Stack/IntStack/FloatStack <lang objeck> stack := IntStack->New(); stack->Push(13); stack->Push(7); (stack->Pop() + stack->Pop())->PrintLine(); stack->IsEmpty()->PrintLine(); </lang>

Objective-C

Using a NSMutableArray: <lang objc>NSMutableArray *stack = [NSMutableArray array]; // creating

[stack addObject:value]; // pushing

id value = [stack lastObject]; [stack removeLastObject]; // popping

[stack count] == 0 // is empty?</lang>

OCaml

Implemented as a singly-linked list, wrapped in an object: <lang ocaml>exception Stack_empty

class ['a] stack =

 object (self)
   val mutable lst : 'a list = []

   method push x =
    lst <- x::lst

   method pop =
     match lst with
       []    -> raise Stack_empty
     | x::xs -> lst <- xs;
                x

   method is_empty =
     lst = []
 end</lang>

Oz

A thread-safe, list-based stack. Implemented as a module: <lang oz>functor export

  New
  Push
  Pop
  Empty

define

  fun {New}
     {NewCell nil}
  end

  proc {Push Stack Element}
     NewStack
     %% Use atomic swap for thread safety
     OldStack = Stack := NewStack
  in
     NewStack = Element|OldStack
  end

  proc {Pop Stack ?Result}
     NewStack
     %% Use atomic swap for thread safety
     OldStack = Stack := NewStack
  in
     Result|NewStack = OldStack
  end
  
  fun {Empty Stack}
     @Stack == nil
  end

end</lang>

There is also a stack implementation in the standard library.

PARI/GP

<lang parigp>push(x)=v=concat(v,[x]);; pop()={

 if(#v,
   my(x=v[#v]);
   v=vecextract(v,1<<(#v-1)-1);
   x
 ,
   error("Stack underflow")
 )

}; empty()=v==[]; peek()={

 if(#v,
   v[#v]
 ,
   error("Stack underflow")
 )

};</lang>

Pascal

This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects). <lang pascal>{ tStack is the actual stack type, tStackNode a helper type } type

 pStackNode = ^tStackNode;
 tStackNode = record
               next: pStackNode;
               data: integer;
              end;
 tStack = record
           top: pStackNode;
          end;

{ Always call InitStack before using a stack } procedure InitStack(var stack: tStack);

begin
 stack.top := nil
end;

{ This function removes all content from a stack; call before disposing, or before a local stack variable goes out of scope } procedure ClearStack(var stack: tStack);

var
 node: pStackNode;
begin
 while stack.top <> nil do
  begin
   node := stack.top;
   stack.top := stack.top^.next;
   dispose(node);
  end
end;

function StackIsEmpty(stack: tStack):Boolean;

begin
 StackIsEmpty := stack.top = nil
end;

procedure PushToStack(var stack: tStack; value: integer);

var
 node: pStackNode;
begin
 new(node);
 node^.next := stack.top;
 node^.data := value;
 stack.top := node
end;

{ may only be called on a non-empty stack! } function PopFromStack(var stack: tStack): integer;

var
 node: pStackNode;
begin
 node := stack.top;
 stack.top := node^.next;
 PopFromStack := node^.data;
 dispose(node);
end;</lang>

Perl

Perl comes prepared to treat its lists as stacks, giving us the push and pop functions for free. To add empty, we basically give a new name to "not":

<lang perl>sub empty{ not @_ }</lang>

Perl 6

Perl 6 still has the stack functions from Perl 5, but now they also can be accessed by object notation:

<lang perl6>my @stack; # just a array @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</lang>

PHP

PHP arrays behave like a stack: <lang php>$stack = array();

empty( $stack ); // true

array_push( $stack, 1 ); // or $stack[] = 1; array_push( $stack, 2 ); // or $stack[] = 2;

empty( $stack ); // false

echo array_pop( $stack ); // outputs "2" echo array_pop( $stack ); // outputs "1"</lang>

PicoLisp

The built-in functions push and pop are used to maintain a stack (of any type). <lang PicoLisp>(push 'Stack 3) (push 'Stack 2) (push 'Stack 1)</lang>

: Stack
-> (1 2 3)

: (pop 'Stack)
-> 1

: Stack
-> (2 3)

: (set 'Stack)  # empty
-> NIL

: Stack
-> NIL

PL/I

<lang PL/I> /* Any controlled variable may behave as a stack. */

declare s float controlled;

/* to push a value on the stack. */ allocate s; s = 10;

/* To pop a value from the stack. */ put (s); free s;

/* to peek at the top of stack> */ put (s);

/* To see whether the stack is empty */ if allocation(s) = 0 then ...

/* Note: popping a value from the stack, or peeking, */ /* would usually require a check that the stack is not empty. */

/* Note: The above is a simple stack for S. */ /* S can be any kind of data structure, an array, etc. */

/* Example to push ten values onto the stack, and then to */ /* remove them. */

/* Push ten values, obtained from the input, onto the stack: */ declare S float controlled; do i = 1 to 10;

  allocate s;
  get list (s);

end; /* To pop those values from the stack: */ do while (allocation(s) > 0);

  put skip list (s);
  free s;

end; /* The values are printed in the reverse order, of course. */ </lang>

PostScript

Library: initlib

<lang postscript> % empty? is already defined. /push {exch cons}. /pop {uncons exch pop}. [2 3 4 5 6] 1 push = [1 2 3 4 5 6] [1 2 3 4 5 6] pop =[2 3 4 5 6] [2 3 4 5 6] empty? =false [] empty? =true </lang>

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:

<lang prolog>% push( ELEMENT, STACK, NEW ) % True if NEW is [ELEMENT|STACK] push(ELEMENT,STACK,[ELEMENT|STACK]).

% pop( STACK, TOP, NEW ) % True if TOP and NEW are head and tail, respectively, of STACK pop([TOP|STACK],TOP,STACK).

% empty( STACK ) % True if STACK is empty empty([]).</lang>

PureBasic

For LIFO function PureBasic normally uses linked lists. Usage as described above could look like; <lang PureBasic>Global NewList MyStack()

Procedure Push_LIFO(n)

 FirstElement(MyStack())
 InsertElement(MyStack())
 MyStack() = n

EndProcedure

Procedure Pop_LIFO()

 If FirstElement(MyStack())
   Topmost = MyStack()
   DeleteElement(MyStack())
 EndIf
 ProcedureReturn Topmost

EndProcedure

Procedure Empty_LIFO()

 Protected Result
 If ListSize(MyStack())=0
   Result = #True
 EndIf
 ProcedureReturn Result

EndProcedure

Procedure Peek_LIFO()

 If FirstElement(MyStack())
   Topmost = MyStack()
 EndIf
 ProcedureReturn Topmost

EndProcedure

---- Example of implementation ----

Push_LIFO(3) Push_LIFO(1) Push_LIFO(4) While Not Empty_LIFO()

 Debug Pop_LIFO()

Wend</lang>

Outputs

4
1
3

Python

Works with: Python version 2.5

The faster and Pythonic way is using a deque (available from 2.4). A regular list is a little slower.

<lang python>from collections import deque stack = deque() stack.append(value) # pushing value = stack.pop() not stack # is empty?</lang>

If you need to expose your stack to the world, you may want to create a simpler wrapper:

<lang python>from collections import deque

class Stack:

   def __init__(self):
       self._items = deque()
   def append(self, item):
       self._items.append(item)
   def pop(self):
       return self._items.pop()
   def __nonzero__(self):
       return bool(self._items)</lang>

Here is a stack implemented as linked list - with the same list interface.

<lang python>class Stack:

   def __init__(self):
       self._first = None
   def __nonzero__(self):
       return self._first is not None 
   def append(self, value):
       self._first = (value, self._first)
   def pop(self):
       if self._first is None:
           raise IndexError, "pop from empty stack"
       value, self._first = self._first
       return value</lang>

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: <lang python>while not stack.empty():</lang> You can write: <lang python>while stack:</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.

R

Library: proto

See FIFO for functional and object oriented implementations of a First-In-First-Out object, with similar code. <lang R>library(proto)

stack <- proto(expr = {

  l <- list()
  empty <- function(.) length(.$l) == 0
  push <- function(., x) 
  {
     .$l <- c(list(x), .$l)
     print(.$l)
     invisible()
  }
  pop <- function(.) 
  {
     if(.$empty()) stop("can't pop from an empty list")
     .$l1 <- NULL
     print(.$l)
     invisible()
  }

})

stack$empty()

1. [1] TRUE

stack$push(3)

1. 1
2. [1] 3

stack$push("abc")

1. 1
2. [1] "abc"
3. 2
4. [1] 3

stack$push(matrix(1:6, nrow=2))

1. 1
2. [,1] [,2] [,3]
3. [1,] 1 3 5
4. [2,] 2 4 6
5. 2
6. [1] "abc"
7. 3
8. [1] 3

stack$empty()

1. [1] FALSE

stack$pop()

1. 1

[1] "abc"

1. 2
2. [1] 3

stack$pop()

1. 1
2. [1] 3

stack$pop()

1. list()

stack$pop()

1. Error in get("pop", env = stack, inherits = TRUE)(stack, ...) :
2. can't pop from an empty list</lang>

Raven

Use built in stack type:

<lang raven>new stack as s 1 s push s pop</lang>

Word empty is also built in:

<lang raven>s empty if 'stack is empty' print</lang>

REBOL

<lang rebol>REBOL [ Title: "Stack" Author: oofoe Date: 2010-10-04 URL: http://rosettacode.org/wiki/Stack ]

stack: make object! [ data: copy []

push: func [x][append data x] pop: func [/local x][x: last data remove back tail data x] empty: does [empty? data]

peek: does [last data] ]

Teeny Tiny Test Suite

assert: func [code][print [either do code [" ok"]["FAIL"] mold code]]

print "Simple integers:" s: make stack [] s/push 1 s/push 2 ; Initialize.

assert [2 = s/peek] assert [2 = s/pop] assert [1 = s/pop] assert [s/empty]

print [lf "Symbolic data on stack:"] v: make stack [data: [this is a test]] ; Initialize on instance.

assert ['test = v/peek] assert ['test = v/pop] assert ['a = v/pop] assert [not v/empty] </lang>

Sample run:

Simple integers:
  ok [2 = s/peek]
  ok [2 = s/pop]
  ok [1 = s/pop]
  ok [s/empty]

Symbolic data on stack:
  ok ['test = v/peek]
  ok ['test = v/pop]
  ok ['a = v/pop]
  ok [not v/empty]

Retro

<lang Retro>: stack ( n"- ) create 0 , allot ;

push ( na- ) dup ++ dup @ + ! ;

pop ( a-n ) dup @ over -- + @ ;

top ( a-n ) dup @ + @ ;

empty? ( a-f ) @ 0 = ;

10 stack st

1 st push 2 st push 3 st push st empty? putn st top putn st pop putn st pop putn st pop putn st empty? putn</lang>

REXX

<lang rexx> y=123 /*define a REXX variable, value is 123 */

push y /*pushes 123 onto the stack. */

pull g /*pops last value stacked & removes it. */

q=empty() /*invokes the EMPTY subroutine (below)*/

exit

empty: return queued() /*subroutine returns # of stacked items.*/ </lang>

Ruby

Using an Array, there are already methods Array#push, Array#pop and Array#empty?.

<lang ruby>stack = [] stack.push(value) # pushing value = stack.pop # popping stack.empty? # is empty?</lang>

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.

<lang ruby>require 'forwardable'

1. A stack contains elements in last-in, first-out order.
2. Stack#push adds new elements to the top of the stack;
3. Stack#pop removes elements from the top.

class Stack

 extend Forwardable

 # Creates a Stack containing _objects_.
 def self.[](*objects)
   new.push(*objects)
 end

 # Creates an empty Stack.
 def initialize
   @ary = []
 end

 # Duplicates a Stack.
 def initialize_copy(obj)
   super
   @ary = @ary.dup
 end

 # Adds each object to the top of this Stack. Returns self.
 def push(*objects)
   @ary.push(*objects)
   self
 end
 alias << push

 ##
 # :method: pop
 # :call-seq:
 #   pop -> obj or nil
 #   pop(n) -> ary
 #
 # Removes an element from the top of this Stack, and returns it.
 # Returns nil if the Stack is empty.
 #
 # If passing a number _n_, removes the top _n_ elements, and returns
 # an Array of them. If this Stack contains fewer than _n_ elements,
 # returns them all. If this Stack is empty, returns an empty Array.
 nil

 if ([].pop(0) rescue false)
   # Ruby >= 1.8.7
   def_delegator :@ary, :pop
 else
   # Ruby < 1.8.7
   def pop(*args)  # :nodoc:
     case len = args.length
     when 0
       @ary.pop
     when 1
       n = [@ary.length, args.first].min
       @ary.slice!(-n, n)
     else
       raise ArgumentError, "wrong number of arguments (#{len} for 0..1)"
     end
   end
 end

 ##
 # :method: empty?
 # Returns true if this Stack contains no elements.
 def_delegator :@ary, :empty?

 ##
 # :method: size
 # Returns the number of elements in this Stack.
 def_delegator :@ary, :size
 alias length size

 # Converts this Stack to a String.
 def to_s
   "#{self.class}#{@ary.inspect}"
 end
 alias inspect to_s

end</lang>

<lang ruby>s = Stack.new s.empty? # => true s.pop # => nil s.pop(1) # => [] s.push(1) # => Stack[1] s.push(2, 3) # => Stack[1, 2, 3] s.pop # => 3 s.pop(1) # => [2] s.empty? # => false

s = Stack[:a, :b, :c] s.pop # => :c</lang>

Sather

This one uses a builtin linked list to keep the values pushed onto the stack. <lang sather>class STACK{T} is

 private attr stack :LLIST{T};

 create:SAME is 
   res ::= new;
   res.stack := #LLIST{T};
   return res;
 end;

 push(elt: T) is
   stack.insert_front(elt);    
 end;

 pop: T is
   if ~stack.is_empty then
     stack.rewind;
     r ::= stack.current;
     stack.delete;
     return r;
   else
     raise "stack empty!\n";
   end;
 end;

 top: T is
   stack.rewind;
   return stack.current;
 end;

 is_empty: BOOL is
   return stack.is_empty;
 end;

end;</lang>

<lang sather>class MAIN is

 main is
   s ::= #STACK{INT};
   #OUT + "push values...\n";
   s.push(3);
   s.push(2);
   s.push(1);
   s.push(0);
   #OUT + "retrieving them...\n";
   loop
     #OUT + s.pop + "\n";
   until!(s.is_empty); end;
 end;

end;</lang>

Sather library has the abstract class $STACK{T}, but using this forces us to implement other methods too.

Scala

<lang scala>class Stack[T] {

  private var items=List[T]()

  def isEmpty=items.isEmpty

  def peek=items match{
     case List() => error("Stack empty")
     case head::rest => head
  }

  def pop=items match{
     case List() => error("Stack empty")
     case head::rest => items=rest; head
  }

  def push(value:T)=items=value+:items

} </lang>

Scheme

This version uses primitive message passing. <lang scheme>(define (make-stack)

 (let ((st '()))
   (lambda (message . args)
     (case message
       ((empty?) (null? st))
       ((top) (if (null? st)
                  'empty
                  (car st)))
       ((push) (set! st (cons (car args) st)))
       ((pop) (if (null? st)
                  'empty
                  (let ((result (car st)))
                    (set! st (cdr st))
                    result)))
       (else 'badmsg)))))</lang>

Slate

From Slate's standard library: <lang slate>collections define: #Stack &parents: {ExtensibleArray}. "An abstraction over ExtensibleArray implementations to follow the stack protocol. The convention is that the Sequence indices run least-to-greatest from bottom to top."

s@(Stack traits) push: obj [s addLast: obj].

s@(Stack traits) pop [s removeLast].

s@(Stack traits) pop: n [s removeLast: n].

s@(Stack traits) top [s last].

s@(Stack traits) top: n [s last: n].

s@(Stack traits) bottom [s first].</lang>

Tcl

Here's a simple implementation using a list: <lang tcl>proc push {stackvar value} {

   upvar 1 $stackvar stack
   lappend stack $value

} proc pop {stackvar} {

   upvar 1 $stackvar stack
   set value [lindex $stack end]
   set stack [lrange $stack 0 end-1]
   return $value

} proc size {stackvar} {

   upvar 1 $stackvar stack
   llength $stack

} proc empty {stackvar} {

   upvar 1 $stackvar stack
   expr {[size stack] == 0}

} proc peek {stackvar} {

   upvar 1 $stackvar stack
   lindex $stack end

}

set S [list] empty S ;# ==> 1 (true) push S foo empty S ;# ==> 0 (false) push S bar peek S ;# ==> bar pop S ;# ==> bar peek S ;# ==> foo</lang>

Library: Tcllib (Package: struct::stack)

<lang tcl>package require struct::stack struct::stack S S size ;# ==> 0 S push a b c d e S size ;# ==> 5 S peek ;# ==> e S pop ;# ==> e S peek ;# ==> d S pop 4 ;# ==> d c b a S size ;# ==> 0</lang>

UnixPipes

<lang bash>init() { if [ -e stack ]; then rm stack; fi } # force pop to blow up if empty push() { echo $1 >> stack; } pop() { tail -1 stack; x=`head -n -1 stack | wc -c` if [ $x -eq '0' ]; then rm stack; else truncate -s `head -n -1 stack | wc -c` stack fi } empty() { head -n -1 stack |wc -l; } stack_top() { tail -1 stack; } </lang>test it:<lang>% push me; push you; push us; push them % pop;pop;pop;pop them us you me</lang>

VBA

Define a class Stack in a class module with that name. <lang vb> 'Simple Stack class

'uses a dynamic array of Variants to stack the values 'has read-only property "Size" 'and methods "Push", "Pop", "IsEmpty"

Private myStack() Private myStackHeight As Integer

'method Push Public Function Push(aValue)

 'increase stack height
 myStackHeight = myStackHeight + 1
 ReDim Preserve myStack(myStackHeight)
 myStack(myStackHeight) = aValue

End Function

'method Pop Public Function Pop()

 'check for nonempty stack
 If myStackHeight > 0 Then
   Pop = myStack(myStackHeight)
   myStackHeight = myStackHeight - 1
 Else
   MsgBox "Pop: stack is empty!"
 End If

End Function

'method IsEmpty Public Function IsEmpty() As Boolean

 IsEmpty = (myStackHeight = 0)

End Function

'property Size Property Get Size() As Integer

 Size = myStackHeight

End Property </lang>

Usage example: <lang vb> 'stack test Public Sub stacktest()

 Dim aStack As New Stack
 With aStack
   'push and pop some value
   .Push 45
   .Push 123.45
   .Pop
   .Push "a string"
   .Push "another string"
   .Pop
   .Push Cos(0.75)
   Debug.Print "stack size is "; .Size
   While Not .IsEmpty
     Debug.Print "pop: "; .Pop
   Wend
   Debug.Print "stack size is "; .Size
   'try to continue popping
   .Pop
 End With

End Sub </lang>

Output:

stacktest
stack size is  3 
pop:  0,731688868873821 
pop: a string
pop:  45 
stack size is  0 

(after wich a message box will pop up)

VBScript

Stack class <lang vb>class stack dim tos dim stack() dim stacksize

private sub class_initialize stacksize = 100 redim stack( stacksize ) tos = 0 end sub

public sub push( x ) stack(tos) = x tos = tos + 1 end sub

public property get stackempty stackempty = ( tos = 0 ) end property

public property get stackfull stackfull = ( tos > stacksize ) end property

public property get stackroom stackroom = stacksize - tos end property

public function pop() pop = stack( tos - 1 ) tos = tos - 1 end function

public sub resizestack( n ) redim preserve stack( n ) stacksize = n if tos > stacksize then tos = stacksize end if end sub end class

dim s set s = new stack s.resizestack 10 wscript.echo s.stackempty dim i for i = 1 to 10 s.push rnd wscript.echo s.stackroom if s.stackroom = 0 then exit for next for i = 1 to 10 wscript.echo s.pop if s.stackempty then exit for next</lang>

Output (changes every time)

-1
9
8
7
6
5
4
3
2
1
0
0.7090379
0.81449
0.7607236
1.401764E-02
0.7747401
0.301948
0.2895625
0.5795186
0.533424
0.7055475