MidtermPresentation_Essentials_QueueDataStructure.pdf

CS 211 – Data Structures Topics under Data Structures Array Linear Circular LinkedList SinglyLinked DoublyLinked Stack Queue PriorityQueue Tree Binary Tree Binary Search Tree Balanced Binary Search Tree Graph HashMap* Objective ( This Lesson )...

CS 211 – Data Structures Topics under Data Structures Array Linear Circular LinkedList SinglyLinked DoublyLinked Stack Queue PriorityQueue Tree Binary Tree Binary Search Tree Balanced Binary Search Tree Graph HashMap* Objective ( This Lesson ) Explain Fundamental concepts associated with the Queue Data Structure Create Java Codes (Code Segments) for the Queue Data Structure Trace Java programs that apply the Queue Data Structure (c/o laboratory exercise) Create a Java application that uses the Queue Data Structure(c/o laboratory project)  Data Structures Reminders: Checklist of Expectations 1. Completed the exercise on the applications of the Stack Data Structure ( Palindrome Checking, Mouse Maze problem) 2. Working on the exercise on the application of the Queue Data Structure ( Simulation of a Single-Server Service System) 3. Working with Groupmates for the midterm projects a. Infix-Postfix Conversion program, evaluation of a Postfix expression b. Program for the Huffman Code problem c. Lecture presentation videos for data structures (Stack, Queue, …) Queue Data Structure FIFO Data Structure LILO Data Structure The Queue Data Structure Queue - linearly ordered set of elements that is processed by following the first-in, first-out (FIFO) discipline The QUEUE Data Structure Queue - linearly ordered set of elements that is processed by following the first-in, first-out (FIFO) discipline First-in,first-out (FIFO) is equivalent to Last- in,last-out(LILO). Linked Representation of the QUEUE rear/tail front/head Popular/Conventional terms associated with the Queue Data Structure enqueue dequeue front rear head tail Conventional terms used with the Queue Data Structure front → reference to the first(oldest) element of the queue rear → reference to the last (newest) element of the queue head → alternative term for the front tail → alternative term for the rear enqueue → operation for adding an element to the Queue(at the tail/rear) dequeue → operation for removing an element from the Queues ( from the head/front) Exercise Assume that you will design a Queue Data Structure that will be implemented using the Java programming language. Assume further that the Queue data structure uses a Linked Representation rather than an Array. It is expected that you have reference class for a node and an QueueInterface that lists the fundamental operations that may be performed on the Queue. Furthermore, your design should be such that the Queue can store elements of generic type. REQUIRED: 1. Show a class diagram for the node of the Queue 2. Show your code for the QueueInterface (i.e. provide the statements in the block of the following interface) public interface QueueInterface { // what may be here? } Template for the node of a Linked Representation of the Queue public class QueueNode { T info; QueueNode link; public QueueNode(T info, QueueNode link) { this.info = info; this.link = link; } } Linked Representation of the QUEUE Queue is empty if front = rear = null Overflow will happen only when the program runs out of memory Linked Representation of the QUEUE public class LinkedQueue implements Queue{ QueueNode front, rear; public LinkedQueue () { front = null; rear = null; } Linked Representation of the QUEUE public void enqueue(T item) throws QueueOverflowException{ QueueNode newNode=null; try { newNode = new QueueNode(item, null); if (front == null) { front = newNode; rear = newNode; } else { rear.setLink(newNode); // rear.link rear = newNode; } } catch (Exception ex ){ throw new QueueOverflowException(“Queue full “); } } Linked Representation of the QUEUE rear/tail front/head Linked Representation of the QUEUE public T dequeue() throws QueueUnderflowException{ T x; if (front == null) throw new QueueUnderflowException("Deleting from an empty queue."); x = front.getInfo(); // x=front.info front = front.getLink(); // front = front.link return x; } Linked Representation of the QUEUE FRONT X The QUEUE Data Structure public class QueueOverflowException extends RuntimeException{ public QueueOverflowException(String err){ super(err); } } The QUEUE Data Structure 2 basic operations for data manipulation: insertion at the rear and deletion at the front interface Queue{ void enqueue(T item) throws QueueOverflowException; T dequeue() throws QueueUnderflowException; // other methods ( e.g. isEMpty ) } The QUEUE Data Structure Sequential Representation Makes use of one-dimensional array/vector Queue is empty if front=rear and full if front=0 and rear=n Deletion from an empty queue causes an underflow Insertion onto a full queue causes an overflow The QUEUE Data Structure public class QueueUnderflowException extends RuntimeException{ public QueueUnderflowException(String err){ super(err); } } The QUEUE Data Structure The QUEUE Data Structure public class SequentialQueue implements Queue{ Object Q[]; int n = 100 ; int front = 0; int rear = 0; public SequentialQueue(){ Q = new Object[n]; }  public SequentialQueue(int size){ n = size; Q = new Object[n]; } public void enqueue(T item) throws QueueOverflowException{ if (rear == n) moveQueue(); Q[rear] = (Object) item; rear++; } The QUEUE Data Structure void moveQueue() throws QueueOverflowException{ if (front==0) throw new QueueOverflowException("Inserting into a full queue"); for(int i=front; i0. Circular Queue Circular Queue Initialization: front = 0, rear = 0 Empty queue: if front = rear Full queue: if front == (rear + 1) mod n public void enqueue(Object item) throws QueueOverflowException{ if (front == (rear + 1) % n) throw new QueueOverflowException("Inserting into a full queue."); Q[rear] = item rear = (rear + 1) % n; } Circular Queue public Object dequeue() throws QueueUnderflowException{ Object x; if (front == rear) throw new QueueUnderflowException("Deleting from an empty queue."); x = Q[front]; front = (front + 1) % n; return x; } Topological Sorting – An Application – Recommended Reading Input - partially ordered elements Output - list of elements in which there is no element listed with its predecessor that is not yet in the output Partial ordering properties of ≼: Transitivity : if x ≼ y and y ≼ z, then x ≼ z Antisymmetry : if x ≼ y and y ≼ x, the x = y Reflexivity : x≼x Corollaries. If x ≼ y and x ≠ y then x ≺ y. Transitivity : if x ≺ y and y ≺ z, then x ≺ z Asymmetry : if x ≺ y then y ≺ x Irreflexivity : x≺x  To generate the output : 1. Look for an item, say k, with count of direct predecessors equal to zero, i.e., COUNT[k] == 0. Put k in the output 2. Scan list of direct successors of k, and decrement the count of each such successor by 1 3. Repeat steps 1 and 2 until all items are in the output A linked queue could be used to avoid having to go through the COUNT vector repeatedly to look for objects with a count of zero COUNT of each item j in the queue could be reused as a link field: COUNT[j] = k if k is the next item in the queue =0 if j is the rear element in the queue Reiterations A queue is a linearly ordered set of elements obeying the first-in, first-out (FIFO) principle Two basic queue operations are insertion at the rear and deletion at the front Queues have 2 implementations - sequential and linked In circular queues, there is no need to move the elements to make room for insertion The topological sorting approach discussed uses both sequential and linked allocation techniques, as well as a linked queue embedded in a sequential vector Application Simulation: A technique in which one system models the behavior of another system is called simulation. Simulation techniques are used when it is too expensive or dangerous to experiment with real systems. Queuing System Consists of servers and queues of objects waiting to be served. Server = object that provides the service ( e.g. bank teller, grocery cashier, theatre cashier) Customer = object receiving the service Service time = time it takes to serve a customer (aka transaction time) Time-driven simulation The clock is implemented as a counter and the passage of time, say 1 minute, is implemented by incrementing the counter by 1. If the simulation needs to be run fro 100 minutes, the counter starts at 1 and goes up to 100. (i.e. implemented as a loop) Main Algorithm 1. Declare and initialize the variables such as the simulation parameters (time units the simulation will run, number of servers, transaction time, interarrival time), customer number, clock, total and average waiting times, number of customers arrived, number of customers served, number of customers left in the waiting queue, number of customers left with the servers, waiting customer queue, and a list of servers. 2. The main loop is for (clock=1; clock