Stack and queue power point presentation data structure and algorithms Stack-Queue-LL.pptx

Stack and queue

1. Introduction and Overview of Data Structure This part will introduce the concept of data structure. But before the discussion of data structure we will have a look of some elementary concepts and terminology related to data structure. Data “A well-known fact that has some implicit meaning and that can be recorded is known as data”. In simplest words we can say that data means value or set of values. So raw facts and figures about any thing may be termed as data. Some of the examples are Robert 34 New Jersey 07-04-1980 CEO In the above example we are having some figures but these figures are not able to represent the clear message. Means we don’t know what is the meaning of this data.

2. Information Processed data is known as information. Means after processing of data we can get clear message inherited into the data or meaningful data is called information In other words “data +associated attributes” may be termed as information The above example can be represented in such a way Employee Name -- Robert Age -- 34 City -- New Jersey Date of Joining -- 07-04-1980 Designation -- CEO This example gives the information that Robert, which is a 34 year old, lives in New Jersey. He is CEO in a company and his date of joining is 07-04-1980 Relation between data and information   DATA Procedure to process the Data Information

3. Data Structure Data structure is the structural representation of logical relationship between elements of data. Or in other words a data structure is a way of organizing data items by considering its relationship to each other.   ALGORITHMS + DATA STRUCTURE = PROGRAM   Data structures are the building blocks of a program. Means the selection of a poor data structure may design an inefficient program. LIBRARY Classification of fundamental Data Structure- Some of the data structures are used frequently almost in all application areas and with the help of which almost all-complex data structure can be constructed. These data structures are known as fundamental or classic data structure. Classification of all fundamental data structures is as follows:

4. Classification of Data Structure Fundamental data Structure Linear Data Structure Non-Linear Data Structure Arrays Stacks Queues Linked List Trees Graphs Tables Sets

5. Data Structure Operations Traversing -Accessing each record exactly once. Searching -Finding the location of the record with the given key value. Inserting -Adding a new record to the structure. Deleting -Removing a record from the structure Sorting -Arranging the records in some logical order. Merging -Combining the records

6. Arrays An array is a finite, ordered collection of homogeneous data elements. Array is finite because it contains only limited number of elements, and ordered, as all the elements are stored one by one in contiguous locations of computer memory in a linear ordered manner. All the elements of an array are of the same data type that is why termed as collection of homogeneous elements. Array may be one-dimensional or multidimensional. In multidimensional array elements are arrange in the form of row and column. Elements of an array can be accessed through index (say i ) or subscript. If we want to store n elements in an array A then the elements will store from A[0] to A[n-1]. Any particular element can be represented as A [ i ]. The diagrammatic representation would be as follows- A[0] A[1] A[2] ………… A[n-1]

7. Stacks

8. “A stack is an ordered collection of homogeneous data element where the insertion and deletion operations take place at one end only called TOP of the stack” In case of arrays and linked list, insertion and deletion operations can take place at any position. But in case of stack insertion and deletion operations are known as PUSH and POP and restricted to one end only, known as TOP of the stack. An element in a stack is termed as ITEM. The maximum number of elements that a stack can accommodate is termed its size. The last inserted element in stack, will be first removed from the stack. That is why the stack is known as LAST IN FIRST OUT (LIFO). Insert Elements(PUSH) Delete last inserted element(POP) Top of the Stack Bottom of the Stack ITEM 1 ITEM 2 ITEM 3 ITEM 4 ITEM 5

9. Operations on Stack PUSH The process of adding a new element to the top of stack is called PUSH. Pushing an element in the stack involve adding new element In case the array is full and no new element can be accommodated, it is called the STACK OVERFLOW.   POP The process of deleting an element from the top of stack is called POP. After every pop operation the stack is decremented by one. If there is no element in the stack and POP is performed then this will result into STACK UNDERFLOW. Implementation of Stack Stack can be implemented in two ways Stack implementation using arrays (static implementation) Stack implementation using pointers (dynamic implementation)

10. ALGORITHM TOP-top of stack. Initial value of TOP is 0 ITEM- element to be inserted MAXSTK- maximum size of stack PUSH ( STACK ,TOP ,ITEM ,MAXSTK ) This procedure pushes an item onto stack. If TOP = MAXSTK , then : Print: OVERFLOW, and Return. Set TOP = TOP+1 Set STACK [TOP] = ITEM Return.     POP ( STACK ,TOP ,ITEM ) If TOP = 0 , then : Print : Underflow, and Return. Set ITEM = STACK [TOP] Set TOP = TOP- 1 Return.

11. Applications of Stacks Page-visited history in a Web browser Undo sequence in a text editor Backtracking Saving local variables when one function calls another, and this one calls another, and so on. Recursion Infix to postfix conversion Quick sort Mobile

12. Queues A Queue is an ordered collection of items from which items may be deleted at one end (called the front of the queue) and into which items may be inserted at the other end (the rear of the queue). The first element inserted into the queue is the first element to be removed. For this reason a queue is sometimes called a fifo (first-in first-out) list as opposed to the stack, which is a lifo (last-in first-out).

