Introduction to Stack

Stack is an abstract data type with a predefined capacity. It is a linear data structure where we can store same type of Data in a particular order on which some operations are be performed.

Features of Stack

1. Stack is an ordered list of similar data type.
2. Stack is a LIFO(Last in First out) structure or we can say FILO(First in Last out).
3. push() function is used to insert new elements into the Stack and pop() function is used to remove an element from the stack. Both insertion and removal are allowed at only one end of Stack called Top(when stack is empty top is -1).
4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

When do we use stack?

Let’s take an Example of real life application which we often use in our daily life.

In MS-office we often use “BackSpace” key which deletes recent (push() deleted word into stack) word and when we press  “Ctrl+Z” it returns (pop() top of stack ) our deleted words.

Another application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack.

There are other uses also like:

1. Parsing
2. Expression Conversion(Infix to Postfix, Postfix to Prefix etc)

Implementation of Stack

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size. Here we will implement Stack using array.

Algorithm for PUSH operation

• Check if the stack is full or not.
• If the stack is full, then print error of overflow and exit the program.
• If the stack is not full, then increment the top and add the element.

code for push operation

Algorithm for POP operation

·        Checks if the stack is empty.

·        If the stack is empty, produces an error and exit.

·        If the stack is not empty, accesses the data element at which top is pointing.

·        Decreases the value of top by 1.

·        Returns success.

code for pop operation

TOP of Stack

It is the recent element of Stack. in starting top is -1 and keeps on increasing when push() function is called until reaches the maximum limit and when pop() function is called it gets decreased until top is not equal to -1.

Algorithm for isEmpty() function

It returns True if Stack is empty else return False Or we can say returns true if top of stack is -1.


code for isEmpty() function

Algorithm for isFull() function

Returns true if top of Stack is equal to the size of defined of Stack (Array).


code for isFull() function

to check running of this program click here