Prepared By : Uday Shah (HOD-IT)
E-Mail : rupareleducation@gmail.com
Contact No : 7600044051
Data Structure Unit 2
Question: What is Stack?
· Stack is an abstract data type, commonly
use in most programming language.
· Stack can be categorized in static stack
or dynamic stack.
· Concept of stack are commonly used in
data structure.
· In
real word, stack allow operation at only one end the real life example
of stack is plates on counters or cards.
· According to above example , we can
place or remove cards or plate from top
of the stack only.
·
At any given time, we can only access the top
element of the stack.
·
It store the information on the base of
LIFO system.
·
Here the element which is place last
access first.
·
Following is some list of operation
supported by the stack linear data structure.
- Push
- Peep
- Pop
Push Operation:
·
Push operation is allow user to insert
an information in the stack.
·
But before inserting, we must 1st
check that enough space is available or not.
· If require space is not available then
it display an appropriate message on the screen that is stack is overflow.
·
Otherwise increment in top by 1.
· And store the data into the stack.
·
Following is a diagram of push function
in stack.
Draw Diagram Here
·
According to above diagram, If stack is
empty then value of top is
-1
but here the value of top is 1 so, it allow user to input an element in to
stack.
Peep Operation:
·
Peep operation of stack is used to display all element which are
exist in a stack.
·
In this operation, top traversal from
top to bottom before handling this operation 1st of all we have to
check that “elements are available or not in stack”.
·
If there is a no any element in the
stack then the value of tos in -1 and display appropriate message on the screen
that is “stack in empty”
·
Other wise it display data in LIFO
manner.
·
Following is a diagram of peep
operation.
Draw Diagram Here
·
According to above diagram, peep function allow tos to
traversal from top to bottom.
·
And data displaying sequential order.
Pop Operation:
·
This is used to removing or deleting and
existing element from the stack.
·
Stack is always inserted and remove at
one end It means there is no any choice for remaining an item.
·
But ,The value of tos is decrease by one
to their position to lower position in the stack.
·
Before
delete or remove element from the stack check the condition that
elements are available or not in a stack.
·
If stack has no any element then it
display appropriate message on the screen that is stack is empty.
·
Otherwise the value of tos is -1.
·
Actually the element are store inside
the array but it not display while displaying other element.
·
Following is a diagram of pop operation:
Draw Diagram Here
·
According to above diagram, Before
deleting an element from the stack the position of tos is
at the 30.
·
And after the delete the value of tos is
-1.
Means the posting to the value of 20.
Question : Applications of Stack
·
Here you will learn about
applications of stack.
·
Stack is an abstract data type
and a data structure that follows LIFO (last in first out) strategy. It means
the element added last will be removed first. Stack allows two operations push
and pop. Push adds an element at the top of the stack and pop removes an
element from top of the stack.
·
Below I have mentioned few
applications of stack data structure.
Applications of Stack
·
Expression Evaluation
Stack is used to evaluate
prefix, postfix and infix expressions.
·
Expression Conversion
An expression can be
represented in prefix, postfix or infix notation. Stack can be used to convert
one form of expression to another.
·
Syntax Parsing
Many compilers use a stack for
parsing the syntax of expressions, program blocks etc. before translating into
low level code.
·
Backtracking
Suppose we are finding a path
for solving maze problem. We choose a path and after following it we realize
that it is wrong. Now we need to go back to the beginning of the path to start
with new path. This can be done with the help of stack.
·
Parenthesis Checking
Stack is used to check the
proper opening and closing of parenthesis.
·
String Reversal
Stack is used to reverse a
string. We push the characters of string one by one into stack and then pop
character from stack.
·
Function Call
Stack is used to keep
information about the active functions or subroutines.
Polish Expression:
Polish Expression is a notation form for expressing arithmetic,
logic and algebraic equations. Its most basic distinguishing feature is that
operators are placed on the left of their operands. If the operator has a
defined fixed number of operands, the syntax does not require brackets or
parenthesis to lessen ambiguity.
Polish notation is also known as prefix notation, prefix Polish
notation,
Infix, Postfix and Prefix notations are three different but
equivalent ways of writing expressions. It is easiest to demonstrate the
differences by looking at examples of operators that take two operands.
For ex. :
A * ( B + C ) / D
Infix notation: X + Y
·
Operators
are written in-between their operands.
·
This
is the usual way we write expressions.
·
An
expression such as A * (B + C) / D is
usually taken to mean something like: "First add B and C together, then
multiply the result by A, then divide by D to give the final answer."
·
Infix
notation needs extra information to make the order of evaluation of the
operators clear: rules built into the language about operator precedence and associatively,
and brackets ( ) to allow users to override these rules.
·
For
example, the usual rules for associatively say that we perform operations from
left to right, so the multiplication by A is assumed to come before the
division by D.
·
Similarly,
the usual rules for precedence say that we perform multiplication and division
before we perform addition and subtraction.
Postfix notation (also known as
"Reverse Polish notation"): X Y +
Operators are written after their operands.
The infix expression given above is equivalent
to A B C + * D / .The order of
evaluation of operators is always left-to-right, and brackets cannot be used to
change this order.
Because the
"+" is to the left of the "*" in the example above, the
addition must be performed before the multiplication.
Operators act on values immediately to the left of them. For
example, the "+" above uses the "B" and "C". We
can add brackets to make this explicit: ( (A (B C +) *) D /) Thus,
the "*" uses the two values immediately preceding: "A", and
the result of the addition. Similarly, the "/" uses the result of the
multiplication and the "D".
Prefix notation (also known as
"Polish notation"): + X Y
Operators are written before their operands. The expressions
given above are equivalent
to / * A + B C D as for Postfix,
operators are evaluated left-to-right and brackets are sufficient. Operators
act on the two nearest values on the right. It again added brackets to make
this clear: (/ (* A (+ B C) ) D)
In all three versions, the operands occur in the same order, and
just the operators have to be moved to keep the meaning correct.
Queue
Que: 1 What is Queue?
·
Queue is also an abstract data type or linear data
structure.
·
It help user to store data in a sequential.
·
Queue is work on FIFO manner.
·
Queue is most useful linear data structure and use in real life, example like Queue at
ticket window.
·
Queue has two pointer that is front pointer and
rear pointer.
·
Front is also called head and rear called the tail.
·
Queue can be categorizes in following category.
A. Simple Queue
B. Circular Queue
C. Double Ended Queue
D. Priority Queue
Simple Queue:
·
Simple Queue represent a linear data structure to
store data in a linear format.
·
Simple queue has open and close end.
·
One end is always used to insert a data while
another end is always used remove data.
·
Queue follow FIFO algorithm it means data items are
store 1st will be access 1st .
·
Simple queue have 3 different operation:
Push Operation
Peep Operation
Pop Operation
Push
Operation:
·
Queue provide two separate value which initialize
with -1 means queue is empty.
·
Push operation is generally used to insert an
element in a queue.
·
But, before an inserting an element, Check the
condition in a queue that enough space is available or not.
·
If enough space is not available the it display an
appropriate message on the screen that is Queue is overflow.
·
Otherwise allow to insert an element into the
queue. If Inserted element was 1st then increment in front by 1
otherwise increment in rear by 1.
·
Following is
diagram of push function in a queue.
Diagram
·
According to above diagram, if Queue is empty then
value of front and rear is -1.
·
While in second diagram, After inserting an element
value of front and rear increment by 1.
Pop
Operation:
·
Pop operation is used to remove or delete an element in a queue.
·
Before Executing a pop operation first check the
condition that elements are available or
not.
·
If queue has no any element then it display
appropriate message on the screen that is queue is empty.
·
Otherwise
increment in front pointer by 1.
·
In this operation there is no any choice from the user because it work on FIFO manner.
·
At the time of executing ,the pop operation if
there is only single element then, The value of front and rear is -1 which
denoted that queue is empty.
·
Following is diagram of pop Operation:
Diagram
·
According to above diagram, we can clearly show
that the value of front is increment by 1 and remove the element in a queue.
Peep Operation:
·
This is used to display an existing element in a
queue before handling this operation 1st check
the condition .
·
If queue has no any element then it display
appropriate message on the screen that is queue is empty.
·
Otherwise it traversal from Front to rear.
·
Following is diagram of Peep operation:
Diagram
·
According to above diagram, this allow
traversal from the front to rear and display data in sequential order.
Circular Queue:
·
Circular
queue is also one of the concept of linear
data structure.
·
And it
provide an attractive way to insert a record in a linear data structure.
·
It also
follow the principle of FIFO manner.
·
It means it
re-allocate a space which is already used by in elements.
·
The main
advantages of circular queue is never display overflow message on the
screen.
·
In a simple queue, Once the queue is full , A
new element are not allow to insert, Even after few elements, are deleted from
front.
·
It not allow
to insert a new element in a replace of a deleted elements.
·
While in a
circular queue, allow to access the data elements space which is already
deleted from the queue.
·
Following is
diagram of Circular queue:
Diagram
·
According to
above diagram, circular queue continuously allow to user input a new element in
their buffer element.
·
Circular
queue have 3 different operation:
Push Operation
Peep Operation
Pop Operation
Push
operation:
·
In this
queue, push operation allow user to input an element into the queue abstract
data type.
·
Before
inserting a new element must check the condition the require space the require
space is available or not.
·
If require
space is not available then it may possible to destroy all the element, from
the queue and start a new queue as a element.
·
Otherwise
rear pointer increment by 1 and allocate new index value to store the element.
·
Following is
diagram of push operation in circular queue.
Diagram
·
According to
above diagram, user can insert an element at rear pointer the rear pointer is
always increment by 1.
·
If space is
available otherwise destroy it.
Pop
operation:
·
This is used
to remove or delete an existing element from the circular queue.
·
Before
executing the pop operation 1st check the condition that circular
queue has element or not.
·
If there is
no any element in a circular queue, then it display an appropriate message that
is “Queue is empty.”
·
If circular
queue is empty then the value of front and rear are -1.
·
If there are
element, in a queue then it remove element, from front it means the value of
front is increment by 1.
·
It also check
one another nested condition that is removed element is a last element in a
queue.
·
If condition
became true then the value of front & rear will be -1.
·
Following is
diagram of pop operation in circular queue.
Diagram
·
According to
above diagram, value of front is increment by 1 which is denoted that the
element is remove from front.
Peep
Operation:
·
Peep
operation is used to display all the element which are store in side the
circular queue.
·
Circular
queue is represent static data structure so, before display all the element
check the condition that element are exist in a queue or not.
·
If there is
no any element in a circular queue, then it display an appropriate message that
is “Queue is empty.”
·
Otherwise it
display element front to rear pointer sequentially as a linear data structure.
·
Circular
queue provide some additional features to display data in circular mode.
·
That may be
possible that the value of front greater than the value of rear pointer.
·
Then data
displaying two separate execution part that is front to size -1 and zero to
rear.
·
Following is
diagram of peep operation in circular queue.
Diagram
·
According to
above diagram, peep operation display their element in 2 separate execution
part that we can clearly show that in a diagram.
Double Ended Queue:
·
De–queue
means Double Ended Queue.
·
It work same
as like a simple queue but it provide a special mechanism to insert or remove
data element to or from the queue.
·
De – queue
provided insertion and deletion at either end it means de-queue element can be
add or remove from the both side.
·
Following is
a diagram of de-queue.
Diagram
·
According to
above diagram, user can be add a new element at the rear or from the front
position.
·
And some
as remove element at the rear or from
the front position. That’s why it’s called the De-queue.
·
Following is
some operation of De-queue :
a.
Insert at
front
b.
Insert at
rear
c.
Remove at
front
d.
Remove at
rear
e.
Display from
front to rear
f.
Display from
rear to front
a.
Insert at front:
·
De-queue
provide two separate value which is initialize with -1 means De-queue is empty.
·
In a De-queue
the inserted at front operation is generally used to insert an element at the
front side.
·
It means
de-queue allow insert element at both side.
·
But before
inserting an element into the de queue at
front side you have to check enough space is available or not.
·
If enough
space is available then it insert an element at front side into the
de-queue.
·
Otherwise it
display an appropriate message on the screen that is there is no enough space.
·
Following is
a diagram of insert at front in
de-queue.
Diagram
·
According to
above diagram, if we have space at front side then, we can simply add element
at front using minus 1.
b.
Insert at rear:
·
As it is push
function in simple queue.
c.
Delete at front:
·
As it is pop function in simple queue.
d.
Delete at rear:
·
This
operation is used to delete an element from the rear side.
·
It allow
insertion as well as delete the element 1 by 1 from the rear side.
·
When some
element delete from the rear side then it traversal from 1st step
then the front and rear in the same position it mean the value of front and
rear on equal position and there is only 1 element in the de-queue.
·
Before delete
an element from the rear 1st check the condition that element are
exist in a queue or not.
·
If there is
no any element then, display appropriate message on the screen that is,
de-queue is empty.
·
Otherwise,
rear pointer decrement by 1.
·
Following is
a diagram of delete at front in
de-queue.
Diagram
·
According to
above diagram, We can clearly show that if element are exist in a de-queue then
it is possible to delete an element from
the rear side using r--.
e. Display
front to rear:
·
As it is peep
function in simple queue.
f. Display Rear to front:
·
This
operation is used to display an existing element in a de-queue before handling
this operation 1st check the condition that element are exist in a
queue or not.
·
If there is
no any element then, display appropriate message on the screen that is,
de-queue is empty.
·
Otherwise, it
traversal from rear to front.
·
Following is
a diagram of display rear to front in
de-queue.
Diagram
According to above diagram, this operation allow
traversal from display rear to front and display data in reverse order.
Priority of the Queue
·
In computer science,
a priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each
element has a "priority" associated with it. In a priority queue, an
element with high priority is served before an element with low priority. If
two elements have the same priority, they are served according to their order
in the queue.
·
A Queue is a data
type for storing a collection of priority wise element in which it is possible
to insert or remove at any position in a queue.
·
It is Depend on
it’s priority it means order of the priority that the element can access it’s
information and also provide a remove operation on any time in a queue.
·
In short we can
say that in a priority of the queue every element of a queue has some priority
and because based on this priority it is known as priority of the queue.
A priority queue must at least support the following
operations:
·
pull_highest_priority_element:
remove the element from the queue that has the highest priority.
Question: Applications of Queue
Queue, as the name suggests is used whenever we need to manage any
group of objects in an order in which the first one coming in, also gets out
first while the others wait for their turn, like in the following scenarios:
1. Serving requests on a single shared resource, like a printer, CPU
task scheduling etc.
2. In real life scenario, Call Center phone systems uses Queues to
hold people calling them in an order, until a service representative is free.
Handling of interrupts in real-time systems. The interrupts are handled
in the same order as they arrive i.e First come first served.
Please share and Comment it... Thank You
:: Best Of Luck ::
