Stack
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.