Stacks¶
Stacks are an abstract data type with the following basic operations:
push that puts an element on the top of the stack,
top that returns the element at the top of the stack, and
pop that removes the topmost element of the stack.
Thus stacks are like queues (see Section Queues and Deques) but with
“last in, first out” (LIFO) semantics.
Obviously,
stacks are easy to implement with linked lists, resizable arrays or deques (see Section Queues and Deques).
Or in other word, linked lists, resizable arrays and deques implement the stack abstract data type.
For instance,
in the C++ vector resizable array class,
the push_back method corresponds to the push operation of the abstract data type,
pop_back corresponds to pop, and
back corresponds to top.
Implementations of stacks in some standard libraries:
In Scala, the Stack class implements stacks by using the ArrayDeque class.
In C++, the stack class allows the user to select the underlying container class from list, vector or deque, the default being deque at the moment.
In Java, Stack implements stacks with a variant of resizable arrays but use of ArrayDeque is recommended instead.
Example
The Scala code below shows a simple evaluator for expressions in the reverse Polish notation. The idea is that
when a numeric value is read, it is pushed in the stack, and
when a binary operator is read, two topmost elements of the stack are popped, the operator applied on then, and the result is pushed back in the stack.
def evaluate(input: String): Int = {
val stack = new collection.mutable.Stack[Int]()
input.trim.split("\\s+").foreach(_ match {
case "+" => stack.push(stack.pop() + stack.pop())
case "*" => stack.push(stack.pop() * stack.pop())
case x => stack.push(x.toInt)
})
stack.top
}
// evaluate("2 4 3 * 3 + * 12 +") results in 42 as 2*((4*3)+3)+12 = 42
The figure below shows how the stack contents evolve when the input symbols “2 4 3 * 3 + * 12 +” are read. The stacks are drawn such that the topmost element is, well, topmost.
