Queue, Stack, Graph, Tree

(Prepared by)
Dr. Thinn Thu Naing
Rector
University of Computer Studies, Taunggyi
Queue
 Queue
Definition Methods of Queue
A queue is a data structure used to • Enqueue: places an item at the
model a First-In-First-Out (FIFO) back of the queue;
strategy. Conceptually, we add to • Dequeue: retrieves the item at
the end of a queue and take away the front of the queue, and
elements from its front. removes it from the queue;
• Peek: retrieves the item at the
front of the queue without
Types of Queue
removing it from the queue
• A standard queue
• Priority Queue
• Double Ended Queue
 Standard Queue
• The main property of a queue is that we have access to the item at the front of
the queue.
• The queue data structure can be efficiently implemented using a singly linked list
• A singly linked list provides O(1) insertion and deletion run time complexities.
• The reason we have an O(1) run time complexity for deletion is because we only
ever remove items from the front of queues (with the Dequeue operation).

Applications of Queue
•CPU Scheduling in Processor
•Disk Scheduling in Secondary
Storage
•Job scheduling algorithms.
•Round robin scheduling.
•Recognizing a palindrome.
 Priority Queue
• a priority queue determines the order of its items by using a form of custom comparer
to see which item has the highest priority.
• the items in a priority queue being ordered by priority it remains the same as a normal
queue: It can only access the item at the front of the queue.
• a priority queue is to use a heap data structure (Heap tree).

Applications of Priority Queue

• Prim's algorithm implementation can be
done using priority queues.
• Dijkstra's shortest path algorithm
implementation can be done using priority
queues.
• A* Search algorithm implementation can be
done using priority queues.
• Priority queues are used to sort heaps.
• Priority queues are used in operating system
for load balancing and interrupt handling.
• Priority queues are used in huffman codes for
data compression.
• In traffic light, depending upon the traffic, the
colors will be given priority.
 Double Ended Queue
• a double ended queue allows Applications of deque
• Pallindrome checker.
to access the items at both
• A-steal job scheduling algorithm
the front, and back of the - The A-steal algorithm implements task
scheduling for multiple processors
queue.
(multiprocessor scheduling).
• A double ended queue is - The processor gets the first element
from the double ended queue.
commonly known as a
- When one of the processors completes
“Deque” execution of its own thread, it can steal a
• A deque applies no thread from other processors.
- It gets the last element from the deque
prioritization strategy to its of another processor and executes it.
• Undo-redo operations in software
items like a priority queue
applications.
does, items are added in
order to either the front of
back of the deque.
Stack
 Stack
Definition Methods of Stack

Stacks are, on an abstract level, • EmptyStack, the empty stack

equivalent to linked lists. They are • Push(element,stack), which

the ideal data structure to model a takes an element and pushes it

First-In-Last-Out (FILO), or Last-In- on top of an existing stack

First-Out (LIFO), strategy in search. • top(stack), which gives back

the top most element of a
stack
• Pop(stack), which gives back
the stack without the top most
element.
 Applications of Stack
• Expression evaluation (Arithmetic expression & problem solving)
– The NP-Complete problem

– Traveling Salesman Problem

– bin packing

– linear programming,

• Backtracking (Searching)
– game playing

– finding paths

– exhaustive searching

• Memory management, run-time environment for nested language features.

– Any modern computer environment uses a stack as the primary memory management model for a
running program
– native code (x86, Sun, VAX) or JVM, a stack is at the center of the run-time environment for Java, C++,
Ada, FORTRAN, etc.
Memory management (Memory Stack)
 Graph

Definition
• A Graph is a non-linear data structure
consisting of nodes and edges. The
nodes are sometimes also referred to as
vertices and the edges are lines or arcs
that connect any two nodes in the
graph.
the Graph in figure ,
• A Graph consists of a finite set of
the set of vertices V = {0,1,2,3,4} and
vertices(or nodes) and set of Edges
the set of edges E = {01, 12, 23, 34, 04, 14, 13}.
which connect a pair of nodes.

Types of Graph Representation

• Adjacency Matrix
• Adjacency List
 Adjacency Matrix

• Adjacency Matrix is a 2D array of size V x V where

V is the number of vertices in a graph.
• Let the 2D array be adj[][], a slot adj[i][j] = 1
indicates that there is an edge from vertex i to
vertex j.
Adjacency List

• An array of lists is used. Size of the array is equal

to the number of vertices. Let the array be array[].
An entry array[i] represents the list of vertices
adjacent to the ith vertex.
 Some examples Applications of Graph Theory

Contract Tracing using Graph Location Recognition Graph

Topological Map of
Railway Station
 Tree
