Stack Data Structure

Introduction of Stack Data Structure

• A stack data structure is an example of an Abstract Data Type (ADT), commonly used in most programming languages.
• A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning that the last element added to the stack is the first to be removed. It can be envisioned as a collection of elements with two primary operations: push and pop.

Definition

• A stack is a basic, linear, and non-contiguous data structure that stores objects/data items.
• A stack is a list of elements in which a component is always inserted or deleted one at a time from only one/same end, usually called the top of the stack. 
• A stack is a storage structure that stores information in such a way that the last item stored is the first item retrieved. 
• A stack is a collection of elements with two primary operations: push (to add a new/fresh element to the top of the stack) and pop (to remove the existing element from the top of the stack). 

Features/Characteristics/Property of Stack

• The stack follows a Last-In-First-Out (LIFO) order, meaning the last element added is the first one to be removed, or FILO(first in last out) meaning the first element added is the last one to be removed.
• The items can be added or removed only from the top position of the stack.
• All insertions and deletions operations occur at the same end, i.e., at the top, so the last element added to the stack will be the first element removed.
• When a stack is created, the stack base remains fixed while the stack top changes as elements are added and removed.
• The most and first accessible element in the stack is the top and the least and last accessible element is the bottom of the stack.

Examples of Stack

There are the following popular examples of stack found in our real/daily-to-daily life –

• The stack of trays in a cafeteria.
• The stack of Plates in a cupboard.
• The stack of Playing Cards.
• The stack of (making) Breads.
• The stack of Coins.

Operations in Stack

• The basic operations that occur in the stacks are – 
  • Push( ) : When a new data item/element is added/inserted at the top position in the stack is called a Push operation.
  • Pop( ) : When an existing data item/element is removed/deleted from the top of a stack is called Pop operation.
  • Top( ) : Get/access the top data element of the stack, without removing it.
  •  Peek( ) : Returns the element at the top of the stack without removing it.
  • isFull( ) : check if the stack is full.
  • isEmpty( ) : check if the stack is empty/blank and return true if the stack is empty, otherwise false.
  • size( ) : Returns the number of elements in the stack.

Representation/Implementation of Stack

• A stack can be represented in two forms – (i) As an Array form and (ii) As a Linked List form.

(i) As an Array form :

• • When a stack is represented in the form of an array, its size is restricted/fixed before the execution. This is called the size of the stack.
  • When the number of new elements to be added should not exceed the given maximum size of the stack.
  • If we attempt to add a new element beyond the maximum size, we will encounter a stack overflow condition. Similarly, we cannot remove/delete elements below the base size of the stack. If such is the case, we will reach a stack underflow condition.

(ii) As a Linked List form :

Advantages of Stack Data Structure

• It allocates memory dynamically and in a non-contiguous form.
• We can easily add or remove elements from the stack.

Disadvantages of Stack Data Structure

• It is comparatively less flexible.
• Random access does not occur.

Uses/Applications of Stack Data Structure

• It is used by compilers to check for balancing of parentheses, brackets, and braces in an expression.
• It is used to convert an infix expression into its postfix/prefix form. These postfix or prefix notations/expressions are used in computers to express some expressions that are useful for processing.
• In recursion, all intermediate arguments and return values are stored on the processor’s stack during processing.
• During a function call, the return address and arguments are pushed onto a stack, and on return, they are popped off.
• They are used to implement functions, parsers, expressions, evaluation, backtracking problems, etc.
• They are used in memory management.