A stack or LIFO (last in, first out) is an abstract data type that serves as a collection of elements.

It has following principal operations:

  1. Push- which adds an element of the collection.
  2. Pop- which removes the last element that was added. In the stack, both the operations of push and pop takes place at the same end that is top of the stack.
  3. Peek: Get the topmost item.

A stack is a sequence of elements such that each new element is added (pushed) onto one end, called the top of the stack, and an element is removed (popped) from the same end. Also, known as a FILO (First In Last Out) buffer.

There are two ways to implement a stack:

The complexity of Stack:

 

Time Complexity

Space Complexity

 

Average

Worst

Worst

Data Structure 

 Access 
 Search 
 Insertion 
 Deletion 
 Access 
 Search 
 Insertion 
 Deletion 
 

Stack

Θ(n) Θ(n) Θ(1) Θ(1) O(n) O(n) O(1) O(1) O(n)

 

Examples:

  • Application
    • Undo operation,
    • Back feature in web browser
    • Backtracking,
    • Knight tour problem,
    • Rat in a maze,
    • N-queen problem
    • Sudoku 
  • Algorithm
    • Tower of Hanoi,
    • Tree traversals,
    • Stock span problem,
    • Histogram problem
    • Depth First Search