Stack ( ADT ) Data Structure

Stack ( ADT ) Data Structure :

* Stack is an ADT woks on the principle Last In First Out (LIFO)
* The last element add to the stack is the first element to be delete.
* Insertion and deletion can be takes place at one end called TOP.
* It looks like one side closed tube.
* The add operation of the stack is called push operation
* The delete operation is called as pop operation.
* Push operation on a full stack causes overflow.
* Pop operation on an empty stack causes underflow.
* SP is a pointer, which is used to access the top element of the stack.
* If you push elements that are added at the top of the stack;
in the same way when we pop the elements, the element at the top of the stack is deleted.,

For example the following Fig give an idea about the stack.

From the above Fig 01 it is clear that the size of the stack is having 4Locations and sp = -1 indicates that the stack is empty and we can push the new elements into the stack. Now the fig 02 shows how the stack grows, when we push an elements 12, 13, 14 into the stack. The fig 03 shows the status of the stack after popping 2 times. Now performing (one more) pop operation one more time on the above stack causes an error known as "stack under flow". The fig 04 shows the content of the stack after pushing 16, 17, 18, and 19. If you try to add one more element stack generate error "stack over flow".

Operations of stack:

There are two operations applied on stack they are 1 push 2. pop. While performing push & pop operations the following test must be conducted on the stack.

1) Stack is empty or not

2) Stack is full or not


Push:

Push operation is used to add new elements in to the stack. At the time of addition first check the stack is full or not. If the stack is full it generates an error message "stack overflow".

Pop:

Pop operation is used to delete elements from the stack. At the time of deletion first check the stack is empty or not. If the stack is empty it generates an error message "stack underflow".

Assumptions:

SP stack pointer whose initial value is -1

max_stack is the size of the queue

stack [] is an array

Element is the elements to be added or deleted

Algorithm to push elements into the stack :-

step :- 1) start

step :- 2) take the element to push into stack

step :- 3) If (Sp == max_stack)

display "The stack is full"

else

{ Sp = Sp+1

stack [Sp] = item
}

step :- 4) return to main program

Algorithm to pop elements from the stack :-

step :- 1) start

step :- 2) if (Sp == -1)

display "stack is empty"

else

{ element = stack[Sp]

Sp = Sp -1
}

step :- 3) return element

Classification of Data structures

Data structures can be classified as

· Simple data structure

· Compound data structure

· Linear data structure

· Non linear data structure

Simple Data Structure:

Simple data structure can be constructed with the help of primitive data structure. A primitive data structure used to represent the standard data types of any one of the computer languages. Variables, arrays, pointers, structures, unions, etc. are examples of primitive data structures.

Compound Data structure:

Compound data structure can be constructed with the help of any one of the primitive data structure and it is having a specific functionality. It can be designed by user. It can be classified as

1) Linear data structure

2) Non-linear data structure

Linear data structure :

Collection of nodes which are logically adjacent in which logical adjacency is maintained by pointers

(or)

Linear data structures can be constructed as a continuous arrangement of data elements in the memory. It can be constructed by using array data type. In the linear Data Structures the relation ship of adjacency is maintained between the Data elements.

Operations applied on linear data structure :

The following list of operations applied on linear data structures

1. Add an element

2. Delete an element

3. Traverse

4. Sort the list of elements

5. Search for a data element

By applying one or more functionalities to create different types of data structures

For example Stack, Queue, Tables, List, and Linked Lists.

Non-linear data structure:

Non-linear data structure can be constructed as a collection of randomly distributed set of data item joined together by using a special pointer (tag). In non-linear Data structure the relationship of adjacency is not maintained between the Data items.

Operations applied on non-linear data structures :

The following list of operations applied on non-linear data structures.

1. Add elements

2. Delete elements

3. Display the elements

4. Sort the list of elements

5. Search for a data element

By applying one or more functionalities and different ways of joining randomly distributed data items to create different types of data structures. For example Tree, Decision tree, Graph and Forest