Stacks

3.1 Introduction

A Stack is a non-primitive linear data Structure. It is a ordered list in which addition and deletion of data items is done only from one end, known as top of stack (TOS). As all the deletions and insertions in a stack is done from the top of the stack the last added element will be the first to be removed from the stack that is the reason why stack is called Last in first out (LIFO) type of list.

3.2 Stack Implementation
Stack can be implemented in two ways:
(i) Static implementation: - It uses array to create stack.
(ii) Dynamic implementation: - Also called linked list representation and uses pointers to implement the stack type of data structure.

3.3 Operations on Stack
(i) PUSH
(ii) POP
(iii) PEEP

3.4 Applications of Stacks

1. Evaluation of Postfix Expression
2. Conversion of infix to Postfix
3. Conversion of infix to Prefix
4. Validity of an Expression

Experiment 1

Aim – Write a program to perform push and pop operations on stack.
Theory- The process of adding a new element to the top of stack is called PUSH operation and after every push operation the top of the stack is incremented by one. In case the array is full and no new element can be accommodated, it is called overflow condition.

The process of deleting an element from the top of the stack is called POP operation and after every pop operation the top of the stack is decremented by one.In case the array is empty , the condition is called underflow condition.
The process of accessing the elements is PEEP operation.

Algorithm- (PUSH)
Let stack [Maxsize] is an array for implementing the stack.

1. [Check for stack overflow]
If Top = Maxsize – 1, then : print : overflow and exit
2. [increment Top by one
Set Top = Top + 1
3. [Insert item in the new Top position]
Set stack[Top] = item
4. Exit

Algorithm- (POP)

Let stack[Maxsize] is an array for implementing the stack and assign to variable item.
2. [Check for stack underflow]
If Top < 0 then :
Print : “Stack overflow” and Exit
Else [Remove the top element]
Set Item = Stack[Top]
3. [decrement the Stack top]
Set Top = Top – 1
4. [Return the Deleted Item from the stack]
5. Exit