Editing Stack

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