- In computer science, a stack is a last in, first out (LIFO) abstract data type and linear data structure.
- A stack can have any abstract data type as an element, but is characterized by two fundamental operations, called push and pop (or pull).
- The push operation adds a new item to the top of the stack, or initializes the stack if it is empty. If the stack is full and does not contain enough space to accept the given item, the stack is then considered to be in an overflow state.
- The pop operation removes an item from the top of the stack. A pop either reveals previously concealed items, or results in an empty stack, but if the stack is empty then it goes into underflow state (It means no items are present in stack to be removed).
- A stack pointer is the register which holds the value of the stack. The stack pointer always points to the top value of the stack.
- A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are those that have been on the stack the longest.
History
The stack was first proposed in 1946, in the computer design of Alan M. Turing (who used the terms "bury" and "unbury") as a means of calling and returning from subroutines. In 1957, the Germans Klaus Samelson and Friedrich L. Bauer patented the idea. The same concept was developed, independently, by the Australian Charles Leonard Hamblin in the first half of 1957
- Applications
6.1 Converting a decimal number into a binary number
6.2 Towers of Hanoi
6.2.1 Output: (when there are 3 disks)
6.2.2 First implementation (using stacks implicitly by recursion)
6.2.3 Second implementation (using stacks explicitly)
6.3 Expression evaluation and syntax parsing
6.3.1 Evaluation of an infix expression that is fully parenthesized
6.3.2 Evaluation of infix expression which is not fully parenthesized
6.3.3 Evaluation of prefix expression
6.3.4 Evaluation of postfix expression
6.3.5 Evaluation of postfix expression (Pascal)
6.4 Conversion of an Infix expression that is fully parenthesized into a Postfix expression
6.5 Rearranging railroad cars
6.5.1 Problem Description
6.5.2 Solution Strategy
6.5.3 A Three Track Example
6.6 Backtracking
6.7 Quicksort
6.8 The Stock Span Problem
6.8.1 An algorithm which has Quadratic Time Complexity
6.8.2 An algorithm which has Linear Time Complexity
6.9 Runtime memory management - Security