Stack

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

Create a stack class of objects

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

 class Stack:
 
     class Node:
     
         def __init__(self, value=None, next=None):
             self.next = next
             self.value = value
 
     def isEmpty(self):
         return self.first == None
 
     def push(self, node):
         self.first = self.Node(node, self.first)
 
     def pop(self):
         if self.first == None:
             raise IndexError, "Can not pop from and empty stack"
         else:
             temp = self.first.value
             self.first = self.first.next
             return temp
 
     def __init__(self):
         self.first = None

A simpler Stack class can be built as a subclass of the built-in list:

class Stack(list):
    ## pop() is inherited
    def push(self, item):
        """alias for append()"""
        self.append(item)
    def depth(self):
        """alias for __len__()"""
        return len(self)
    def __iter__(self):
        """over-ride default iteration"""
        while len(self):
            yield self.pop()

(Note: Some versions of Python contained a bug which silently ignored over-ride of the built-in list class' .__iter__() method).

Most of this class simply provides some purely cosmetic wrappers or aliases to normal list functions. The only unusual (and non-essential) method is to make iteration of a Stack() return elements from the end of the underlying list, and to consume that as it does so (using .pop() as shown). We're only adding aliases to two methods and over-riding one.