Definition Tree’s terminology
A tree as consisting of nodes (also called vertices Root- a unique ‘top level’ node
or points) and edges (also called lines, or, in Child node - is connected to the
order to stress the directedness, arcs) with a given node via a branch
tree-like structure.
Parent node – is connected to the
given node (via an edge) on the level
above
Sibling : Nodes that have the same
parent are known as siblings
The depth or level of a node is given
by the length of this path.
The maximal length of a path in a
tree is also called the height of the
tree.
The size of a tree is given by the
Types of Tree number of nodes it contains.
• Quad Tree
• Binary Tree
• Binary Search Tree
• AVL Tree
• Heap Trees
 Quad-trees

Definition.- A quad tree is either

• (Rule 1) a root node with a value, or
• (Rule 2) a root node without a value and four quad tree children: lu (left upper),, ru
(right upper) , ll(left lower) and rl (right lower) , in which Rule 1 is the “base case”
and Rule 2 is the “induction step”.
• A quadtree is primitive if it consists of a single node/number, and that can be tested
by the corresponding condition:
 Application Areas of Quad-trees
precise geometric location of these
interfaces by using fine mesh cells in
• Computational Geometry
regions
• Games
• Physically based simulations
• generate “smart” meshes
 Binary Tree

Definition. A binary tree is either

(Rule 1) the empty tree EmptyTree, or
(Rule 2) it consists of a node and two binary trees, the left subtree and right subtree.
The primitive operators for binary trees are fairly obvious.
• EmptyTree, which returns an empty tree,
• MakeTree(v,l,r), which builds a binary tree from a root node with label v and two
constituent binary trees l and r.

• root(t), which returns the value

of the root node of binary treet,
• left(t), which returns the left
sub-tree of binary tree t,
• right(t), which returns the right
sub-tree of binary tree t.
 Binary Search Tree
Definition.
A binary search tree start with a root node with value x, where the left subtree of x
contains nodes with values < x and the right subtree contains nodes whose values are ≥
x. Each node follows the same rules with respect to nodes in their left and right subtrees.
The primitive operators for binary trees are fairly obvious.

Methods of Binary Search Tree

• Insertion
• Searching
• Deletion
• Tree Traversals
• Preorder
• Postorder
Binary Search Tree
• Inorder
Insertion node (Binary Search Tree)
Searching node (Binary Search Tree)
Deletion node (Binary Search Tree)
Deletion node (Binary Search Tree)
Deletion node (Binary Search Tree)
Deletion node (Binary Search Tree)
 Traversal (Binary Search Tree)

Preorder Traversal
The preorder algorithm, you visit the root first, then traverse the left
subtree and finally traverse the right subtree. (Root, Left, Right)
 Traversal (Binary Search Tree)

Postorder Traversal
The postorder algorithm, you visit the left subtree and traverse the right
subtree, finally traverse the root. (Left, Right, Root)
 Traversal (Binary Search Tree)

Inorder Traversal
The inorder algorithm, you visit the left subtree first, then traverse the
root and finally traverse the right subtree. (Left, Roof, Right)
 AVL Tree

• Adelson-Velsky and E.M. Landis invented the first self-balancing binary

search tree data structure, calling it AVL Tree.
• An AVL tree is a binary search tree(BST)with a self-balancing condition
stating that the difference between the height of the left and right
subtrees cannot be no more than one.
 Unbalanced Binary Search Tree & balanced AVL Tree

Fig (1) binary search tree represents the worst case scenario in which the running time
of all common operations such as search, insertion and deletion are O(n).

By applying a balance condition (Fig (2) , we ensure that the worst case running time
of each common operation is O(log n).

Fig (2) Balanced AVL Trees

Fig (1) Unbalanced Binary Search Tree
 AVL Tree Rotations

• A tree rotation is a constant time operation on a binary search tree that

changes the shape of a tree while preserving standard BST properties.
There are left and right rotations both of them decrease the height of a
BST by moving smaller subtrees down and larger subtrees up.
AVL Tree Rotations
AVL Tree Rebalancing
 Heap Tree
Definition

A heap tree is a complete binary tree which is either empty or satisfies the
following conditions:

• The priority of the root is higher than (or equal to) that of its children.

• The left and right subtrees of the root are heap trees.

Not valid Heap Tree

Valid Heap Tree
 Building Heap Tree from Array
Consider a simple example array if items from which a heap tree must be built:
5 8 3 9 1 4 7 6 2
i= 1 i=2 i=3 i=4 i=5 i=6 i=7 i=8 i=9

We can start by simply drawing the array as a tree, and see that the last 5 entries
(those with indices greater than 9/2 = 4) are leaves of the tree, as follows:

i= 1

i= 2 i= 3

i= 4 i= 5 i= 6 i= 7

i= 8 i= 9