Difference between revisions of "Stack"

Latest revision as of 04:48, 5 March 2011

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 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[edit]

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[edit]

Call stack[edit]

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 main calls the function fox, which in turn calls itself with different arguments, then during the deeper call to fox, the call stack will contain, from bottom to top, frames for main, fox, and fox. 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 fox frames will differ in that the higher one will contain the parameters for the deeper fox 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[edit]

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[edit]

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:

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

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[edit]

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:

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
          empty L

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 size field to the stack object.)

C++ STL stack class[edit]

In the C++ STL, std::stack, found in the <stack> header, is a template container capable of holding items of any (fixed) type, the type being supplied as a template argument. Hence, for example, stack<char> is a stack of characters. The container supplies the following member functions (note that T is the type of the elements of the stack):

• void push(const T& x): pushes x onto the stack.
• void pop(): performs a pop.
• T& top(): returns the element which is to be popped next
• size_type size(): returns the number of elements currently on the stack
• bool empty(): returns true if the stack is empty, false otherwise.

The stack 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 iteration through the elements of the stack. In such circumstances the STL stack 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 top followed by pop.