**Stacks**

An array is a *random access* data structure, where each element can be accessed directly and in constant time. A typical illustration of random access is a book – each page of the book can be open independently of others. Random access is critical to many algorithms, for example binary search.

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the push-down stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. A stack is a limited access data structure – elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.A stack is a recursive data structure. Here is a structural definition of a Stack:
a stack is either empty or |

**Implementation**

In the standard library of classes, the data type stack is an *adapter* class, meaning that a stack is built on top of other data structures. The underlying structure for a stack could be an array, a vector, an ArrayList, a linked list, or any other collection. Regardless of the type of the underlying data structure, a Stack must implement the same functionality. This is achieved by providing a unique interface:

```
public interface StackInterface<AnyType>
{
public void push(AnyType e);
public AnyType pop();
public AnyType peek();
public boolean isEmpty();
}
```

The following picture demonstrates the idea of implementation *by composition*.

Another implementation requirement (in addition to the above interface) is that all stack operations must run in **constant time O(1)**. Constant time means that there is some constant k such that an operation takes k nanoseconds of computational time regardless of the stack size.

**Array-based implementation**

In an array-based implementation we maintain the following fields: an array A of a default size (≥ 1), the variable top that refers to the top element in the stack and the capacity that refers to the array size. The variable top changes from -1 to `capacity - 1` . We say that a stack is empty when `top = -1` , and the stack is full when `top = capacity-1` .In a fixed-size stack abstraction, the capacity stays unchanged, therefore when top reaches capacity, the stack object throws an exception.In a dynamic stack abstraction when top reaches capacity, we double up the stack size. |

**Linked List-based implementation**

Linked List-based implementation provides the best (from the efficiency point of view) dynamic stack implementation. |

**Applications**

- The simplest application of a stack is to reverse a word. You push a given word to stack – letter by letter – and then pop letters from the stack.
- Another application is an “undo” mechanism in text editors; this operation is accomplished by keeping all text changes in a stack.

**Backtracking**. This is a process when you need to access the most recent data element in a series of elements. Think of a labyrinth or maze – how do you find a way from an entrance to an exit?Once you reach a dead end, you must backtrack. But backtrack to where? to the previous choice point. Therefore, at each choice point you store on a stack all possible choices. Then backtracking simply means popping a next choice from the stack. - Language processing:
- space for parameters and local variables is created internally using a stack.
- compiler’s syntax check for matching braces is implemented by using stack.
- support for recursion