Week 5 Objectives

KNOW:

• The difference between a linked list and a sequential list
• that a queue is a first-in-first-out (FIFO) data structure
• that a queue is a useful data structure when keeping track of multiple clients waiting for a single resource (such as spooling jobs to a printer, simulating arrivals of customers at a check-out line, routing packets of information in a computer network)

BE ABLE TO:

• de-reference a pointer to a struct
• Write code to build a linked list
• Write code to traverse a linked list
• implement the queue operations (enqueue, dequeue, isEmpty) using a linked list
• implement the queue operations (enqueue, dequeue, isEmpty) using an array
• use a queue to solve various problems

Sample Quiz Questions:

1. Implement the following function:

       int everyNodeIsx (struct listNode* head, int x);
       /* Precondition: head is the head pointer of a 
       ** non-empty linked list.
       ** Postcondition: The return value is 1 (true) if every node in the
       ** list contains x in the data part. Otherwise, the return value
       ** is 0 (false).
       */
   

2. Explain why the dequeue operation works differently for a queue containing one item as opposed to a queue containing more than one item.