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 element to the stack
- pop - remove last added element
- empty - return a true value 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#
public class Stack
{
private Node first = null;
public bool Empty {
get {
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;
}
}
}
C++
Library: STL
#include <stack>
#include <deque>
template <class T, class Sequence = 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);
}
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;
}
}
}
Compiler: JDK 1.5 with Generics
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
Interpreter: Python 2.5
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