Stack Data Structure

Introduction

• A stack is an example of Abstract Data Type (ADT), commonly used in most of the 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 one 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 used to store a collection of objects/data items.
• A stack is a list of elements in which an element 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. 

Features/Characteristics/Property of Stack

• It works on the principle of LIFO (last in, first out) or FILO(first in last out).
• The items can be added or removed only from the top position of the stack.
• All insertions and deletions operations take place at the same end i.e. at the top, so the last element added to the stack will be the first element removed from the stack.
• 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.
  • isFull : check if the stack is full.
  • isEmpty : check if the stack is empty/blank.

Representation/Implementation

• 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

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

Disadvantages

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

Uses/Applications

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