logging in or signing up e computer notes - Data Structures - 9 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 9 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.09 Data Structures http://ecomputernotes.comMemory Organization: Memory Organization Code Static data Stack Heap Process 1 (browser) Process 3 (word) Process 4 (excel) Windows OS Process 2 (dev-c++) http://ecomputernotes.comStack Layout during a call: Stack Layout during a call Here is stack layout when function F calls function G: Parameters(F) Local variables(F) Return address(F) Parameters(G) Parameters(F) Local variables(F) Return address(F) Parameters(F) Local variables(F) Return address(F) Parameters(G) Local variables(G) Return address(G) During execution of G After call At point of call sp sp sp http://ecomputernotes.comQueues: Queues A stack is LIFO (Last-In First Out) structure. In contrast, a queue is a FIFO (First-In First-Out ) structure. A queue is a linear structure for which items can be only inserted at one end and removed at another end. http://ecomputernotes.comQueue Operations: Queue Operations Enqueue(X) – place X at the rear of the queue. Dequeue() -- remove the front element and return it. Front() -- return front element without removing it. IsEmpty() -- return TRUE if queue is empty, FALSE otherwise http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: Recall Insert works in constant time for either end of a linked list. Remove works in constant time only. Seems best that head of the linked list be the front of the queue so that all removes will be from the front. Inserts will be at the end of the list. http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: front 2 5 7 1 1 7 5 2 front rear rear http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: front 2 5 7 1 1 7 5 2 front rear rear front 2 5 7 1 7 5 2 front rear rear dequeue() http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: front 2 5 7 1 1 7 5 2 front rear rear front 2 5 7 9 7 5 2 front rear rear enqueue(9) 9 http://ecomputernotes.comImplementing Queue: Implementing Queue int dequeue() { int x = front->get(); Node* p = front; front = front->getNext(); delete p; return x; } void enqueue(int x) { Node* newNode = new Node(); newNode->set(x); newNode->setNext(NULL); rear->setNext(newNode); rear = newNode; } http://ecomputernotes.comImplementing Queue: Implementing Queue int front() { return front->get(); } int isEmpty() { return ( front == NULL ); } http://ecomputernotes.comQueue using Array: Queue using Array If we use an array to hold queue elements, both insertions and removal at the front (start) of the array are expensive. This is because we may have to shift up to “n” elements. For the stack, we needed only one end; for queue we need both. To get around this, we will not shift upon removal of an element. http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 1 rear 6 5 7 0 0 1 3 2 4 front 1 7 5 2 3 rear http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 1 rear 6 5 7 0 0 1 3 2 4 front 1 7 5 2 4 rear enqueue(6) 6 6 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 1 rear 6 5 7 0 0 1 3 2 4 front 1 7 5 2 5 rear enqueue(8) 6 6 8 8 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 rear 6 5 7 1 0 1 3 2 4 front 7 5 2 5 rear dequeue() 6 6 8 8 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 rear 6 5 7 2 0 1 3 2 4 front 5 2 5 rear dequeue() 6 6 8 8 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 rear 6 5 7 2 0 1 3 2 4 front 5 2 7 rear enqueue(9) enqueue(12) 6 6 8 8 9 9 12 12 enqueue(21) ?? http://ecomputernotes.comQueue using Array: Queue using Array We have inserts and removal running in constant time but we created a new problem. Cannot insert new elements even though there are two places available at the start of the array. Solution: allow the queue to “wrap around”. http://ecomputernotes.comQueue using Array: Queue using Array Basic idea is to picture the array as a circular array . front 2 5 rear 2 front 7 rear 6 8 9 12 6 5 7 0 1 3 2 4 5 2 6 8 9 12 http://ecomputernotes.comQueue using Array: Queue using Array void enqueue(int x) { rear = (rear+1)%size; array[rear] = x; noElements = noElements+1; } front 2 5 rear 2 front 0 rear 6 8 9 12 6 5 7 0 1 3 2 4 5 2 6 8 9 12 enqueue(21) 21 21 8 size 7 noElements http://ecomputernotes.comQueue using Array: Queue using Array int isFull() { return noElements == size; } int isEmpty() { return noElements == 0; } front 2 5 rear 2 front 1 rear 6 8 9 12 6 5 7 0 1 3 2 4 5 2 6 8 9 12 enqueue(7) 21 21 8 size 8 noElements 7 7 http://ecomputernotes.comQueue using Array: Queue using Array int dequeue() { int x = array[front]; front = (front+1)%size; noElements = noElements-1; return x; } front rear 4 front 1 rear 6 8 9 12 6 5 7 0 1 3 2 4 6 8 9 12 dequeue() 21 21 8 size 6 noElements 7 7 http://ecomputernotes.comUse of Queues: Use of Queues Out of the numerous uses of the queues, one of the most useful is simulation . A simulation program attempts to model a real-world phenomenon. Many popular video games are simulations, e.g., SimCity, FlightSimulator Each object and action in the simulation has a counterpart in real world. http://ecomputernotes.comUses of Queues: Uses of Queues If the simulation is accurate, the result of the program should mirror the results of the real-world event. Thus it is possible to understand what occurs in the real-world without actually observing its occurrence. Let us look at an example. Suppose there is a bank with four tellers. http://ecomputernotes.comSimulation of a Bank: Simulation of a Bank A customer enters the bank at a specific time (t 1 ) desiring to conduct a transaction. Any one of the four tellers can attend to the customer. The transaction (withdraw, deposit) will take a certain period of time (t 2 ). If a teller is free, the teller can process the customer’s transaction immediately and the customer leaves the bank at t 1 +t 2 . http://ecomputernotes.com You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
e computer notes - Data Structures - 9 ecomputernotes Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 9 Category: Education License: All Rights Reserved Like it (0) Dislike it (0) Added: December 28, 2011 This Presentation is Public Favorites: 0 Presentation Description Computer Notes on all computer subject that's related to all university and all college.it help you prepare better for the school and college exams ecomputernotes present to you the revision notes on Computer subjects. Comments Posting comment... Premium member Presentation Transcript PowerPoint Presentation: Class No.09 Data Structures http://ecomputernotes.comMemory Organization: Memory Organization Code Static data Stack Heap Process 1 (browser) Process 3 (word) Process 4 (excel) Windows OS Process 2 (dev-c++) http://ecomputernotes.comStack Layout during a call: Stack Layout during a call Here is stack layout when function F calls function G: Parameters(F) Local variables(F) Return address(F) Parameters(G) Parameters(F) Local variables(F) Return address(F) Parameters(F) Local variables(F) Return address(F) Parameters(G) Local variables(G) Return address(G) During execution of G After call At point of call sp sp sp http://ecomputernotes.comQueues: Queues A stack is LIFO (Last-In First Out) structure. In contrast, a queue is a FIFO (First-In First-Out ) structure. A queue is a linear structure for which items can be only inserted at one end and removed at another end. http://ecomputernotes.comQueue Operations: Queue Operations Enqueue(X) – place X at the rear of the queue. Dequeue() -- remove the front element and return it. Front() -- return front element without removing it. IsEmpty() -- return TRUE if queue is empty, FALSE otherwise http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: Recall Insert works in constant time for either end of a linked list. Remove works in constant time only. Seems best that head of the linked list be the front of the queue so that all removes will be from the front. Inserts will be at the end of the list. http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: front 2 5 7 1 1 7 5 2 front rear rear http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: front 2 5 7 1 1 7 5 2 front rear rear front 2 5 7 1 7 5 2 front rear rear dequeue() http://ecomputernotes.comImplementing Queue: Implementing Queue Using linked List: front 2 5 7 1 1 7 5 2 front rear rear front 2 5 7 9 7 5 2 front rear rear enqueue(9) 9 http://ecomputernotes.comImplementing Queue: Implementing Queue int dequeue() { int x = front->get(); Node* p = front; front = front->getNext(); delete p; return x; } void enqueue(int x) { Node* newNode = new Node(); newNode->set(x); newNode->setNext(NULL); rear->setNext(newNode); rear = newNode; } http://ecomputernotes.comImplementing Queue: Implementing Queue int front() { return front->get(); } int isEmpty() { return ( front == NULL ); } http://ecomputernotes.comQueue using Array: Queue using Array If we use an array to hold queue elements, both insertions and removal at the front (start) of the array are expensive. This is because we may have to shift up to “n” elements. For the stack, we needed only one end; for queue we need both. To get around this, we will not shift upon removal of an element. http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 1 rear 6 5 7 0 0 1 3 2 4 front 1 7 5 2 3 rear http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 1 rear 6 5 7 0 0 1 3 2 4 front 1 7 5 2 4 rear enqueue(6) 6 6 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 1 rear 6 5 7 0 0 1 3 2 4 front 1 7 5 2 5 rear enqueue(8) 6 6 8 8 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 7 rear 6 5 7 1 0 1 3 2 4 front 7 5 2 5 rear dequeue() 6 6 8 8 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 rear 6 5 7 2 0 1 3 2 4 front 5 2 5 rear dequeue() 6 6 8 8 http://ecomputernotes.comQueue using Array: Queue using Array front 2 5 rear 6 5 7 2 0 1 3 2 4 front 5 2 7 rear enqueue(9) enqueue(12) 6 6 8 8 9 9 12 12 enqueue(21) ?? http://ecomputernotes.comQueue using Array: Queue using Array We have inserts and removal running in constant time but we created a new problem. Cannot insert new elements even though there are two places available at the start of the array. Solution: allow the queue to “wrap around”. http://ecomputernotes.comQueue using Array: Queue using Array Basic idea is to picture the array as a circular array . front 2 5 rear 2 front 7 rear 6 8 9 12 6 5 7 0 1 3 2 4 5 2 6 8 9 12 http://ecomputernotes.comQueue using Array: Queue using Array void enqueue(int x) { rear = (rear+1)%size; array[rear] = x; noElements = noElements+1; } front 2 5 rear 2 front 0 rear 6 8 9 12 6 5 7 0 1 3 2 4 5 2 6 8 9 12 enqueue(21) 21 21 8 size 7 noElements http://ecomputernotes.comQueue using Array: Queue using Array int isFull() { return noElements == size; } int isEmpty() { return noElements == 0; } front 2 5 rear 2 front 1 rear 6 8 9 12 6 5 7 0 1 3 2 4 5 2 6 8 9 12 enqueue(7) 21 21 8 size 8 noElements 7 7 http://ecomputernotes.comQueue using Array: Queue using Array int dequeue() { int x = array[front]; front = (front+1)%size; noElements = noElements-1; return x; } front rear 4 front 1 rear 6 8 9 12 6 5 7 0 1 3 2 4 6 8 9 12 dequeue() 21 21 8 size 6 noElements 7 7 http://ecomputernotes.comUse of Queues: Use of Queues Out of the numerous uses of the queues, one of the most useful is simulation . A simulation program attempts to model a real-world phenomenon. Many popular video games are simulations, e.g., SimCity, FlightSimulator Each object and action in the simulation has a counterpart in real world. http://ecomputernotes.comUses of Queues: Uses of Queues If the simulation is accurate, the result of the program should mirror the results of the real-world event. Thus it is possible to understand what occurs in the real-world without actually observing its occurrence. Let us look at an example. Suppose there is a bank with four tellers. http://ecomputernotes.comSimulation of a Bank: Simulation of a Bank A customer enters the bank at a specific time (t 1 ) desiring to conduct a transaction. Any one of the four tellers can attend to the customer. The transaction (withdraw, deposit) will take a certain period of time (t 2 ). If a teller is free, the teller can process the customer’s transaction immediately and the customer leaves the bank at t 1 +t 2 . http://ecomputernotes.com