What is Linear Data Structure

1]. INTRODUCTION

               As you know word stack is used in link of mankind as an arrangement of an objects like stack of tray or stack of folded shift or stack of coins.

2]. DEFINITION

                             

“A data structures in which element are added & removed from only one end , “A last in first out structure.”

“A stack is an ordered collection of items into which new item may be inserted & from which items may be deleted at one end called the top of the stack. “

3]. WHAT IS STACK ?

A stack can be defined as the list in which all insertion & deletion are made at one end. This end is called top. The remove of the existing element & the addition of the new element can tack place only at the top the stack.

The stack is an ordered group of items because the element occur in a sequence according to how long they have been in the stack. The item that have been in the stack , the longest are at the bottom and most recent are the top.

                              STACK

Caption : Containing stack term.

In stack we remove an item in this situation the top of the stack moves downward to correspond to new highest element.

 The bottom element of the stack is called bottom of the stack & top element is called top of the stack . In above figure the bottom element is 1 and top of the stack is 5.

Element are added and removed only from the top of the stack. The last elements are added and the first to be removed in the method is use (LIFO).

A stack is also characterized by a type attributes, that means a stack can  accept element of its own type. For e.g. an integer stack can be maintained to push & pop only integers. It is also feasible to have a stack  for composite data type. In  computing context, all elements of a stack are of the same data type. Through this need not be seen in real life stack.

4]. FEATURES  OF THE STACK

                                            

                              Features of stack are as follow:

v  SATCK IS A SPECIAL TYPE OF LIST.

v  ALL ELEMENTS ARE OF SAME TYPE.

v  LOGICALY ONLY ONE ELEMENT (THE TOP) IS POSSIBLE.

v  ALL OPERATION CAN BE DONE ONLY ON THE TOP ELEMENT.

The stack can be implemented in two ways .

1]. Using linked list.

2]. Using array.

5].OPERATION AND ALGORITHMS PERFORMED ON STACK:-

                              As per class note

6]. APPLICATION OF STACK.:-

There are several applications where stack can be put to use.

1. Recursion

2. Stack Machine

3. Check for valid parenthesis

4. Conversion from one notation to another.

5. Evaluation of any notation.

1.Recursion: -

Recursion is the name given to the technique of defining a set on a process in term of itself.          OR

When a called function in turn calls another function a process of chaining occurs recursion a special case of this process when a function calls itself.

There are two important conditions that must be satisfied by any recursive procedure.

1) Each time a procedure calls itself (either directly or indirectly) it must be “nearer in                  some sense, to a solution”. In the case of the factorial function, each time that the function calls itself, it argument is decrement by one, so the argument of the function is getting smaller.

2) There must be a decision criterion for stopping the process or computation. In the case of the factorial function, the value of n must be zero.

2. Stack Machine: -

One of the main problems with using machines which have a very limited no of registers is how to handle the store of intermediate results to solve this problem such machines are known as stack machine.

Many of the machines, which are appearing on the market, include in their architecture hardware stacks or stack mechanisms. The such machines are the PDP-11 & the Burroughs 5000. Both machines are particularly well suited for the stacking of local variables & parameters that arise in procedure calls of block nested languages.

3, Polish notation: -

We are already familiar with arithmetic expressions in infix notation. In this notation a binary operator is placed between its operands.

For example: -

A + B – C

A – ( C – D ) / ( B * D )

A + B * D – E / F

The operations are normally carried out from left to right. We also have procedure rules for evaluating expressions. A*B+C+D*E would be to multiply B & A, then adding it to C, saving that result temporarily say in RESULT, Then multiplying D & E, and add it to the RESULT. Therefore we have to followed the sequence as given below,

AB * C + DE * +

This notation is called the postfix notation or reverse-polish notation.

We can convert infix notation to postfix notation by using stack data structure.

Operator priority list

ü  Highest: ‘^’ OR ‘$’ means exponent

ü  Lower: ‘*’ means multiplication and ‘\’ means Division

ü  Lowest: ‘+’ means addition and ‘-‘means subtraction.

Rules for conversion from infix to postfix

ü  Take a stack and an answer.

ü  If stack is empty then directly push the operator in it. And if operand is scanned put it into the answer.

ü  If the stack already contains the operator then check the incoming operator and the top of the stack operator.

ü  If the priority of the incoming operator is high than the priority of the operator of top of the stack then push it into the stack rather than pushing it into the answer. Ex. Top=’+’ and incoming =’*’.

