Editing Stack

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
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.
 
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.
 
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).
 
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]].
 
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:
 
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>
 
<pre>
Line 41: Line 41:
 
</pre>
 
</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.  
 
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:
 
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>
 
<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.)
 
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):
 
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.
 
* <code>void push(const T& x)</code>: pushes <code>x</code> onto the stack.

Please note that all contributions to PEGWiki are considered to be released under the Attribution 3.0 Unported (see PEGWiki:Copyrights for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource. Do not submit copyrighted work without permission!

Cancel | Editing help (opens in new window)