Stack
Data Structure
This illustrates a data structure, a means of storing data within a program.
Create a stack supporting the basic operations:
- push - Add an element to the stack.
- pop - Remove the most recently added element.
- empty - Return logical value True if the stack is empty, False otherwise.
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;
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 ; } }
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; } } }
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 time 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