ü  If the priority of the incoming operator is lower than the priority of the operator of top of the stack then first POP all the operators with higher priority from Top of stack than the incoming operator. For Ex. Top=’*’ and incoming =’-‘or ‘+’.

ü  If the priority of the incoming operator is equal to the priority of the Top of stack operator, then first POP the operator from Top of stack and then PUSH the incoming operator into the stack. For Ex. Top=’-‘and incoming =’+’.

ü  If we have PUSHed the opening bracket of the equation and we found the same type of closing bracket then POP all the operators between two brackets and add the operators into the answer string.

Rules for conversion from infix to prefix

ü  First of all convert the given equation into reverse order.

ü  Solve the equation from left to right and put the answer from right to left.

ü  If opening bracket will found after related closing bracket then put all the operators in between then into answers.

ü  If the priority of incoming operator is high then the top of the stack operator then directly put incoming operator into the stack.

ü  If the priority of the incoming operator is low then the top of the stack operator then first pop the top of the stack operator into answer and then after compare the incoming and the new one of the Top of the stack operator and if the priority of operator is still lower than the Top of stack POP the second one into answer from Top of stack. (Do until the incoming operator becomes higher than Top of stack or equal to Top of stack.)

ü  If the priority of the incoming operator is equal to the priority of Top of stack element then PUSH the incoming operator into the stack (reverse then postfix, main difference)

Introduction:

• Queue is data structure in which element may be deleted from one end called “FRONT” and element may be inserted from one end called “REAR”.
• The information such as list in process in the same order as it was received that in the “FIRST IN FIRST OUT” bases.

1

2

3

4

5

6

                   FRONT                                                           REAR

• In the queue shown above element one is at the FRONT & element six is at the rear of the queue.
• When you add new element as last position increment REAR and when delete element from first position increment FRONT.
• Ex:The conman application for queue is “Compute Application.”, is for the scheduling of jobs. In a time sharing sys programs from a queue waiting to be executed. When a program has to be executed it is put at the end of queue. The program at the FRONT of the queue is the first one to get executed.

Types of Queue:-

·        single Queue(linear Queue)

·        circular Queue

·        priority Queue

·        Double Ended Queue(Dqueue)

Operation Performed on queue:-

·        Insertion(push)

·        Deletion(pop)

·        Display(Traversing)

·        Searching(peep)

·        Change(update)

Description about circular queue, priority queue, queue based on class note.  Read Algorithms of insertion ,deletion and display for the linear and circular queue from the class note.

Implementation of  Queue:-

It can be implemented with 

·        Array

·        Link list

An algorithm has indicator like REAR pointer which add new element and FRONT which delete element, SIZE variable give size of  given queue Q.

v  Write an algorithm insert element in queue

START

Step-1 . [Check overflow condition]

                If REAR>SIZE-1

                 Print(“overflow”)

                 Return

                 End if

Step-2. [Increment rear pointer]

               REAR=REAR+1

Step-3. [Insert an element]

               Q[REAR]=value

Step-4. [set the FRONT pointer]

                 If “(FRONT==0)

               FRONT=1

              End if

Step-5. EXIT

v  Write an algorithm to delete element from queue

  START

Step-1. [Check underflow condition]

             If FRONT=0

             PRINT(”Underflow”)

          return

Step-2. [Remove an element]

             Value=Q[FRONT]

Step-3. [Check for empty queue]

             If FRONT=REAR

             FRONT=0

             REAR=0

             Else

              FRONT=FRONT+1

Step-4. Return(value)

EXIT

v  Write an algorithm to display  given queue

START

Step-1. [check for empty queue]

            If((FRONT<0 AND REAR<0)OR(FRONT>REAR))

            Print(“Queue is an empty”)

           Return

                 End if

Step-2.  [display all element ]

              For I=FRONT to I<=REAR

              Print (Q[I])

              End loop

Step-3.  Exit

CIRCULAR QUEUE   

Circular Queue mean no any end of list; after last element of list come first element again this procedure call circular queue.

In a circular queue when REAR=N ;if we insert an element then this  element is  assigned to Q[1].That is instead of increment of REAR ,we reset REAR=1.if FORNT=N and an element of queue is remove ,we reset FRONT to 1.Suppose queue contains only one element that is FRONT =REAR=1 and suppose that element is remove then the FRONT and REAR pointer are now assign NULL to indicate that queue is empty.

v Write an algorithm to insert into circular queue

START

