Stack ^[1]

A Stack is a linear data structure to collect data elements in last in, first out order (LIFO). The only elementary operations are push and pop. Push adds one element on the top of stack, while pop removes an entry from the top of the stack and returns that element to the caller. Entries are removed from the stack in the reverse order of their additions. In practice, there is often a third operation. Peek retrieves the top element without removing the entry from the stack.

The stack is a natural structure to remember where to continue after some work was interrupted to do some more important tasks, which itself might be interrupted again, even recursively and multiple times. This applies to depth-first tree traversals like minimax search or evaluating nested arithmetical expressions.

Software Stack

A stack can be implemented through an array or a linked list, for instance in C-like pseudo code with a fixed sized array in conjunction with typical pre-increment and post-decrement:

int tos = -1; // index top of stack
int stack[STACKSIZE]; // fixed sized array

void push (int element) {
   if (tos == STACKSIZE - 1) throw stack overflow exception;
   stack[++tos] = element;
}

int pop () {
   if (tos == -1 ) throw stack underflow exception;
   return stack[tos--];
}

Hardware Stack

Most central processing units support a hardware stack (processor stack, call stack) as part of the main memory. Processors have a special register, pointing to the top of stack (stack pointer), and push and pop instructions respectively. Intel processors from 8080 until x86-64 let the stack grow from higher to lower addresses via pre-decrement push and post-increment pop.

push(register) ::= stack[--sp] := register
pop (register) ::= register := stack[sp++]

To implement such hardware stacks was motivated by control flow considerations of calling and returning from subroutines, possibly recursively as coined by Algol-like programming languages. A call instruction pushes the program address of the next instruction on the stack, just before it sets its instruction pointer register to the subroutine-address. After executing the subroutine, a trailing return instruction pops the return address from the stack into the instruction pointer, to continue the execution flow as expected. Additionally, high level procedural programming languages demanded local variables. While actual parameters were pushed before the call applying certain calling conventions of various platforms and compiler ^[2]^[3], the callee did accordant stack pointer manipulations, to reserve or allocate a stack frame for local, automatic variables. Intel's 16-bit 8086 introduced an additional register, intended as base pointer into a possible variable stack frame, and the option of dynamic frame re-allocation.

A typical 8086 stack frame with Pascal calling conventions, where the callee is responsible for balancing the stack. Similar stack layout appears in x86 with 32-bit extended registers (esp, ebp) and stack entries ^[4].

push word para1
push word para2
call foo
...

foo proc near
  push  bp
  mov   bp, sp
  sub   sp, 3*2  ; allocate space for three local 16-bit variables
  ...
  mov   sp, bp
  pop   bp
  ret   4        ; return and "pop" additional four bytes of the parameters

with following memory layout inside the scope of foo:

stack growth
^   <---- 16 bit ---->
|  +------------------+            +------+
   | local variable 3 | [bp-6] <---|  SP  |
   +------------------+            +------+
   | local variable 2 | [bp-4]
   +------------------+
   | local variable 1 | [bp-2] 
   +------------------+            +------+
   | saved bp         | <----------|  BP  |
   +------------------+            +------+
   | return address   |
   +------------------+
   | parameter  2     | [bp+4]
   +------------------+
   | parameter  1     | [bp+6]
|  +------------------+
v
higher addresses

Applications

Stack Calculator

The Reverse Polish or Postfix notation scheme as proposed in 1954 by Burks, Warren, and Wright ^[5] , was independently reinvented by Friedrich L. Bauer, Klaus Samelson ^[6] and Edsger W. Dijkstra in the early 1960s to coin and utilize the stack data structure to efficiently evaluate expressions, likely after parsing infix notation recursively, which is actually a depth-first traversal of a expression tree.

Infix:

(1 + 2)*(3 + 4)

Infix Tree:

       *
   +       +
 1   2   3   4

Postfix Stack:

 push 1
 push 2
 add
 push 3
 push 4
 add
 mul

Many todays compiler and interpreter work that way, so does the Java Virtual Machine. Reverse Polish notation is further utilized in the Forth Stack-oriented programming language.

Depth-First Search

In computer game programming, a stack of nodes is also the appropriate data structure in depth-first tree search, like Minimax or Alpha-beta. Immediately before a move is made to search further, the node is pushed on the stack - and popped back while unmaking. Despite global state variables like a board representation, which are updated incrementally, programs implicitly use the processor stack by passing parameters to a recursive search routine with local variables. A software stack is obligatory for an iterative search, and likely implemented as array indexed by ply.