Stack

From Rosetta Code
Revision as of 03:52, 2 January 2010 by rosettacode>Wmeyer (Added Oz example.)
Task
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 as a containers presume copyable elements. I.e. stack elements have by-value semantics. This means that when an element is pushed onto the stack, a new instance of the element's type is created. This instance has a value equivalent to one the pushed element.

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>

C

<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>

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) 

 (pop (stack-elements stack)))

(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

Implemented a stack class by using sequence array. <lang d>module stack ; class Stack(T){ 

 private T[] content = null ;
 void push(T top) { content ~= top ; }
 T pop() {
   if (empty)
     throw new Exception("Stack Empty") ;
   T top = content[$-1] ;
   content.length = content.length - 1 ;
   return top ;
 }
 bool empty() { return content.length == 0 ; }

}</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>

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>


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>

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>

J

<lang J>create_stack_=: monad def 'stack=:$0' push_stack_=: monad def 'stack=:stack,y' pop_stack_=: monad def 'r[ stack=:}:stack[ r=.{:stack' empty_stack_=: monad def '0=#stack'</lang>

Example use:

<lang J> example=:conew~'stack'</lang> <lang J> push__example 0</lang> <lang J> pop__example 0</lang> <lang J> empty__example 0</lang>

pop and empty ignore their arguments. In this implementation, push returns the new state of the stack.

Java

<lang java>public class Stack { 

   private Node first = null;
   public boolean isEmpty {
       return (first == null);
   }
   public Object Pop() {
       if (first == null) 
           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) {
           Next = next;
           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 (first == null) 
           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) {
           Next = next;
           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>

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>

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
  Top

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

  fun {Top Stack}
     case @Stack of X|_ then X end
  end

end</lang>

There is also a stack implementation in the standard library.

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); 

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>

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>

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 Demonstration"
   File: %stack.r
   Author: oofoe
   Date: 2009-12-04
   URL: http://rosettacode.org/wiki/Stack

]

Make stack class.

stack: make object! [ stack: copy []

push: func [v] [append stack v] pop: func [/local x] [x: last stack remove back tail stack x]

top: does [last stack] empty?: does [0 = length? stack] ]

Tests

assert: func [description actual wanted][ print rejoin [description ": " either actual = wanted ["ok"]["fail"]]]

s: make stack []

assert "Start empty" s/empty? yes

s/push 34 s/push 99 assert "Simple push" s/stack [34 99]

assert "Pop top" s/pop 99

assert "Peek top" s/top 34 assert "Pop last" s/pop 34

assert "Finish empty" s/empty? yes </lang>

Ruby

Using an Array: <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:

<lang ruby>class Stack 

   def initialize
       @items = []
   end
   def push(item)
       @items.push(item)
   end
   def pop
       @items.pop
   end
   def empty?
       @items.empty?
   end

end</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>

There is a package in

Library: tcllib

called struct::stack that presents an object interface:

<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

Uses moreutils <lang bash>init(echo > stack) push() {echo $1 >> stack} pop() {tail -1 stack; (cat stack |head -n -1)|sponge stack} empty() {cat stack |wc -l}</lang> Usage: <lang bash>push me; push you; push us; push them pop;pop;pop;pop them us you</lang> 

me
Retrieved from "https://rosettacode.org/wiki/Stack?oldid=24924"