New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Computer Science II Chapter 7

by: Gaoqi Zheng

Computer Science II Chapter 7 CSE 214

Marketplace > Stony Brook University > ComputerScienence > CSE 214 > Computer Science II Chapter 7
Gaoqi Zheng
Stony Brook U

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Chapter 7 - Queues
Computer Science II
Ahmad Esmaili
Class Notes
Computer Science
25 ?




Popular in Computer Science II

Popular in ComputerScienence

This 31 page Class Notes was uploaded by Gaoqi Zheng on Monday March 28, 2016. The Class Notes belongs to CSE 214 at Stony Brook University taught by Ahmad Esmaili in Spring 2016. Since its upload, it has received 16 views. For similar materials see Computer Science II in ComputerScienence at Stony Brook University.

Similar to CSE 214 at Stony Brook U


Reviews for Computer Science II Chapter 7


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 03/28/16
Queues Chapter 7 Fundamentals • A queue is a sequence of data elements (of the same type) arranged one after another conceptually. • An element can be added to the rear of the queue only. (“ENQUEUE”) • An element can be removed from the front of the queue only. (“DEQUEUE”) Applications of Queues • Operating systems - input buffers, print queues, process scheduling • Telecommunications and transportation engineering - modeling and simulation of computer and phone networks, road systems and transportation hubs Conceptual Picture 12 31 20 Depending on the FRONT REAR implementation of a queue, it may or may not have a maximum capacity. ENQUEUE 49 12 31 20 49 FRONT REAR REAR X DEQUEUE 12 12 31 20 49 FRONT FRONT REAR X Depending on the implementation of the queue, the 12 may still be in memory but is not part of the queue. Basic Queue Operations • Constructor – create an empty queue • isEmpty – is the queue empty? • enqueue – insert an element on to the rear of the queue (if the queue is not full) • dequeue – remove the front element from the queue (if the queue is not empty) Example: Jai Alai Jai Alai Rules • Played by 8 teams. • Two teams play against each other while the others wait in a queue. • After each match of two teams, the loser goes to the end of the queue, and the first team in the queue leaves and plays the previous winner. • During the first seven matches, the winner of each match earns one point. • After the first seven matches, the winner of each match earns two points. • The game ends when one team earns 7 points. Implementation of a Queue • ARRAYS front element is always in first array cell 12 31 20 front rear rear element is always in last array cell 12 31 20 front rear Is there a better way? Implementation of a Queue • ARRAYS (a better way) 12 31 20 front rear 20 12 31 rear front An IntQueue using Arrays public class IntQueue implements Cloneable { public final int CAPACITY = 100; private int[] data; private int front; private int rear; // IntQueue methods (clone not shown) } IntQueue (arrays) (cont’d) public IntQueue() { front = -1; rear = -1; data = new int[CAPACITY]; } public boolean isEmpty() { return (front == -1); } IntQueue (arrays) (cont’d) public void enqueue(int item) { if ((rear+1)%CAPACITY == front) throw new FullQueueException(); if (front == -1) { // isEmpty() front = 0; rear = 0; } else rear = (rear+1)%CAPACITY; data[rear] = item; } IntQueue (arrays) (cont’d) public int dequeue() { int answer; if (front == -1) // isEmpty() throw new EmptyQueueException(); answer = data[front]; if (front == rear) { front = -1; rear = -1; } else front = (front+1)%CAPACITY; return answer; Implementation of a Queue • LINKED LISTS Which is more efficient? 12 31 20 front rear 20 31 12 rear front An IntQueue using Lists public class IntQueue implements Cloneable { private IntNode front; private IntNode rear; // IntQueue methods (clone not shown) } IntQueue (lists) (cont’d) public IntQueue() { front = null; rear = null; } public boolean isEmpty() { return (front == null); } IntQueue (lists) (cont’d) public void enqueue(int item) { IntNode newNode = new IntNode(item); if (front == null) { front = newNode; rear = front; } else { rear.setLink(newNode); rear = newNode; } } IntQueue (lists) (cont’d) public int dequeue() { int answer; if (front == null) throw new EmptyQueueException(); answer = front.getData(); front = front.getLink(); if (front == null) rear = null; return answer; } Priority Queue • Applications • Implementations front rear 27 23 10 19 36 29 72 48 2 1 3 1 2 3 4 2 Random Numbers • Math.random() returns a random uniformly- distributed double in the range [0.0,1.0) . • Generating a random double in [0.0,10.0): Math.random() * 10.0 • Generating a random int in [0,10): (int)(Math.random() * 10.0) • Generating a random int in [5,15): (int)(Math.random() * 10.0 + 5.0) Random Numbers (cont’d) • An event E occurs with probability p. • 0 < p < 1 • Example: Roll a die. Let E = a roll of 1. For this event, p = 1/6 . • We need a function such that if we call this function N times, where N is very large, then - the function returns true pN times - the function returns false (1-p)N times BooleanSource • The probability of an event occurring is ¼. • Does the event occur? • Generate a uniform random number between 0 and 1. (Any number is equally- likely to be generated in that range.) 0 0.25 1 If the number is in If the number is in this range, return TRthis range, return FALSE Random Numbers (cont’d) public class BooleanSource { private double probability; public BooleanSource(double p) throws {.. if (p < 0.0 || p > 1.0) throw new IllegalArgumentExceptio;() probability = p; } public boolean occurs() { return (Math.random() < probability); } } Car Wash Simulation CAR WASH How long, on average, does a car have to wait once it arrives on line before it is washed? Car Simulator (cont’d) • Assumptions: - One car can be washed at a time. - At most one car can arrive per second. • Simulation time unit is the second. • Queue will store arrival time of each car. • What can happen during any given second? 1. A car can arrive. 2. A car can enter the car wash. 3. A car can be washed for one second. Simulator public static void carWash(int washTime, double arrivalProb, int totalTime) { if (washTime <= 0 || arrivalProb < 0.0 || arrivalProb > 1.0 || totalTime < 0) { System.out.println(“NO SIMULATION”); return; } // simulation variables IntQueue cars = new IntQueue(); BooleanSource arrival = new BooleanSource(arrivalProb); Car Wash Simulation (cont’d) // simulation variables (cont’d) int totalWaitTime = 0; int carsWashed = 0; double avgWaitTime; int currentSecond; int timeLeftInWasher = 0; // loop simulates each second of time for ( currentSecond = 1; currentSecond <= totalTime; currentSecond++) Car Wash Simulation (cont’d) // EVENT 1: has a car arrived? if (arrival.occurs()) cars.enqueue(currentSecond); // EVENT 2: can we take a car off the // queue and put it in the car wash? if ((timeLeftInWasher == 0) && (!cars.isEmpty())) { timeLeftInWasher = washTime; totalWaitTime += (currentSecond – cars.dequeue()); carsWashed++; } Car Wash Simulation (cont’d) // EVENT 3: wash a car for 1 second if (timeLeftInWasher > 0) timeLeftInWasher--; } // end for loop // calculate final statistics avgWaitTime = (double)totalWaitTime/carsWashed; System.out.println(“Avg wait time = ” + avgWaitTime + “ seconds.”); }


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.