Stack: Difference between revisions
Content deleted Content added
<code> |
m <lang> |
||
Line 18: | Line 18: | ||
=={{header|ActionScript}}== |
=={{header|ActionScript}}== |
||
In ActionScript an Array object provides stack functionality. |
In ActionScript an Array object provides stack functionality. |
||
< |
<lang actionscript> |
||
var stack:Array = new Array(); |
var stack:Array = new Array(); |
||
stack.push(1); |
stack.push(1); |
||
Line 24: | Line 24: | ||
trace(stack.pop()); // outputs "2" |
trace(stack.pop()); // outputs "2" |
||
trace(stack.pop()); // outputs "1" |
trace(stack.pop()); // outputs "1" |
||
</ |
</lang> |
||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
This is a generic stack implementation. |
This is a generic stack implementation. |
||
< |
<lang ada> |
||
generic |
generic |
||
type Element_Type is private; |
type Element_Type is private; |
||
Line 46: | Line 46: | ||
end record; |
end record; |
||
end Generic_Stack; |
end Generic_Stack; |
||
</ |
</lang> |
||
< |
<lang ada> |
||
with Ada.Unchecked_Deallocation; |
with Ada.Unchecked_Deallocation; |
||
Line 90: | Line 90: | ||
end Generic_Stack; |
end Generic_Stack; |
||
</ |
</lang> |
||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
ALGOL 68 uses "HEAP" variables for new LINKs in a linked list. Generally ALGOL 68's |
ALGOL 68 uses "HEAP" variables for new LINKs in a linked list. Generally ALGOL 68's |
||
[[garbage collector]] should recover the LINK memory some time after a value is popped. |
[[garbage collector]] should recover the LINK memory some time after a value is popped. |
||
< |
<lang cpp> |
||
MODE VALUE = STRING; # type of a LINK in this STACK # |
MODE VALUE = STRING; # type of a LINK in this STACK # |
||
Line 152: | Line 152: | ||
print(((repr OF class stack)(stack), newline)) |
print(((repr OF class stack)(stack), newline)) |
||
</ |
</lang> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 159: | Line 159: | ||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<lang c> |
||
#include <stdio.h> |
#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
Line 231: | Line 231: | ||
check_pointer(s->bottom); |
check_pointer(s->bottom); |
||
s->allocated_top = s->bottom + qtty - 1;} |
s->allocated_top = s->bottom + qtty - 1;} |
||
</ |
</lang> |
||
=={{header|C sharp|C #}}== |
=={{header|C sharp|C #}}== |
||
Line 255: | Line 255: | ||
The C++ standard library already provides a ready-made stack class. You get it by writing |
The C++ standard library already provides a ready-made stack class. You get it by writing |
||
< |
<lang cpp> |
||
#include <stack> |
#include <stack> |
||
</ |
</lang> |
||
and then using the <tt>std::stack</tt> class. |
and then using the <tt>std::stack</tt> class. |
||
Line 263: | Line 263: | ||
An example of an explicit implementation of a stack class (which actually implements the standard stack class, except that the standard one is in namespace std): |
An example of an explicit implementation of a stack class (which actually implements the standard stack class, except that the standard one is in namespace std): |
||
< |
<lang cpp> |
||
#include <deque> |
#include <deque> |
||
template <class T, class Sequence = std::deque<T> > |
template <class T, class Sequence = std::deque<T> > |
||
Line 319: | Line 319: | ||
return !(x < y); |
return !(x < y); |
||
} |
} |
||
</ |
</lang> |
||
=={{header|D}}== |
=={{header|D}}== |
||
Implemented a stack class by using sequence array. |
Implemented a stack class by using sequence array. |
||
< |
<lang d> |
||
module stack ; |
module stack ; |
||
class Stack(T){ |
class Stack(T){ |
||
Line 336: | Line 336: | ||
bool empty() { return content.length == 0 ; } |
bool empty() { return content.length == 0 ; } |
||
} |
} |
||
</ |
</lang> |
||
=={{header|E}}== |
=={{header|E}}== |
||
Line 418: | Line 418: | ||
Haskell solution is trivial, using a list. Note that pop returns both the element and the changed stack, to remain purely functional. |
Haskell solution is trivial, using a list. Note that pop returns both the element and the changed stack, to remain purely functional. |
||
< |
<lang haskell> |
||
type Stack a = [a] |
type Stack a = [a] |
||
Line 434: | Line 434: | ||
empty [] = true |
empty [] = true |
||
empty _ = false |
empty _ = false |
||
</ |
</lang> |
||
=={{header|Java}}== |
=={{header|Java}}== |
||
< |
<lang java> |
||
public class Stack |
public class Stack |
||
{ |
{ |
||
Line 468: | Line 468: | ||
} |
} |
||
} |
} |
||
</ |
</lang> |
||
{{works with|Java|1.5}} |
{{works with|Java|1.5}} |
||
< |
<lang java5> |
||
public class Stack<T> |
public class Stack<T> |
||
{ |
{ |
||
Line 503: | Line 503: | ||
} |
} |
||
} |
} |
||
</ |
</lang> |
||
=={{header|JavaScript}}== |
=={{header|JavaScript}}== |
||
The built-in Array class already has stack primitives. |
The built-in Array class already has stack primitives. |
||
< |
<lang javascript> |
||
var stack = []; |
var stack = []; |
||
stack.push(1) |
stack.push(1) |
||
Line 513: | Line 513: | ||
print(stack.pop()); // 3 |
print(stack.pop()); // 3 |
||
print(stack.length); // 2, stack empty if 0 |
print(stack.length); // 2, stack empty if 0 |
||
</ |
</lang> |
||
=={{header|Logo}}== |
=={{header|Logo}}== |
||
Line 527: | Line 527: | ||
Implemented as a singly-linked list, wrapped in an object: |
Implemented as a singly-linked list, wrapped in an object: |
||
< |
<lang ocaml> |
||
exception Stack_empty |
exception Stack_empty |
||
Line 546: | Line 546: | ||
lst = [] |
lst = [] |
||
end |
end |
||
</ |
</lang> |
||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects). |
This implements stacks of integers in standard Pascal (should work on all existing Pascal dialects). |
||
< |
<lang pascal> |
||
{ tStack is the actual stack type, tStackNode a helper type } |
{ tStack is the actual stack type, tStackNode a helper type } |
||
type |
type |
||
Line 606: | Line 606: | ||
dispose(node); |
dispose(node); |
||
end; |
end; |
||
</ |
</lang> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
Line 614: | Line 614: | ||
The faster and Pythonic way is using a deque (available from 2.4). A regular list is little slower. |
The faster and Pythonic way is using a deque (available from 2.4). A regular list is little slower. |
||
< |
<lang python> |
||
from collections import deque |
from collections import deque |
||
stack = deque() |
stack = deque() |
||
Line 620: | Line 620: | ||
value = stack.pop() |
value = stack.pop() |
||
not stack # is empty? |
not stack # is empty? |
||
</ |
</lang> |
||
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
||
< |
<lang python> |
||
from collections import deque |
from collections import deque |
||
Line 636: | Line 636: | ||
def __nonzero__(self): |
def __nonzero__(self): |
||
return bool(self._items) |
return bool(self._items) |
||
</ |
</lang> |
||
Here is a stack implemented as linked list - with the same list interface. |
Here is a stack implemented as linked list - with the same list interface. |
||
< |
<lang python> |
||
class Stack: |
class Stack: |
||
def __init__(self): |
def __init__(self): |
||
Line 653: | Line 653: | ||
value, self._first = self._first |
value, self._first = self._first |
||
return value |
return value |
||
</ |
</lang> |
||
Notes: |
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: |
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: |
||
< |
<lang python> |
||
while not stack.empty(): |
while not stack.empty(): |
||
</ |
</lang> |
||
You can write: |
You can write: |
||
< |
<lang python> |
||
while stack: |
while stack: |
||
</ |
</lang> |
||
Quick testing show that deque is about 5 times faster then the wrapper linked list implementations. This may be important if your stack is used in tight loops. |
Quick testing show that deque is about 5 times faster then the wrapper linked list implementations. This may be important if your stack is used in tight loops. |
||
Line 683: | Line 683: | ||
Using an Array: |
Using an Array: |
||
< |
<lang ruby> |
||
stack = [] |
stack = [] |
||
stack.push(value) # pushing |
stack.push(value) # pushing |
||
value = stack.pop # popping |
value = stack.pop # popping |
||
stack.empty? # is empty? |
stack.empty? # is empty? |
||
</ |
</lang> |
||
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
If you need to expose your stack to the world, you may want to create a simpler wrapper: |
||
< |
<lang ruby> |
||
class Stack |
class Stack |
||
def initialize |
def initialize |
||
Line 707: | Line 707: | ||
end |
end |
||
end |
end |
||
</ |
</lang> |
||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||
This version uses primitive message passing. |
This version uses primitive message passing. |
||
< |
<lang scheme> |
||
(define (make-stack) |
(define (make-stack) |
||
(let ((st '())) |
(let ((st '())) |
||
Line 727: | Line 727: | ||
result))) |
result))) |
||
(else 'badmsg))))) |
(else 'badmsg))))) |
||
</ |
</lang> |