Data Structures

When you write a program using an abstract data structure, you can complete the design of the program before you determine the actual implementation of the data structure. If you design the interfaces carefully, you should be able to change the way you implement the data structure without affecting the outcome of the program. In this Application, you will write alternative pseudocode implementations of a queue.

A queue is a first-in, first-out list. The queue has two essential operations: enqueue, which appends an entry to the end of the list (called the tail) and dequeue, which returns and removes the first entry in the list (called the head). The queue returns entries in the sequence in which they were added. When you do this in real life, you may refer to it as “standing in line.” Some queue implementations include auxiliary operations that may allow programmers to write simpler code.

1. Write pseudocode that represents the abstract functions of the enqueue and dequeue operations. Define and explain any supplementary information needed by your pseudocode.
2. Refer to the fixed array implementation in Figure 8.5 of your textbook. Write pseudocode that implements the enqueue and dequeue operations by using a fixed array named Cells. The head of the queue should always be in Cells[1]. Define and explain any supplementary information needed by your pseudocode.
3. Refer to the circular array implementation in Figure 8.14 of your textbook. Write pseudocode that implements the enqueue and dequeue operations using this technique. Define and explain any supplementary information needed by your pseudocode.
4. What do you see as the advantages and disadvantages of each implementation?