CSC152 2005F, Class 41: Queues Admin: * Exams due! * Reading to be assigned over weekend. * Sam will be reviewing grant proposals for NSF on Monday. Eryn will run lab. * NSF writes: "Your panel will run until 5:30 or whenever you finish." If we run late, I won't make my plane, and you won't have class on Tuesday. Overview: * Questions on stacks? * PAMI of Queues * Implementation strategy one: Arrays * Implementation strategy two: Nodes (pairs) Stacks: * Linear structure with LIFO policy * We implement stacks with arrays (or Vectors) * We put things at the "end" (larger indices) * We get things at the "end" (larger indices) Queues: * Philosophy: Linear Structures with a FIFO policy * Applications: * Models the line at a grocery store * Many copmuter things should follow the same policy (printing queue) * Fairer for "to do lists" * Methods * Same as linear structures * Queues were designed before linear structures * enqueue and dequeue (sometimes enque and deque) (sometimes nq dq) Implementing Queues with Arrays/Vectors * Add at the front and take off the back * Interpretation: Adding at the front requires shifting * Critique: Shifting is expensive (it's a lot of shifting) * Another idea? * Add to the end, remove from the front * When we remove, remember that we've shifted the front * Critique: Lots of blank space * Response to critique (from critic) * Wrap around * Critique of response to critique * But we must make sure we never have more things than are in the Vector * In general, any strategy we choose will be a PITN An alternate strategy: Use pairs/nodes +---+---+ | | | +---+---+ car and cdr The first part stores a 'value' The second part stores the 'next node' +---+---+ +---+---+ +---+---+ | * | *---> | * | *---> | * | / | +-|-+---+ +-|-+---+ +-|-+---+ a c q * If we keep track of the front of this structure (the first node), that gives us the front of the queue FRONT BACK +---+---+ +---+---+ +---+---+ | * | *---> | * | *---> ... --> | * | / | +-|-+---+ +-|-+---+ +-|-+---+ a c q after get FRONT BACK +---+---+ +---+---+ | * | *---> ... --> | * | / | +-|-+---+ +-|-+---+ c q How do we add things? keep track of the back from FRONT BACK +---+---+ +---+---+ +---+---+ | * | *---> | * | *---> ... --> | * | / | +-|-+---+ +-|-+---+ +-|-+---+ a c q to FRONT BACK +---+---+ +---+---+ +---+---+ +---+---+ | * | *---> | * | *---> ... --> | * | ----> | * | / | +-|-+---+ +-|-+---+ +-|-+---+ +-|-+---+ a c q n Turning strategy into code. (1) Create a class, Node that defines these node things. Two fields: T value Node next (2) Create a class, NodeBasedQueue (or LinkedQueue), with at least two fields Node front Node back