Queue Data Structure

Queue Data Structure:

• Queue is a linear data structure
• it works on the principle First In First Out (FIFO).
• The first element insert into the queue is the first element to be delete
• Insertion can be done at rear end using rear pointer and deletions can be done at front end using front pointer
• It looks like open tube.
• The insertion operation is called append/enqueue operation
• The deletion operation is called as serve/dequeue operation.
• Enqueue operation on a full queue causes overflow.
• Dequeue operation on empty queue causes underflow.
• The initial value of the front and rear pointer is always –1
• The pointer front points to the starting end of the queue
• The pointer rear points to the rear end of the queue

For example

The fig 01 illustrates a queue containing three elements a, b and c. the element (a ) is at the front of the queue and c is at the rear of the queue. Fig 02 shows queue after deleting an element. Since elements may be deleted only from the front of the queue, (a) is removed and b is now at the front. Now fig 03 shows queue after inserting elements d and e , they must be inserted at the rear of the queue.

Operations of a queue:

There are two operations applied on queue they are 1 enqueue 2. dequeue. While performing enqueue operation check the queue is Full or not and while performing dequeue operation check the queue is empty or not.

Enqueue:

Insert an element into the queue is called Enqueue operation. Insertion can be done at rear end. At the time of insertion first check the queue is full or not. If the queue is full it generates an error message “queue if Full”.

Dequeue:

Delete an element from the queue is called Dequeue operation. Deletion can be done at front end. At the time of deleting first check the queue is empty or not. If the queue is empty it generates an error message “queue is empty”.

Assumptions:

rear, front are pointers , initial values are -1, -1

max_queue is the size of the queue

Q[ ] is an array

element is the element to be added or deleted

Algorithm for adding an element in to the queue (enqueue):

Step1: start

Step2: if (rear == max_queue - 1) then error “queue is full “go to step 5

Step3: else{ update front as front = front +1

Step4: put the element into the queue at rear as queue [rear] = element }

Step5: stop.

Algorithm for deleting an element from the queue (dequeue):

Step1: start

Step2: if (front == rear) then error “queue is empty” go to step5

Step3: else {update front as front = front +1

Step4: delete an element from front as element = queue [front]}

Step5: stop.

Applications of queue:

· Queues can be used to store the interrupts in the operating system

· It is used by an application program to store the incoming data

· Queue is used to process synchronization in Operating System

· Used for job scheduling

Drawbacks of a queue:

For each and every enqueue operation the queue is to be rearranged other wise even the queue is having an empty space it is not possible to utilize.

Applications of Stack Data Structure

Application of stacks :-

The linear data structure stack can be used in the following situations.

1. It can be used to process function calls.

2. Implementing recursive functions in high level languages

3. Converting and evaluating expressions.

Function calls:

A stack is useful for the compiler/operating system to store local variables used inside a function block, so that they can be discarded once the control comes out of the function block.

Recursive functions:

The stack is very much useful while implementing recursive functions. The return values and addresses of the function will be pushed into the stack and the lastly invoked function will first return the value by popping the stack.

Representation of expressions :-

In general there are 3 kinds of expressions available depending on the placement of the operators & operands.

1) Infix expression :- It is the general notation used for representing expressions.

“In this expression the operator is fixed in between the operands”

Ex: a + bc

2) Post fix expression :- (Reverse polish notation)

“In this expression the operator is placed after the operands”.

Ex : abc+

3) Prefix expression :- (Polish notation)

“In this expression the operators are followed by operands i.e the operators are fixed before the operands”

Ex : +abc

All the infix expression will be converted into post fix notation with the help of stack in any program

The stack will be useful in evaluating the postfix expressions also.

Algorithm for evaluating post fix expression using stacks :-

step :- 1 start

step :- 2 for(each character ch in the postfix expression)

step :- 3 If operand is found push it into the stack

step :- 4 else

step :- 5 If operator is found then pop the stack 2 times

OP2 = pop ( ) OP1 = pop ( )

step :- 6 Perform the specified operation as result = OP1 operator OP2

step :- 7 Push the intermediate result back into the stack

step :- 8 Repeat the above steps until the end of the expression

step :- 9 pop the stack to obtain the final result

step :- 10 stop

Algorithm to convert infix to post fix expression: -

– assumptions

§ Operands are single lowercase letters that represent integer values

§ Stack is a stack data structure

§ Precedence is the function to get the precedence of an operator

Steps

1. for (each character ch in the infix expression) {
2. switch (ch) {

i. case operand: // append operand to end of PE

postfixExp = postfixExp + ch; break

ii. case '(':

a Stack.push(ch) break

iii. case ')':

1. while (top of stack is not '(')

a. postfixExp = postfixExp + (Stack.pop())

2. Stack.pop() // remove the open parenthesis

3. break

iv. case operator:

1. while (!Stack.isEmpty and top of stack is not '(' and precendence(ch) <= precendence(top of aStack))

a. postfixExp = postfixExp + (Stack.pop())

2. Stack.push(ch) // save new operator

3. break

3. }
4. }
5. // append to postfixExp the operators remaining in the stack
6. while (!Stack.isEmpty())
7. postfixExp = postfixExp + (Stack.pop())

Fox example the following figure shows how to convert the infix expression a - (b + c * d)/e to postfix form

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

Data Structure Definitions

Data structure Definitions : -

In computer science, a data structure is a way of storing data in a computer so that it can be used efficiently. Often a carefully chosen data structure will allow the most efficient algorithm to be used. The choice of the data structure often begins from the choice of an abstract data type. A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible. Data structures are implemented by a programming language as data types and the references and operations they provide.

Definition:

“Collection of data elements organized in a specified manner and a set of functions to store, retrieve and manipulate the individual data elements.”

Or

“The way of representing data internally in the memory is called data structure” Or “A data structure is a way of store data in a computer so that it can be used efficiently”

Or

A data structure is a specialized format for organizing and storing data. General data structure types include the array, the file, the record, the table, the tree, and so on. Any data structure is designed to organize data to suit a specific purpose so that it can be accessed and worked with in appropriate ways. In computer programming, a data structure may be selected or designed to store data for the purpose of working on it with various algorithms.