Class Notes (811,134)
Canada (494,511)
CMPT 225 (60)
John Edgar (28)
Lecture 3

CMPT 225 Week 3 Lecture 2

2 Pages
Unlock Document

Simon Fraser University
Computing Science
CMPT 225
John Edgar

Queues Assignment 2 is writing a linked list to implement a queue Queues are sometimes referred to as "fair algorithms" (although prof dislikes) FIFO (first in, first out) For a print queue, want a request class (data) and a collection class (the data structure) Items are inserted at back and removed from front, like a line. Or a queue. Queues need to implement at least insert (enqueue) and remove (dequeue). Peek is optionally but very nice to have! And, of course, default constructor that allows you to create an empty queue. Assumed that these will be performed efficiently, in constant time Dequeue is just dependant on order in which elements are recieved, nothing else. Will be looking at two implementations: one with an array, one with a linked list Array Implementation: What is the index going to be for the front and the back of the queue? Back -> current size of array, much like stack implementation Initially make front of queue index 0. Inserting is easy!Add and increment back. Removing: remove and increment front. Don't reuse the space at the front. Wastes space. Could have absurd situation where queue is full, but only has 1 entity in it. Could go and shuffle everything down rather than incrementing front. However, this is not constant time. So, can use a circular array. Not a new data structure; just pretend that it's arranged in a circle, rather than a straight line. End of array wraps around and fills empty spaces in front. Mod operator (%) calculates remainders. Can be used to calc front and back in circular array without if statements! Back of queue is: (front + num) % queue.length num is number of items in queue After removing an item the front of the queue is: (front + 1) % queue.length; If you're going to make a bigger array, could fill new array from index 0 upwards, but start at the actual front. So, in the new array front of the new queue is 0.A bit less confusing/hard to map this way! In the end, all that matters are that items are in the same order and the front and back indices are correct. Can implement in multiple ways! However, isn't always be better to have so
More Less

Related notes for CMPT 225

Log In


Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.