13. QUEUE OPERATIONS Initialize the queue Insert to the rear of the queue Remove (Delete) from the front of the queue Is the Queue Empty Is the Queue Full What is the size of the Queue Implementation of Queue Queue can be implemented in two ways Queue implementation using arrays (static implementation) Queue implementation using pointers (dynamic implementation)

14. Queue Implementation using Circular Array QINSERT(QUEUE,N,FRONT,REAR,ITEM) 1. [Queue already filled?] If FRONT=1 and REAR=N or if FRONT=REAR+1 then Write OVERFLOW and exit. 2. If FRONT=NULL then[Queue is initially empty] Set FRONT=1 and REAR=1 Else if REAR=N then set REAR=1 Else set REAR=REAR+1 3. Set QUEUE[REAR]=ITEM 4 . Exit QDELETE(QUEUE,N,FRONT,REAR,ITEM) [Queue already empty] If FRONT=NULL then Write UNDERFLOW and exit. Set ITEM=QUEUE[FRONT] If FRONT=REAR then [queue has only one element to start] Set FRONT=REAR=NULL Else if FRONT=N then Set FRONT=1 else Set FRONT=FRONT+1 4. Exit

15. Types and Applications of Queue TYPES Deque or Dequeue (Input Restricted/Output Restricted) Priority Queue Applications Waiting lines Access to shared resources (e.g., printer) printer queue, keystroke queue, etc. Searching(DFS & BFS) Used extensively in operating systems Multiprogramming Queues of processes, I/O requests, and much more

16. Linked List Array is a data structure where elements are stored in consecutive memory locations. We have to specify the size of array before its usage. Once memory is allocated it cannot be extended any more. That is why array is known as static data structure. In contrast to this linked list is called dynamic data structure where amount of memory required can be varied during its use. A linked list consists of nodes. A node consists of two fields; one is data (actual content) and link (which point to the next data). LINK Link to the Next Node Node : An element in a linked list DATA

17. Definition A linked list or one way list is an ordered collection of finite data elements called nodes where the linear order is maintained by means of links or pointers. DATA LINK DATA LINK DATA LINK Linked List representation START 22 40 50 NULL

18. TO CREATE LINK LIST In C, a linked list is created using structures, pointers and dynamic memory allocation function .We consider head as an external pointer. This helps in creating and accessing other nodes in the linked list. Consider the following structure definition and head creation: Struct node { int DATA; struct node * ptr ; };   typedef struct node NODE ; NODE *start; Start=(NODE *) malloc ( sizeof (NODE)); When the Statement Start=(NODE *) malloc ( sizeof (NODE)); Is executed , a block of memory sufficient to store the NODE is allocated and assigns head as the starting address of the NODE. This activity can be pictorially shown as follows:- start DATA ptr

19. Types of Linked List Header Linked List -Grounded Header Linked List -Circular Header Linked List Two way Linked List Two way Circular Header Linked List Applications of linked List Dynamic Memory Allocation Polynomials representations and various operations over polynomials Non Contiguous Memory Allocation Representing Sparse Matrix Representation of PCB in Operating system

20. Inserting After a Given Node Suppose we are given the value of LOC where either LOC is the location of a node A in a linked list or LOC=NULL, so that ITEM is the first node.

21. Deletion from a Linked List

22. Deleting the node Following a Given Node Let LIST be a linked list in memory. Suppose we are given the location LOC of a node N in LIST. Furthermore we are given the location LOCP of the node preceding N or. when N is the first node, we are given LOCP=NULL.

23. HEADER LINKED LISTS A header linked list is a linked list which always contains a special node, called the header node at the beginning of the list. The following are two kinds of widely used header lists: A gronded header list is a header list where the last node contains the null pointer. (The term grounded comes from the fact that many texts use the electrical ground symbol to indicate the null pointer.) A circular header list is a header list where the last node points back to the header node

24. TWO WAY LISTS (OR DOUBLY LINKED LIST)

25. TWO WAY CIRCULAR HEADER LISTS

26. Linked Implementation of Stack

27. Linked Implementation of Queue LINKQ_INSERT(INFO,FRONT,REAR,AVAIL,ITEM) 1. If AVAIL = NULL then write OVERFLOW and Exit. 2. Set NEW=AVAIL and AVAIL=LINK[AVAIL] 3.Set INFO[NEW]=ITEM and LINK[NEW]=NULL 4.If FRONT =NULL then FRONT=REAR=NEW Else Set LINK[REAR]=NEW and REAR=NEW 5. EXIT

28. LINKQ_DELETE(INFO,LINK,FRONT,REAR,AVAIL,ITEM) 1. If FRONT=NULL the write UNDERFLOW and Exit. 2.Set TEMP=FRONT 3.ITEM=INFO[TEMP] 4.FRONT=LINK[TEMP] 5.LINK[TEMP]=AVAIL and AVAIL=TEMP 6. Exit