Stack is an ordered list in which insertion
and deletion are done at one end, called top.
Last in First out (LIFO) or
First in Last out (FILO)
Push- element is inserted in a stack
Pop- removed from the stack
Overflow- trying to pop out an empty stack is called underflow and trying to push
an
element in a full stack
boolean empty() -Tests if this stack is empty. Returns true if the stack is empty,
and
returns false if the stack contains elements.
Object peek( )- Returns the element on the top of the stack, but does not remove
it.
Object pop( ) -Returns the element on the top of the stack, removing it in the
process.
Object push(Object element) - Pushes the element onto the stack. Element is
also returned.
int search(Object element)- Searches for element in the stack. If found, its offset
from the top of the stack is returned. Otherwise, -1 is returned.
Queue Data Structure
“First in, First out” (FIFO), linear data structure that is open
at both ends and the operations are performed in First In
First Out (FIFO) order. all additions to the list are made at one end (back of the
queue)
all deletions from the list are made at the other end(front of the queue)
Types of Queues
Simple Queue: only insert the element at the back and remove the element from
the
front of the queue
Double-Ended Queue (Dequeue): insertion and deletion operations, both can be
performed from both
ends.
2 Types of Queue
Input Restricted Queue: the input can be taken from only one end but
deletion can be done from any of the ends.
Output Restricted Queue: the input can be taken from both ends but
deletion can be done from only one end.
Circular Queue: the last position is connected back to the first position.
Priority Queue: the elements are accessed based on the priority assigned to them.
Ascending Priority Queue: elements are arranged in increasing order
Descending Priority Queue: elements are arranged in decreasing order
Basic Operations of Queue Data Structure
Enqueue (Insert): Adds an element to the rear of the queue.
Dequeue (Delete): Removes and returns the element from the front of the queue.
Peek: Returns the element at the front of the queue without removing it.
Empty: Checks if the queue is empty.
Full: Checks if the queue is full.
IMPLEMENTATION OF QUEUES
1.array
2. linkedlist
Enqueue = If rear == capacity-1,
Dequeue= If rear ==-1
enQueue(): adds a new node after the rear and moves the rear to the next node.
deQueue(): removes the front node andmoves the front to the next node.
Tree Data Structure
non-linear data structure
Binary tree- each node can have a maximum of two children linked to it.
Ternary Tree- each node has at most three child nodes, usually distinguished
as “left”, “mid” and “right”.
N-ary Tree or Generic Tree- each node is a data structure that consists of
records and a list of references to its children(duplicate
references are not allowed).
General tree -A general tree data structure has no restriction on
the number of nodes.
Balanced tree - If the height of the left sub-tree and the right sub-tree is equal or
differs at most by 1
Basic Operations of Tree
Create – create a tree in the data structure.
Insert − Inserts data in a tree.
Search − Searches specific data in a tree to check whether it is
present or not.
Traversal:
Depth-First-Search Traversal
Breadth-First-Search Traversal
Graph Data Structure
graph data structure mainly represents a network
connecting various points. These points are termed as
vertices and the links connecting these vertices are called
‘Edges’. So a graph g is defined as a set of vertices V and
edges E that connect these vertices.
Different Variants of Graph
1. Directed Graph- the edges have a specific direction. They originate from
one vertex and culminate into another vertex.
2. Weighted Graph- a weight is associated with each edge of the graph. The
weight normally indicates the distance between the two vertices.
Graph Representation In Java
Adjacency Matrix -linear representation of graphs. This matrix stores the mapping
of vertices and edges of the graph. In the adjacency matrix, vertices of the graph
represent rows and columns.
Adjacency List- Instead of representing a graph as an adjacency matrix which is
sequential in nature, we can also use linked representation. This linked
representation is known as the adjacency list. An adjacency list is nothing but a
linked list and each node in the list represents a vertex.
