Stack: Difference between revisions
Content added Content deleted
(The pythonic solution first, then simple wraper, then questionable linked list implementation) |
|||
Line 236: | Line 236: | ||
'''Interpreter:''' [[Python]] 2.5 |
'''Interpreter:''' [[Python]] 2.5 |
||
The Pythonic way is using just using a list: |
|||
<pre> |
|||
stack = [] |
|||
stack.append(value) # pushing |
|||
value = stack.pop() |
|||
not stack # is empty? |
|||
</pre> |
|||
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
|||
<pre> |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
</pre> |
|||
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: |
|||
<pre> |
|||
class Stack: |
class Stack: |
||
Line 260: | Line 288: | ||
def __init__(self): |
def __init__(self): |
||
self.first = None |
self.first = None |
||
</pre> |
|||
A simpler Stack class can be built as a subclass of the built-in list: |
|||
⚫ | |||
## pop() is inherited |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
"""alias for __len__()""" |
|||
⚫ | |||
⚫ | |||
"""over-ride default iteration""" |
|||
⚫ | |||
⚫ | |||
(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. |
Revision as of 00:48, 4 November 2007
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
The Pythonic way is using 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:
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