Stack: Difference between revisions
added ruby |
<code> |
||
Line 18: | Line 18: | ||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
||
In ActionScript an Array object provides stack functionality. |
In ActionScript an Array object provides stack functionality. |
||
<actionscript> |
<code actionscript> |
||
var stack:Array = new Array(); |
var stack:Array = new Array(); |
||
stack.push(1); |
stack.push(1); |
||
Line 24: | Line 24: | ||
trace(stack.pop()); // outputs "2" |
trace(stack.pop()); // outputs "2" |
||
trace(stack.pop()); // outputs "1" |
trace(stack.pop()); // outputs "1" |
||
</code> |
|||
</actionscript> |
|||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
This is a generic stack implementation. |
This is a generic stack implementation. |
||
<ada> |
<code ada> |
||
generic |
generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
Line 46: | Line 46: | ||
end record; |
end record; |
||
end Generic_Stack; |
end Generic_Stack; |
||
</ |
</code> |
||
<ada> |
<code ada> |
||
with Ada.Unchecked_Deallocation; |
with Ada.Unchecked_Deallocation; |
||
Line 90: | Line 90: | ||
end Generic_Stack; |
end Generic_Stack; |
||
</ |
</code> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
ALGOL 68 uses "HEAP" variables for new LINKs in a linked list. Generally ALGOL 68's |
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. |
[[garbage collector]] should recover the LINK memory some time after a value is popped. |
||
<cpp> |
<code cpp> |
||
MODE VALUE = STRING; # type of a LINK in this STACK # |
MODE VALUE = STRING; # type of a LINK in this STACK # |
||
Line 151: | Line 151: | ||
OD; |
OD; |
||
print(((repr OF class stack)(stack), newline)) |
print(((repr OF class stack)(stack), newline)) |
||
</code> |
|||
Output:<pre> |
|||
Output: |
|||
("saw", "I", "cat", "a", "it", "Was")</pre> |
|||
<pre> |
|||
("saw", "I", "cat", "a", "it", "Was") |
|||
</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
<code c> |
|||
<c>#include <stdio.h> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <stddef.h> |
#include <stddef.h> |
||
Line 226: | Line 230: | ||
s->bottom = realloc(s->bottom, new_size); |
s->bottom = realloc(s->bottom, new_size); |
||
check_pointer(s->bottom); |
check_pointer(s->bottom); |
||
s->allocated_top = s->bottom + qtty - 1;} |
s->allocated_top = s->bottom + qtty - 1;} |
||
</code> |
|||
=={{header|C sharp|C #}}== |
=={{header|C sharp|C #}}== |
||
Line 250: | Line 255: | ||
The C++ standard library already provides a ready-made stack class. You get it by writing |
The C++ standard library already provides a ready-made stack class. You get it by writing |
||
<code cpp> |
|||
#include <stack> |
|||
#include <stack> |
|||
</code> |
|||
and then using the < |
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): |
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): |
||
<code cpp> |
|||
#include <deque> |
|||
#include <deque> |
|||
template <class T, class Sequence = std::deque<T> > |
|||
template <class T, class Sequence = std::deque<T> > |
|||
class stack { |
|||
class stack { |
|||
friend bool operator== (const stack&, const stack&); |
|||
friend bool operator== (const stack&, const stack&); |
|||
friend bool operator< (const stack&, const stack&); |
|||
public: |
|||
public: |
|||
typedef typename Sequence::value_type value_type; |
|||
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: |
|||
protected: |
|||
Sequence seq; |
|||
Sequence seq; |
|||
public: |
|||
public: |
|||
stack() : seq() {} |
|||
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> |
|||
template <class T, class Sequence> |
|||
bool operator==(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
bool operator==(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
{ |
|||
{ |
|||
return x.seq == y.seq; |
|||
return x.seq == y.seq; |
|||
} |
|||
} |
|||
template <class T, class Sequence> |
|||
template <class T, class Sequence> |
|||
bool operator<(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
bool operator<(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
{ |
|||
{ |
|||
return x.seq < y.seq; |
|||
return x.seq < y.seq; |
|||
} |
|||
} |
|||
template <class T, class Sequence> |
|||
template <class T, class Sequence> |
|||
bool operator!=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
bool operator!=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
{ |
|||
{ |
|||
return !(x == y); |
|||
return !(x == y); |
|||
} |
|||
} |
|||
template <class T, class Sequence> |
|||
template <class T, class Sequence> |
|||
bool operator>(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
bool operator>(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
{ |
|||
{ |
|||
return y < x; |
|||
return y < x; |
|||
} |
|||
} |
|||
template <class T, class Sequence> |
|||
template <class T, class Sequence> |
|||
bool operator<=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
bool operator<=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
{ |
|||
{ |
|||
return !(y < x); |
|||
return !(y < x); |
|||
} |
|||
} |
|||
template <class T, class Sequence> |
|||
template <class T, class Sequence> |
|||
bool operator>=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
bool operator>=(const stack<T,Sequence>& x, const stack<T,Sequence>& y) |
|||
{ |
|||
{ |
|||
return !(x < y); |
|||
return !(x < y); |
|||
} |
|||
} |
|||
</code> |
|||
=={{header|D}}== |
=={{header|D}}== |
||
Implemented a stack class by using sequence array. |
Implemented a stack class by using sequence array. |
||
<code d> |
|||
<pre>module stack ; |
|||
module stack ; |
|||
class Stack(T){ |
class Stack(T){ |
||
private T[] content = null ; |
private T[] content = null ; |
||
Line 325: | Line 335: | ||
} |
} |
||
bool empty() { return content.length == 0 ; } |
bool empty() { return content.length == 0 ; } |
||
} |
|||
}</pre> |
|||
</code> |
|||
=={{header|E}}== |
=={{header|E}}== |
||
Line 407: | Line 418: | ||
Haskell solution is trivial, using a list. Note that pop returns both the element and the changed stack, to remain purely functional. |
Haskell solution is trivial, using a list. Note that pop returns both the element and the changed stack, to remain purely functional. |
||
<code haskell> |
|||
type Stack a = [a] |
|||
type Stack a = [a] |
|||
create :: Stack a |
|||
create = [] |
|||
push :: a -> Stack a -> Stack a |
|||
push x xs = x:xs |
|||
pop :: Stack a -> (a, Stack a) |
|||
pop [] = error "Stack empty" |
|||
pop (x:xs) = (x,xs) |
|||
empty :: Stack a -> Bool |
|||
empty [] = true |
|||
empty _ = false |
|||
</code> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
||
<code 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; |
|||
} |
|||
} |
|||
} |
|||
</code> |
|||
{{works with|Java|1.5}} |
{{works with|Java|1.5}} |
||
<code java5> |
|||
public class Stack<T> |
|||
public class Stack<T> |
|||
{ |
|||
{ |
|||
private Node first = null; |
|||
private Node first = null; |
|||
public boolean isEmpty { |
|||
public boolean isEmpty { |
|||
return (first == null); |
|||
return (first == null); |
|||
} |
|||
} |
|||
public T Pop() { |
|||
public T Pop() { |
|||
if (first == null) |
|||
throw new Exception("Can't Pop from an empty Stack."); |
|||
throw new Exception("Can't Pop from an empty Stack."); |
|||
else { |
|||
else { |
|||
T temp = first.Value; |
|||
first = first.Next; |
|||
return temp; |
|||
} |
} |
||
} |
|||
public void Push(T o) { |
|||
public void Push(T o) { |
|||
first = new Node(o, first); |
|||
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) { |
|||
public Node(T value, Node next) { |
|||
Next = next; |
|||
Value = value; |
|||
} |
} |
||
} |
} |
||
} |
|||
</code> |
|||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
The built-in Array class already has stack primitives. |
The built-in Array class already has stack primitives. |
||
<code javascript> |
|||
var stack = []; |
|||
var stack = []; |
|||
stack.push(1) |
|||
stack.push(2,3); |
|||
print(stack.pop()); // 3 |
|||
print(stack.length); // 2, stack empty if 0 |
|||
</code> |
|||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
Line 509: | Line 527: | ||
Implemented as a singly-linked list, wrapped in an object: |
Implemented as a singly-linked list, wrapped in an object: |
||
<ocaml> |
<code ocaml> |
||
exception Stack_empty |
|||
class ['a] stack = |
class ['a] stack = |
||
Line 526: | Line 545: | ||
method is_empty = |
method is_empty = |
||
lst = [] |
lst = [] |
||
end |
end |
||
</code> |
|||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects). |
This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects). |
||
<pascal> |
<code pascal> |
||
{ tStack is the actual stack type, tStackNode a helper type } |
{ tStack is the actual stack type, tStackNode a helper type } |
||
type |
type |
||
Line 586: | Line 606: | ||
dispose(node); |
dispose(node); |
||
end; |
end; |
||
</ |
</code> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Line 594: | Line 614: | ||
The faster and Pythonic way is using a deque (available from 2.4). A regular list is little slower. |
The faster and Pythonic way is using a deque (available from 2.4). A regular list is little slower. |
||
<code python> |
|||
<python>from collections import deque |
|||
from collections import deque |
|||
stack = deque() |
stack = deque() |
||
stack.append(value) # pushing |
stack.append(value) # pushing |
||
value = stack.pop() |
value = stack.pop() |
||
not stack # is empty? |
not stack # is empty? |
||
</code> |
|||
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
||
<code python> |
|||
<python>from collections import deque |
|||
from collections import deque |
|||
class Stack: |
class Stack: |
||
Line 612: | Line 635: | ||
return self._items.pop() |
return self._items.pop() |
||
def __nonzero__(self): |
def __nonzero__(self): |
||
return bool(self._items) |
return bool(self._items) |
||
</code> |
|||
Here is a stack implemented as linked list - with the same list interface. |
Here is a stack implemented as linked list - with the same list interface. |
||
<python> |
<code python> |
||
class Stack: |
|||
def __init__(self): |
def __init__(self): |
||
self._first = None |
self._first = None |
||
Line 627: | Line 652: | ||
raise IndexError, "pop from empty stack" |
raise IndexError, "pop from empty stack" |
||
value, self._first = self._first |
value, self._first = self._first |
||
return value |
return value |
||
</code> |
|||
Notes: |
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: |
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: |
||
<code python> |
|||
while not stack.empty(): |
while not stack.empty(): |
||
</code> |
|||
You can write: |
You can write: |
||
<code python> |
|||
while stack: |
while stack: |
||
</code> |
|||
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. |
Quick testing show that deque is about 5 times faster then the wrapper linked list implementations. This may be important if your stack is used in tight loops. |
||
Line 653: | Line 683: | ||
Using an Array: |
Using an Array: |
||
<ruby> |
<code ruby> |
||
stack = [] |
|||
stack.push(value) # pushing |
stack.push(value) # pushing |
||
value = stack.pop # popping |
value = stack.pop # popping |
||
stack.empty? # is empty? |
stack.empty? # is empty? |
||
</code> |
|||
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
||
<ruby> |
<code ruby> |
||
class Stack |
|||
def initialize |
def initialize |
||
@items = [] |
@items = [] |
||
Line 673: | Line 706: | ||
@items.empty? |
@items.empty? |
||
end |
end |
||
end |
end |
||
</code> |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
This version uses primitive message passing. |
This version uses primitive message passing. |
||
<scheme> |
<code scheme> |
||
(define (make-stack) |
|||
(let ((st '())) |
(let ((st '())) |
||
(lambda (message . args) |
(lambda (message . args) |
||
Line 691: | Line 726: | ||
(set! st (cdr st)) |
(set! st (cdr st)) |
||
result))) |
result))) |
||
(else 'badmsg))))) |
(else 'badmsg))))) |
||
</code> |
Revision as of 08:07, 27 January 2009
![Task](http://static.miraheze.org/rosettacodewiki/thumb/b/ba/Rcode-button-task-crushed.png/64px-Rcode-button-task-crushed.png)
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.
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.
var stack:Array = new Array();
stack.push(1);
stack.push(2);
trace(stack.pop()); // outputs "2"
trace(stack.pop()); // outputs "1"
Ada
This is a generic stack implementation.
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;
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;
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.
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))
Output:
("saw", "I", "cat", "a", "it", "Was")
C
- include <stdio.h>
- include <stdlib.h>
- include <stddef.h>
- include <stdbool.h>
- define check_pointer(p) if (!p) {puts("Out of memory."); exit(EXIT_FAILURE);}
- define MINIMUM_SIZE 1
/* Minimal stack size (expressed in number of elements) for which
space is allocated. It should be at least 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;}
C#
// 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();
C++
The C++ standard library already provides a ready-made stack class. You get it by writing
- include <stack>
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):
- 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);
}
D
Implemented a stack class by using sequence array.
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 ; }
}
E
The standard FlexList data structure provides operations for use as a stack.
? def l := [].diverge() # value: [].diverge() ? l.push(1) ? l.push(2) ? l # value: [1, 2].diverge() ? l.pop() # value: 2 ? l.size().aboveZero() # value: true ? l.last() # value: 1 ? l.pop() # value: 1 ? l.size().aboveZero() # value: false
Here's a stack implemented out of a reference to a linked list:
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() # value: <stack> ? s.push(1) ? s.push(2) ? s.last() # value: 2 ? s.pop() # value: 2 ? s.empty() # value: false ? s.pop() # value: 1 ? s.empty() # value: true
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)
Haskell
Haskell solution is trivial, using a list. Note that pop returns both the element and the changed stack, to remain purely functional.
type Stack a = [a]
create :: Stack a
create = []
push :: a -> Stack a -> Stack a
push x xs = x:xs
pop :: Stack a -> (a, Stack a)
pop [] = error "Stack empty"
pop (x:xs) = (x,xs)
empty :: Stack a -> Bool
empty [] = true
empty _ = false
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;
}
}
}
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;
}
}
}
JavaScript
The built-in Array class already has stack primitives.
var stack = [];
stack.push(1)
stack.push(2,3);
print(stack.pop()); // 3
print(stack.length); // 2, stack empty if 0
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.
make "stack [] push "stack 1 push "stack 2 push "stack 3 print pop "stack ; 3 print empty? :stack ; false
OCaml
Implemented as a singly-linked list, wrapped in an object:
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
Pascal
This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects).
{ 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;
Python
The faster and Pythonic way is using a deque (available from 2.4). A regular list is little slower.
from collections import deque
stack = deque()
stack.append(value) # pushing
value = stack.pop()
not stack # is empty?
If you need to expose your stack to the world, you may want to create a simpler wrapper:
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)
Here is a stack implemented as linked list - with the same list interface.
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
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:
while not stack.empty():
You can write:
while stack:
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.
Raven
Use built in stack type:
new stack as s 1 s push s pop
Word empty is also built in:
s empty if 'stack is empty' print
Ruby
Using an Array:
stack = []
stack.push(value) # pushing
value = stack.pop # popping
stack.empty? # is empty?
If you need to expose your stack to the world, you may want to create a simpler wrapper:
class Stack
def initialize
@items = []
end
def push(item)
@items.push(item)
end
def pop
@items.pop
end
def empty?
@items.empty?
end
end
Scheme
This version uses primitive message passing.
(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)))))