Step-1 [Check for overflow]

             If FRONT=1 AND REAR =SIZE

             Print (“Overflow”)

             Return

             End if

Step-2 [Insert element in the queue]

             Else If FRONT=0

             FRONT=1

             REAR=1

             Q [REAR] = VALUE

Step-3 [Check if the rear at the end of the queue]

             Else If REAR=SIZE

              REAR=1

              Q [REAR] = VALUE

Step-4 [insert the element]

             Else

               REAR=REAR+1

             Q [REAR] = VALUE

Step-5 EXIT

v Write an algorithm to delete element from circular queue

Step-1 [check for underflow]

             If FRONT=0

             Print (“UnderFlow”)

              Return

              End if

Step-2 [Remove the element]

               Value=Q [REAR]

    Step-3 [Check whether the queue is empty or not]

                 If FRONT =REAR

                   FRONT=0

                   REAR=0

  Step-4 [Check the pointer position]

                   Else If FRONT=SIZE

                    FRONT = 1

                   ELSE

                   FRONT=FRONT+1

Step-5 [return the removed element]

             Return (value)

EXIT

v  Write an algorithm to display element of circular queue

START          

Step-1 [check for empty queue]

            If FRONT<0

               Print (“queue is empty”)

               Return

            End if

Step-2 [rear is greater position than front]

            If REAR>=FRONT

           For I=FRONT to I<=REAR

            Print (Q [I])

            End loop

Step-3 [when front is greater poison]

            For I=FRONT to I<SIZE

              Print (Q [I])

               End loop

             For I = 0 to I<=REAR

             Print (Q [I])

             End loop

Step-4 EXIT

Priority queue

A Queue in which it is possible to insert an element or remove an element at any position depending on some priority is called priority queue. A priority queue of jobs of waiting to use printer on LAN System. priority of 1 2 3 4 have been attached to the jobs of supervisior ,teacher student and user respectively .therefore if a job is initiated  with priority p,it is inserted immediately at the end of the  queue of other jobs with priority p.

L

v Write an algorithm to insert element ITEM with priority number N in Priority queue

 START

Step:1 Traverse the list until finding a element X whose priority number   exceeds N .

Step:2  Insert ITEM in to front of element X

      Step:3 If no such element is found ,insert ITEM as the last element of the list.

           EXIT

v Write an algorithm to delete element from priority queue

Step:1 Set ITEM<-INFO[FRONT]

Step: 2 Delete First element from list

Step: 3 free ITEM

EXIT

DOUBLE ENDED QUEUE

It is linear list in which insertion and deletion are possible at either end. Double ended queue is also known as dqueue.

We known that in a stack insertion and deletion are possible only at one end (LIFO) while in a queue insertion at one end and deletion at other end. That is operation in queue is performed in FIFO basis. Thus, we can say that dqueue is more superior representation of linear list as compared to stack and simple queue. There are two from of dqueue

1.)    Input restricted dqueue.  [Insertion at one end]

2.)    Output restricted dqueue. [deletion at one end]

Application of Queue:-

In a computer network messages from one to another computer are generally created asynchronously. These messages therefore need to be buffered until the receiving computer is ready for it these communication buffers make extensive use of Queues by storing of Queues by storing these message in a queue. Also the messages need to be sent to receiving computer in the some order in which they are created. I.e. FIFO

SIMULATION:-

·        It is one of the most useful application of queue, priority queue & link list.

·        A simulation program attempts to model a real world situation. In order to learn something about it. As it would be too expensive or dangerous to experiment with the real system. Each object & action in real situation as it’s counter part in the program.

·        If program successfully mirrors real world situation, the results of the program should mirror.

·        The result of actions been simulated that it is possible to understand both occurs in the rear world situation without actually observing its occurrence.

·        Ex: They are physical simulators such as flights simulators used to train and air pilot.

·        In order to simulate a system a model of the system must be produce & to determine the structure of a model for some situation, the entities, attributes & activities of the system should be determine.

·        An entity represents the components of the system & is the object that is persons, places or things of interest in the simulations.

·        Attributes denote the characteristics of these entities. The state of the system at any given time is specified by the attributes of the system entities and the related among the entities at that time.

·        An activity is a process which causes a change of system state & event is the occurrences of an   activity at a particular instant of time. If we consider a bank system an example entities should be customer. The attribute for the customer could be the balance in the account & there credit rating where as the activity might include deposit or withdraw & even would occur when a customer enters or leave the queue.