Stacks

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 linked list is a sequential access data structure, where each element can be accesed only in particular order. 

Stacks

A stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle.  In the pushdown 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 it consistes of a top and the rest which is a stack;

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.
• 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

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.
• 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.