Stack - Revision history

Brian at 04:48, 5 March 2011

2011-03-05T04:48:59Z

Jargon: categorize

2009-12-23T17:19:33Z

categorize

Brian: /* C++ STL stack class */

2009-12-20T05:24:19Z

‎C++ STL stack class

Brian: /* C++ STL stack class */

2009-12-20T05:16:05Z

‎C++ STL stack class

Brian: /* Linked list implementation */

2009-12-20T05:14:10Z

‎Linked list implementation

38.113.177.141 at 04:10, 23 November 2009

2009-11-23T04:10:23Z

Brian: /* C++ STL stack class */ spelling correction: an -> and

2009-11-17T06:26:42Z

‎C++ STL stack class: spelling correction: an -> and

Brian: Created page with 'A '''stack''' is a data structure containing zero or more items, all of the same type, which supports two basic operations: * ''Push'' an element onto the stack. * ''Pop'' the mo…'

2009-11-15T06:55:21Z

Created page with 'A '''stack''' is a data structure containing zero or more items, all of the same type, which supports two basic operations: * ''Push'' an element onto the stack. * ''Pop'' the mo…'

New page

A '''stack''' is a data structure containing zero or more items, all of the same type, which supports two basic operations:
* ''Push'' an element onto the stack.
* ''Pop'' the most recently added item off the stack, returning its value in the process.
In practice, we might choose to include the following operations as well:
* ''Construct'' a new, empty stack. (This one is more or less implicit.)
* ''Copy'' the contents of one stack to another.
* ''Peek'' at the top element in the stack (the one which would be popped next), without removing it.
* ''Empty'' an already existing stack.
* ''Find size'' of a stack.
* ''Test if empty''.
Notice that the ''peek'' operation can be implemented as a pop followed by a push, and is not fundamental and the ''test if empty'' operation is the same as the ''find size'' operation followed by a test of whether or not the size is zero.

=Anatomy and terminology=
The name ''stack'' is quite simply based on real-life objects which are also known as stacks. For example, a stack of paper, a stack of books, a stack of plates. In such stacks, we add new items to the top, and we also remove items from the top; attempting to add or remove items anywhere else has potentially disastrous consequences. In computer science, of course, there does not always need to be a ''top'' and ''bottom''. Instead, elements are added one-by-one to the stack. The most recently added element (and the first that would be removed) is at the ''top'', and the oldest element (the last that would be removed) is at the ''bottom''. An element is said to be ''higher'' than another if the former was added later (and will be removed sooner) than the latter; the latter element is said to be ''lower''. To ''push'' means to add an element, and to ''pop'' means to remove an element.

=Implementation=
==Call stack==
The current state of program execution is partially described by a ''call stack''. Each item in the call stack is a ''stack frame'', that stores the entire environment of a specific invocation of a function. When a function calls another, a stack frame is created for the latter and pushed onto the call stack; when a function returns, its stack frame is popped off the stack. For example, if the function <code>main</code> calls the function <code>fox</code>, which in turn calls itself with different arguments, then during the deeper call to <code>fox</code>, the call stack will contain, from bottom to top, frames for <code>main</code>, <code>fox</code>, and <code>fox</code>. Each frame will contain the parameters of the corresponding function call, as well as any local variables in the corresponding function call. Hence, the two <code>fox</code> frames will differ in that the higher one will contain the parameters for the deeper <code>fox</code> call, and the lower one the parameters for the other. The call stack is implemented implicitly in essentially all programming languages that support function calls (that is, almost all useful programming languages).

==Explicit stack==
When explicit [[recursion]] is not involved, a stack must be stored separately in memory from the call stack. This is almost always done with either an array or a [[linked list]].
===Array implementation===
In an array implementation of a stack, the contents of the stack are stored in contiguous indices in an array. Usually, the bottom of the stack is at the lowest index (such as 0), and the top of the stack at the highest. We may then implement the stack as follows:
<pre>
object stack
function construct(max_size)
let A be an array that can hold at least max_size elements
let top = 0
function push(x)
A[top]=x
top = top + 1
function pop
top = top - 1
return A[top]
function peek
return A[top-1]
function size
return top
function make_empty
top = 0
</pre>
Error-checking code has been omitted (consider what happens for example if we attempt to pop from an empty stack). The ''test if empty'' and ''copy'' operations have been omitted for the sake of brevity.
===Linked list implementation===
The array implementation will almost always be appropriate. However, for rare instances in which a contiguous block of memory of the required size cannot be found, a linked list can be used instead. Details of the list implementation are omitted below:
<pre>
object stack
function construct
let L be an empty linked list
function push(x)
insert x after tail of L
function pop
remove tail of L, returning its data element
function peek
return data element at tail of L
function size
return size of L
function make_empty
delete L
</pre>
As one can easily see, the stack is merely a container over the operations supported by the list itself. (Here we assume that the list maintains its own size; if this is not so then we can add a <code>size</code> field to the stack object.)
===C++ STL stack class===
In the C++ STL, <code>std::stack</code> is a template container capable of holding items of any (fixed) type, the type being supplied as a template argument. Hence, for example, <code>stack<char></code> is a stack of characters. The container supplies the following member functions (note that <code>T</code> is the type of the elements of the stack):
* <code>void push(const T& x)</code>: pushes <code>x</code> onto the stack.
* <code>void pop()</code>: performs a pop.
* <code>T& top()</code>: returns the element which is to be popped next
* <code>size_type size()</code>: returns the number of elements currently on the stack
* <code>bool empty()</code>: returns <code>true</code> if the stack is empty, <code>false</code> otherwise.
The <code>stack</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own stack. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator|iteration]] through the elements of the stack. In such circumstances the STL <code>stack</code> cannot be used an a custom stack must be implemented.

← Older revision		Revision as of 17:19, 23 December 2009
Line 70:		Line 70:

	Note that the pop operation defined by this container is not identical to our own; it only removes the element and it does not return its value. To do both, call <code>top</code> followed by <code>pop</code>.		Note that the pop operation defined by this container is not identical to our own; it only removes the element and it does not return its value. To do both, call <code>top</code> followed by <code>pop</code>.
		+
		+	[[Category:Data structures]]

← Older revision		Revision as of 05:24, 20 December 2009
Line 68:		Line 68:
	* <code>bool empty()</code>: returns <code>true</code> if the stack is empty, <code>false</code> otherwise.		* <code>bool empty()</code>: returns <code>true</code> if the stack is empty, <code>false</code> otherwise.
	The <code>stack</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own stack. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator\|iteration]] through the elements of the stack. In such circumstances the STL <code>stack</code> cannot be used and a custom stack must be implemented.		The <code>stack</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own stack. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator\|iteration]] through the elements of the stack. In such circumstances the STL <code>stack</code> cannot be used and a custom stack must be implemented.
		+
		+	Note that the pop operation defined by this container is not identical to our own; it only removes the element and it does not return its value. To do both, call <code>top</code> followed by <code>pop</code>.

@@ Line 11: / Line 11: @@
 Notice that the ''peek'' operation can be implemented as a pop followed by a push (and is therefore not fundamental) and the ''test if empty'' operation is the same as the ''find size'' operation followed by a test of whether or not the size is zero.
-=Anatomy and terminology=
+==Anatomy and terminology==
 The name ''stack'' is quite simply based on real-life objects which are also known as stacks. For example, a stack of paper, a stack of books, a stack of plates. In such stacks, we add new items to the top, and we also remove items from the top; attempting to add or remove items anywhere else has potentially disastrous consequences. In computer science, of course, there does not always need to be a ''top'' and ''bottom''. Instead, elements are added one-by-one to the stack. The most recently added element (and the first that would be removed) is at the ''top'', and the oldest element (the last that would be removed) is at the ''bottom''. An element is said to be ''higher'' than another if the former was added later (and will be removed sooner) than the latter; the latter element is said to be ''lower''. To ''push'' means to add an element, and to ''pop'' means to remove an element.
-=Implementation=
+==Implementation==
-==Call stack==
+===Call stack===
 The current state of program execution is partially described by a ''call stack''. Each item in the call stack is a ''stack frame'', that stores the entire environment of a specific invocation of a function. When a function calls another, a stack frame is created for the latter and pushed onto the call stack; when a function returns, its stack frame is popped off the stack. For example, if the function <code>main</code> calls the function <code>fox</code>, which in turn calls itself with different arguments, then during the deeper call to <code>fox</code>, the call stack will contain, from bottom to top, frames for <code>main</code>, <code>fox</code>, and <code>fox</code>. Each frame will contain the parameters of the corresponding function call, as well as any local variables in the corresponding function call. Hence, the two <code>fox</code> frames will differ in that the higher one will contain the parameters for the deeper <code>fox</code> call, and the lower one the parameters for the other. The call stack is implemented implicitly in essentially all programming languages that support function calls (that is, almost all useful programming languages).
-==Explicit stack==
+===Explicit stack===
 When explicit [[recursion]] is not involved, a stack must be stored separately in memory from the call stack. This is almost always done with either an array or a [[linked list]].
-===Array implementation===
+====Array implementation====
 In an array implementation of a stack, the contents of the stack are stored in contiguous indices in an array. Usually, the bottom of the stack is at the lowest index (such as 0), and the top of the stack at the highest. We may then implement the stack as follows:
 <pre>
@@ Line 41: / Line 41: @@
 </pre>
 Error-checking code has been omitted (consider what happens for example if we attempt to pop from an empty stack). The ''test if empty'' and ''copy'' operations have been omitted for the sake of brevity.
-===Linked list implementation===
+====Linked list implementation====
 The array implementation will almost always be appropriate. However, for rare instances in which a contiguous block of memory of the required size cannot be found, a linked list can be used instead. Details of the list implementation are omitted below:
 <pre>
@@ Line 60: / Line 60: @@
 As one can easily see, the stack is merely a container over the operations supported by the list itself. (Here we assume that the list maintains its own size; if this is not so then we can add a <code>size</code> field to the stack object.)
-===C++ STL stack class===
+====C++ STL stack class====
 In the C++ STL, <code>std::stack</code>, found in the <code>&lt;stack&gt;</code> header, is a template container capable of holding items of any (fixed) type, the type being supplied as a template argument. Hence, for example, <code>stack&lt;char&gt;</code> is a stack of characters. The container supplies the following member functions (note that <code>T</code> is the type of the elements of the stack):
 * <code>void push(const T& x)</code>: pushes <code>x</code> onto the stack.

@@ Line 56: / Line 56: @@
            return size of L
       function make_empty
-           delete L
+           empty L
 </pre>
 As one can easily see, the stack is merely a container over the operations supported by the list itself. (Here we assume that the list maintains its own size; if this is not so then we can add a <code>size</code> field to the stack object.)
 ===C++ STL stack class===
 In the C++ STL, <code>std::stack</code> is a template container capable of holding items of any (fixed) type, the type being supplied as a template argument. Hence, for example, <code>stack&lt;char&gt;</code> is a stack of characters. The container supplies the following member functions (note that <code>T</code> is the type of the elements of the stack):

@@ Line 9: / Line 9: @@
 * ''Find size'' of a stack.
 * ''Test if empty''.
-Notice that the ''peek'' operation can be implemented as a pop followed by a push, and is not fundamental and the ''test if empty'' operation is the same as the ''find size'' operation followed by a test of whether or not the size is zero.
+Notice that the ''peek'' operation can be implemented as a pop followed by a push (and is therefore not fundamental) and the ''test if empty'' operation is the same as the ''find size'' operation followed by a test of whether or not the size is zero.
 =Anatomy and terminology=

@@ Line 66: / Line 66: @@
 * <code>size_type size()</code>: returns the number of elements currently on the stack
 * <code>bool empty()</code>: returns <code>true</code> if the stack is empty, <code>false</code> otherwise.
-The <code>stack</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own stack. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator|iteration]] through the elements of the stack. In such circumstances the STL <code>stack</code> cannot be used an a custom stack must be implemented.
+The <code>stack</code> container should be used whenever it is sufficient for the problem at hand; it is quicker and less error-prone to use it than to code your own stack. There are, however, times when it might be necessary to execute some unsupported operation such as [[Iterator|iteration]] through the elements of the stack. In such circumstances the STL <code>stack</code> cannot be used and a custom stack must be implemented.