CSE1303 Section An Information Structures and Calculations Address A4 - PowerPoint PPT Presentation

cse1303 part a data structures and algorithms lecture a4 basic data structures continued queues n.
Skip this Video
Loading SlideShow in 5 Seconds..
CSE1303 Section An Information Structures and Calculations Address A4 PowerPoint Presentation
CSE1303 Section An Information Structures and Calculations Address A4

play fullscreen
1 / 23
Download
Download Presentation

CSE1303 Section An Information Structures and Calculations Address A4

Presentation Transcript

  1. CSE1303 Part AData Structures and AlgorithmsLecture A4 – Basic Data Structures – Continued (Queues)

  2. Basic Data Structures • Stacks • Queues • Lists

  3. Overview • What is a Queue? • Queue Operations. • Applications. • Linear Implementation. • Circular Implementation.

  4. Before Front Rear After Front Rear Append

  5. Before Front Rear After This comes off the queue Rear Front Serve

  6. Operations • Initialize the queue. • Append an item to the rear of the queue. • Serve an item from the front of the queue. • Is the queue empty? • Is the queue full? • What size is the queue?

  7. Applications • In operating systems, e.g. printer queues, process queues, etc. • Simulation programs. • Algorithms.

  8. Linear Implementation 0 1 2 3 4 5 6 7 dog fish duck cat finch Rear Front

  9. Append snake 0 1 2 3 4 5 6 7 dog fish duck cat finch snake Front Rear

  10. Append eel 0 1 2 3 4 5 6 7 dog fish duck cat finch snake eel Front Rear

  11. Serve 0 1 2 3 4 5 6 7 fish duck cat finch snake eel Front Rear dog This comes off the queue

  12. Serve 0 1 2 3 4 5 6 7 duck cat finch snake eel Rear Front fish This comes off the queue

  13. Append tiger 0 1 2 3 4 5 6 7 duck cat finch snake eel tiger Front Rear

  14. ROOM HERE NO ROOM HERE Append ape 0 1 2 3 4 5 6 7 duck cat finch snake eel tiger Front Rear

  15. Circular Implementation 0 7 6 1 5 2 4 3

  16. Circular Implementation Append ape 0 1 2 3 4 5 6 7 ape duck cat finch snake eel tiger Rear Front

  17. Queue: #define MAXQUEUE 20 struct QueueRec { int count; int front; int rear; float entry[MAXQUEUE]; }; typedef struct QueueRec Queue; count: front: rear: entry: . . .

  18. #ifndef QUEUEH #define QUEUEH #include <stdbool.h> #define MAXQUEUE 20 struct QueueRec { int count; int front; int rear; float entry[MAXQUEUE]; }; typedef struct QueueRec Queue; void intializeQueue(Queue* queuePtr); bool queueEmpty(const Queue* queuePtr); bool queueFull(const Queue* queuePtr); void append(Queue* queuePtr, float item); float serve(Queue* queuePtr); #endif

  19. #include <stdio.h> #include <stdlib.h> #include “queue.h” void initializeQueue(Queue* queuePtr) { queuePtr -> count = 0; queuePtr -> front = 0; queuePtr -> rear = MAXQUEUE-1; } Queue: 0 count: 0 front: queuePtr: addr ofQueue 19 rear: entry: . . . 19

  20. bool queueEmpty(const Queue* queuePtr) { if (queuePtr->count <= 0) { return true; } else { return false; } } bool queueFull(Queue* queuePtr) { if (queuePtr->count >= MAXQUEUE) { return true; } else { return false; } } 20

  21. void append(Queue* queuePtr, float item) { if (queueFull(queuePtr)) { fprintf(stderr, “Queue is full\n”); exit(1); } else { queuePtr->rear++; if (queuePtr->rear == MAXQUEUE) { queuePtr->rear = 0; } queuePtr->entry[queuePtr->rear] = item; queuePtr->count++; } } 21

  22. float serve(Queue* queuePtr) { float item; if (queueEmpty(queuePtr)) { fprintf(stderr, “Queue is empty\n”); exit(1); } else { item = queuePtr->entry[queuePtr->front]; queuePtr->front++; if (queuePtr->front == MAXQUEUE) { queuePtr->front = 0; } queuePtr->count--; } return item; } 22

  23. Revision Revision: Reading • Queue • Main Operations • Implementation. • Kruse: Chapter 4.1 to 4.2 • Deitel & Deitel: Chapter 12.6 • Standish: Chapter 7 • Langsam: Chapter 4.1 Preparation • Next lecture:Lists • Kruse 4.5, 4.6, 4.8 • Deitel & Deitel (2e) 12.1, 12.2, 12.4