STACKS

It is an ordered collection of data item where insertion and deletion takes place at same
end. Insertion and deletion can be done from top position of the stack, opposite to the top is called
base. Stacks follows „LIFO‟ rule [Last In First Out].
Push:
Element inserted into the stack is called as push operation.
Pop:
Element deleted from the stack is called pop operation.

Operations performed on Stacks

1) stack () : This operation is used to create new empty stack ( no parameters are required returns
nothing)
(2) push (item) : This operation is used 10 add a new data item to the top of stack [ parameters are
required but returns nothing].
(3) pop() : This operation is used to remove the top item from the stack [no parameters are required
but returns data item]
(4) isempty() : This operation is used to check whether the stack is empty or not [returns the
Boolean value].
(5) size(): This operation returns number of data items in the stack [ returns integer value]
(6) peek() : This operation returns top item from the stack but it is not modified.
 (i) Algorithm for PUSH Operation:
STACK is the array that contains N elements and TOP is the pointer to the top element of the
array. ITEM the element to be inserted. This procedure inserts ITEM into the STACK.
Step 1: if (TOP = N -1) then [check overflow]
PRINT “Stack is full”
Exit
End of if
Step 2: TOP = TOP + 1 [Increment the TOP]
Step 3: STACK[TOP] = ITEM [Insert the ITEM]
Step 4: Return

(ii) Algorithm for POP Operation:

STACK is the array that store N items. TOP is the pointer to the top element of the array.
This procedure deleted top element from STACK.
Step 1: if (TOP = NULL) then [check underflow]
PRINT “Stack is empty”
Exit
End of if
Step 2: ITEM = STACK[TOP] [Copy the top element]
Step 3: TOP = TOP – 1 [Decrement the top]
Step 4: Return

Applications of stacks
1. Reversing a string
2. Undo mechanism
3. Back tracking
4. Expression evaluation
5. Tower of honai
6. Quick sort
 QUEUES

It is an ordered collection of data item where insertion and deletion takes place at different
ends
In the queue only two operations are allowed Enqueue and Dequeue.
Enqueue : It means to insert an item into the back of the queue.
Dequeue : It means removing the front item from the queue.
It follows “FIFO” rule [First In First Out]

Types of Queues:
1. Simple Queue
2. Circular Queue
3. Priority Queue
4. Double ended Queue
1. Simple Queue:
In Simple queue insertion occurs at the rear end of the list, and deletion occurs at the front
end of the list.

2. Circular Queue:
A circular queue is a queue in which all nodes are treated as circular such that the last node
follows the first node.

3) Priority Queue:
In this type of Queue insertion and deletion can be done from any position based on the pre-
set priority.

4) Double ended Queue :

In this type of Queue insertion and deletion can be done from both the ends.
 Operations performed on Queues:

(1) Queue() :
This operation is used to create a new empty Queue [ no parameters returns nothing]
(2) Enqueue() :
This operation is used to (insert) add a new item to the rear end of queue [ parameters are
required returns nothing]
(3) dequeue() :
This operation is used to remove data item from front end of queue [no parameters are
required but returns data item]
(4)size():
This operation returns number of data items in the queue [from the queue] [returns integer
value]
(5)isempty() :
This operation is used to check wheather the queue is empty or not [returns Boolean value]

(i) Algorithm to insert an element into the queue [ enqueue]

Let QUEUE be the linear array consisting of N elements. FRONT is the pointer that
contains the location of the element to be deleted and REAR contains the location of the
inserted element. ITEM is the element to be inserted.

Step 1: If REAR = N-1 Then [Check for overflow]

PRINT “Overflow”
Exit
Step 2: If FRONT = NULL Then [Check whether QUEUE is empty]
FRONT = 0
REAR = 0
Else
REAR = REAR + 1 [Increment REAR Pointer]
Step 3: QUEUE[REAR] = ITEM [Copy ITEM to REAR position]
Step 4: Return

(ii) Algorithm for deletion from the queue [ dequeue]

Let QUEUE is the linear array consisting of N elements. FRONT is the pointer that
contains the location of the element to be deleted and REAR contains the location of the inserted
element. This algorithm deletes the element at FRONT position.

Step 1: If FRONT = NULL Then [Check whether QUEUE is empty]

PRINT “Underflow”
Exit
Step 2 : ITEM = QUEUE[FRONT]
Step 3: If FRONT = REAR Then [If QUEUE has only one element]
FRONT = NULL
 REAR = NULL
Else
FRONT = FRONT + 1 [Increment FRONT pointer]
Step 4: Return

Application of Queue
 1. Printer server rooting
 2. Multi-programming
 3. CPU – scheduling
 4. Round-robin system
 5. Some process of operating system
 6. Simulation etc…

Linked list
It is a linear collection of data items called nodes and each node referred by means of
pointers
Linked list used dynamic memory allocation [ dynamic : as and when required we can
increase or decrease the memory allocation]

Types of linked lists

1. Singly linked list (SLL)
2. Doubly linked list (DLL)
3. Circular linked list (CLL)
1) Singly linked list:
In this type each node has 2 parts one is data field and another one is link field of next node.

2) Circular linked list :

In this type all the nodes are connected in a circular path the last node follows the first node.

3) Doubly linked lists:

It is a linked list in which each node is points both to the next node and also to the previous
node.
In doubly linked list each node contains three parts – FORW, BACK and INFO.

 BACK: It is a pointer field containing the address of the previous node.

 FORW: It is a pointer field that contains the address of the next node.
 INFO: It contains the actual data.
Operations on linked lists:
 1. Creating a linked list
 2. Traversing a linked list
 3. Inserting an item into a linked list
 4. Deleting an item from the linked list
 5. Searching an item in the linked list
 6. Merging two or more linked lists

Non-linear data structure

A non-linear data structure is a data structure in which a data item is connected to several
other data items, so that a given data item has the possibility to reach one-or-more data items.
The data items in a non-linear data structure represent hierarchical relationship. Each data
item is called a node.
Ex: graph, tree

Tree:
A tree is a collection of root node and its sub nodes.

Root node:
A node at the top of a tree which do not have any parent node.
Leaf node or chain node:
A node at bottom of a tree which do not have any sub nodes.
Internal node:
A node which have both parent and leaf node.
Height:
The number of nodes traversed from root.
Depth:
The height of a node is the length of the longest downward path to a leaf from that node. The
height of the root is the height of the tree.
BINARY TREE
The simplest form of tree is a binary tree. A binary tree is a tree in which each node has at
most two descendants - a node can have just one but it can‟t have more than two.

Graph:
A graph is a collection of vertices and edges which are connected. A graph is a collection
of nodes called vertices, and the connections between them, called edges.

Undirected and directed graphs

When the edges in a graph have a direction, the graph is called a directed graph or digraph,
and the edges are called directed edges or arcs.

The following diagram shows a graph with 5 vertices and 7 edges. The edges between A and D and
B and C are pairs that make a bidirectional connection, represented here by a double-headed arrow.

****************** ********************