# Stack

Stack is one of the fundamental data structures in computer science and it is used in many algorithms and applications. As an example, stack is used:

- implicitly in recursion;
- for expression evaluation;
- to check the correctness of parentheses sequence;
- etc.

## Stack ADT

Well illustration from the real world is a stack of books, where you can operate with a "top" of the stack only. We will dedicate six operations on the stack. You can put a book on top** (push); **look, which one lays on top of a stack** (peek)** and remove a topmost book **(pop) **and check, if stack is empty **(isEmpty).** Also, there are two operations to create and to destroy a stack. Let us structure them up in the following list.

### Operations

**Stack create()**

creates empty stack

**boolean isEmpty(Stack s)**

tells whether the stack**s**is empty

**push(Stack s, Item e)**

put**e**on top of the stack**s**

**Item peek(Stack s)**

returns topmost element in stack**s**

*Precondition:***s**is not empty

**pop(Stack s)**

removes topmost element from the stack**s**

*Precondition:***s**is not empty

**destroy(Stack s)**

destroys stack**s**

*Note.* In different sources **peek** operation may be called **top.**

### Axioms

- newly created stack is empty;
- after pushing an item to a newly created stack, it becomes nonempty;
- peek returns the most recently pushed item;
- stack remains untouched, after a pair of push and pop commands, executed one after another.

## Example

Sketchy, stack can be shown like this:

## Implementations

We are going to discuss two implementations of the Stack ADT. Each of them has it's own advantages and disadvantages, which are examined in the articles below:

- array-based stack implementation;
- linked list based stack implementation.

## Visualizers

## Recommended books

- Cormen, Leiserson,
Rivest.
**Introduction to algorithms.****(Theory)** - Aho, Ullman, Hopcroft.
**Data Structures and Algorithms.****(Theory)** - Robert Lafore.
**Data Structures and Algorithms in Java.****(Practice)** - Mark Allen Weiss.
**Data Structures and Problem Solving Using C++.****(Practice)**

## Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.

Every dollar helps!