Introduction

Stack is a linear data structure to store and manipulate data which follows LIFO (Last In First Out) order during adding and removing elements in it.

To understand stack operations more clearly, Imagine Fisher-Price Rock-a-Stack game. This game has one stand in which one end is closed and the other end is open from which we add or remove rings. While playing this game assume that we are allowed to add or remove only one ring at a time.

If we notice we are able to remove only the top ring from the stand, it means Last inserted ring gets removed First. This is called Last In First Out ordering. The ring which is inserted into the stand gets removed only if all rings are out. That means FIrst inserted ring gets removed last. This is called First In Last Out ordering.

Operations

Stack is an abstract data type which allows following operations :

• Push : Add an element to the top of the stack.
• Pop : Remove element from the stack.
• IsEmpty : Check if there is any element in the stack.
• Peek : Returns the element at the top of the stack.

Incase of stack, both push and pop operations happen at only one point which is called last.

Applications

In real life we see many examples of stack data structure like stack of plates, stack of books, cd/dvd stand etc. Apart from real life stack data structure is very effective to solve many use cases or applications in the computer science field.

• Undo and Redo Operation in Text Editor.
• Browser History for back and forward clicks.
• Function call stack in program
• Code syntax matching for a few programming languages like HTML, XML etc.
• Tower of Hanoi game

Implementation

Stack is a linear data structure to store and manipulate data which follows LIFO (Last In First Out) order during adding and removing elements in it. There are two basic ways to implement stack data structure, one is using array and the other is using linked list data structure :

• Array based Implementation
  • Using Array or Static Array (Array size is fixed and has to be given during initialization)
  • Using Dynamic Arrays or Resizable Arrays (Arrays can grow or shrink based on requirement)
  • Linked List Based Implementation