Stack: Difference between revisions

[[Category:Encyclopedia]]

{{data structure}}[[Category:Classic CS problems and programs]]

 

 

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

 

 

 

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

 

{{Template:See also lists}}

=={{header|ActionScript}}==

In ActionScript an Array object provides stack functionality.

stack.push(1);

stack.push(2);

trace(stack.pop()); // outputs "2"

 

=={{header|Ada}}==

This is a generic stack implementation.

type Element_Type is private;

package Generic_Stack is

Next : Stack := null;

end record;

 

package body Generic_Stack is

end Pop;

 

 

=={{header|ALGOL 68}}==

ALGOL 68 uses "HEAP" variables for new LINKs in a linked list. Generally ALGOL 68's

[[garbage collection|garbage collector]] should recover the LINK memory some time after a value is popped.

{{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''.}}

CO REQUIRES:

MODE OBJVALUE = ~ # Mode/type of actual obj to be stacked #

 

PROC obj nextlink free = (REF OBJNEXTLINK free)VOID:

CO REQUIRES:

MODE OBJNEXTLINK = STRUCT(

self IS obj stack empty;

 

MODE DIETITEM = STRUCT(

STRING food, annual quantity, units, REAL cost

("Wheat Flour", "370","lb.", 13.33),

("Total Annual Cost", "","", 39.93)

# -*- coding: utf-8 -*- #

 

# OR example stack ISNT obj stack empty #

printf((diet item fmt, obj stack pop(example stack), $l$))

<pre>

Items popped in reverse:

</pre>

'''See also:''' [[Queue#ALGOL_68|Queue]]

 

=={{header|Applesoft BASIC}}==

110 DATA "(2*A)","PI","","TO BE OR","NOT TO BE"

120 FOR I = 1 TO 5

730 LET EMPTY = SP = 0

740 RETURN

 

{{out}}

STACK IS EMPTY

</pre>

 

=={{header|AutoHotkey}}==

msgbox % stack("push", 5)

msgbox % stack("peek")

return 0

}

 

=={{header|Babel}}==

{ (1 2 3) foo set -- foo = (1 2 3)

4 foo push -- foo = (1 2 3 4)

"empty" .

cr << }

foo is not empty

 

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

 

if !%~1.top! equ 0 exit /b 1

for %%N in (!%~1.top!) do set %~2=!%~1.%%N!

 

{{works with|BBC BASIC for Windows}}

FOR n = 3 TO 5

= (sptr% = 0)

ENDCASE

<pre>

Push 3

Error: stack empty

</pre>

 

=={{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>-&gt;</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))

)

&

<pre>not to be

to be or

Built in arrays have push, pop, and empty? methods:

 

stack.push 1

stack.push 2

stack.push 3

 

 

<pre>3

2

=={{header|C}}==

Macro expanding to type flexible stack routines.

#include <stdlib.h>

 

stk_int_delete(stk);

return 0;

===Or===

#include <stdlib.h>

#include <stddef.h>

s->bottom = realloc(s->bottom, new_size);

check_pointer(s->bottom);

 

=={{header|C sharp|C#}}==

System.Collections.Stack stack = new System.Collections.Stack();

stack.Push( obj );

bool isEmpty = stack.Count == 0;

Foo top = stack.Peek(); // Peek without Popping.

 

=={{header|C++}}==

{{libheader|STL}}

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

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 {

{

return !(x < y);

 

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

(defn empty-stack?

"Tests whether or not the stack is empty."

 

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.")

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

 

 

=={{header|COBOL}}==

 

stack.cbl

05 head USAGE IS POINTER VALUE NULL.

 

node.cbl

COPY node-info REPLACING

01 BY 05

node-info BY info.

05 link USAGE IS POINTER VALUE NULL.

 

node-info.cbl

 

p.cbl

88 nil VALUE ZERO WHEN SET TO FALSE IS 1.

88 t VALUE 1 WHEN SET TO FALSE IS ZERO.

 

stack-utilities.cbl

PROGRAM-ID. push.

DATA DIVISION.

GOBACK.

END PROGRAM traverse-stack.

 

stack-test.cbl

PROGRAM-ID. stack-test.

DATA DIVISION.

 

COPY stack-utilities.

 

<pre>

aleph

 

=={{header|CoffeeScript}}==

stack.push 1

stack.push 2

console.log stack

console.log stack.pop()

 

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)

 

 

(defun stack-peek (stack)

=={{header|Component Pascal}}==

Works with BlackBox Component Builder

MODULE Stacks;

IMPORT StdLog;

END Stacks.

 

Execute: ^Q Stacks.TestStack<br/>

<pre>

Point( 2.0, 3.4);

Integer( 1);

</pre>

=={{header|D}}==

Generic stack class implemented with a dynamic array.

 

class Stack(T) {

assert(s.pop() == 10);

assert(s.empty());

 

=={{header|Delphi}}==

 

{$APPTYPE CONSOLE}

lStack.Free;

end;

=={{header|Déjà Vu}}==

 

push-to stack 1

 

if stack: #empty lists are falsy

 

 

 

 

 

=={{header|E}}==

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

# value: [].diverge()

 

 

? l.size().aboveZero()

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

var store := null

def stack {

 

? s.empty()

 

=={{header|Eiffel}}==

class

STACK_ON_ARRAY

 

end

 

=={{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;

stack.index:=stack.index - 1;

stack.area[stack.index + 1] ];

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;

Pull ( stack ) = [ exception (Empty (stack), "Stack Underflow");

Head = head(stack.list); stack.list:=tail(stack.list); Head];

Both versions give the same answers to the following tests:

type Book = text;

BookStack = StackofBooks(50);

 

Pull (BookStack)?

 

=={{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]).

 

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

 

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().

false

7> stack:empty(stack:new()).

 

=={{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 ]

Let's pop it: "hi"

Vector is now: V{ 1 2 3 6 }

 

=={{header|Forth}}==

create here cell+ , cells allot ;

 

st empty? . \ 0 (false)

st pop . st pop . st pop . \ 3 2 1

 

=={{header|Fortran}}==

 

 

 

contains

 

end if

 

end subroutine push

 

end if

 

end if

 

 

 

 

 

 

 

 

 

 

 

 

=={{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,

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:

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"

fmt.Println("nothing to pop")

}

<pre>

new stack: []

top value: four

four popped. stack: [3]

</pre>

 

 

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

assert stack.empty

 

assert stack.empty

 

 

<pre>[55, 21, kittens]

[55, 21]

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

peek :: Stack a -> a

peek [] = error "Stack empty"

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

 

nonEmpty :: Stack a ()

 

=={{header|Icon}} and {{header|Unicon}}==

stack := [] # new empty stack

push(stack,1) # add item

procedure top(x) #: return top element w/o changing stack

return x[1] # in practice, just use x[1]

 

=={{header|Io}}==

aside from using built-in lists, a stack can be created using nodes like so:

next := nil

obj := nil

self node = nn

)

 

=={{header|Ioke}}==

initialize = method(@elements = [])

pop = method(@elements pop!)

empty = method(@elements empty?)

push = method(element, @elements push!(element))

 

=={{header|J}}==

push=: monad def '0$stack=:stack,y'

pop=: monad def 'r[ stack=:}:stack[ r=.{:stack'

Example use:

 

pop ''

9

empty ''

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 {

stack.pop();

}

{{out}}

<pre>New stack empty? true

 

Alternatively, you might implement a stack yourself...

private Node first = null;

public boolean isEmpty(){

}

}

{{works with|Java|1.5}}

private Node first = null;

public boolean isEmpty(){

}

}

 

=={{header|JavaScript}}==

The built-in Array class already has stack primitives.

stack.push(1)

stack.push(2,3);

print(stack.pop()); // 3

Here's a constructor that wraps the array:

this.data = new Array();

 

this.pop = function() {return this.data.pop()}

this.empty = function() {return this.data.length == 0}

 

=={{header|Julia}}==

The built-in <code>Array</code> class already has efficient (linear amortized time) stack primitives.

 

 

 

 

 

=={{header|lang5}}==

: empty? dup execute length if 0 else -1 then swap drop ;

: pop dup execute length 1 - extract swap drop ;

pop . s. cr # 2 [ 1 ]

pop drop

 

=={{header|Liberty BASIC}}==

global stack$

stack$=""

empty =(stack$="")

end function

 

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

 

=={{header|Logtalk}}==

A stack can be trivially represented using the built-in representation for lists:

:- object(stack).

 

 

:- end_object.

 

=={{header|Lua}}==

Tables have stack primitives by default:

table.insert(stack,3)

 

 

=={{header|Maple}}==

 

s := stack:-new(a, b):

empty(s);

pop(s);

<pre> c

 

true</pre>

 

SetAttributes[Push, HoldAll];[a_, elem_] := AppendTo[a, elem]

SetAttributes[Pop, HoldAllComplete];

->4

Peek[stack]

 

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

 

% empty

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

end %methods

Sample Usage:

myLIFO =

ans =

 

 

=={{header|Maxima}}==

 

load(basic)$

 

emptyp(a);

 

=={{header|Mercury}}==

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.

!:Stack = sstack(Elems).

 

 

 

 

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

stack.Length == 0

}

 

=={{header|NetRexx}}==

* 13.08.2013 Walter Pachl translated from REXX version 2

**********************************************************************/

 

method empty(stk) static

<pre>

123 from push

</pre>

 

 

 

 

 

 

 

 

 

 

 

when isMainModule:

 

 

 

=={{header|Objeck}}==

Class library support for Stack/IntStack/FloatStack

stack->Push(13);

stack->Push(7);

(stack->Pop() + stack->Pop())->PrintLine();

 

=={{header|Objective-C}}==

Using a NSMutableArray:

 

[stack addObject:value]; // pushing

[stack removeLastObject]; // popping

 

 

=={{header|OCaml}}==

Implemented as a singly-linked list, wrapped in an object:

 

class ['a] stack =

 

method push x =

 

method pop =

method is_empty =

lst = []

 

=={{header|ooRexx}}==

The ooRexx queue class functions as a stack as well (it is a dequeue really).

stack = .queue~of(123, 234) -- creates a stack with a couple of items

stack~push("Abc") -- pushing

-- the is empty test

if stack~isEmpty then say "The stack is empty"

 

=={{header|OxygenBasic}}==

The real stack is freely available!

function f()

sys a=1,b=2,c=3,d=4

 

f

 

=={{header|Oz}}==

A thread-safe, list-based stack. Implemented as a module:

export

New

@Stack == nil

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,

error("Stack underflow")

)

 

=={{header|Pascal}}==

This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects).

type

pStackNode = ^tStackNode;

PopFromStack := node^.data;

dispose(node);

 

=={{header|Perl}}==

 

 

=={{header|PHP}}==

PHP arrays behave like a stack:

 

empty( $stack ); // true

 

echo array_pop( $stack ); // outputs "2"

 

=={{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)

<pre>: Stack

-> (1 2 3)

: Stack

-> NIL</pre>

 

=={{header|PL/I}}==

 

declare s float controlled;

free s;

end;

 

=={{header|PostScript}}==

{{libheader|initlib}}

/push {exch cons}.

/pop {uncons exch pop}.

=false

[] empty?

 

=={{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]).

% empty( STACK )

% True if STACK is empty

 

=={{header|PureBasic}}==

For LIFO function PureBasic normally uses linked lists.

Usage as described above could look like;

 

Procedure Push_LIFO(n)

While Not Empty_LIFO()

Debug Pop_LIFO()

 

4

1

3

 

=={{header|Python}}==

{{works with|Python|2.5}}

stack = deque()

stack.append(value) # pushing

value = stack.pop()

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

 

class Stack:

return self._items.pop()

def __nonzero__(self):

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

def __init__(self):

self._first = None

raise IndexError, "pop from empty stack"

value, self._first = self._first

Notes:

 

You can write:

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.