Stack

This example is incomplete. Please ensure that it meets all task requirements and remove this message.

Create a stack supporting the basic operations:

• push - add element to the stack
• pop - remove last added element
• empty - return a truth 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);
 }

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 Pythonic way is just using a list:

stack = []
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:

class Stack(object):
    def __init__(self):
        self._items = []
    def append(self, item):
        self._items.append(item)
    def pop(self):
        return self._items.pop()
    def __len__(self):
        return len(self._items)

Note: using list interface - append, __len__ make make it easier to use and change the implementation later.

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 != None 
    def append(self, value):
        self._first = (value, self._first)
    def pop(self):
        if self._first == None:
            raise IndexError, "Can not pop from and empty stack"
        value = self._first[0]
        self._first = self._first[1]
        return value  

Quick testing show that the list is about 5 time faster then the wrapper or the linked list implementation. This may be important if your stack is used in tight loops.