Objective

Students will be able to create skills in the use of linked lists, the stack, and the queue abstract data types, by implementing solutions to fundamental data structures and associated problems.

Assignment Questions 1. (This exercise is a variation of Exercise 3.28 in Chapter 3 of the textbook) A deque is a data structure

consisting of a list of items, on which the following operations are possible:

push(x): insert item x on the front end of the queue. pop(): remove the front item from the deque and return it. inject(x): insert item x on the rear end of the queue. eject(): remove the rear item from the deque and return it. getFront(): returns the element at the front of the deque. getRear(): returns the element at the rear of the deque.

Write routines to support the deque that take O(1) time per operation. Use an array-based implementation. Write a tester class and name it Main.

2. (This exercise is a variation of Exercise 3.28 in Chapter 3 of the textbook) Implement a Stack class using a linked list. Write a tester class and name it Main.

3. Implement a priority queue (priorities will be integers) using a doubly linked list. Assume that the smaller the integer the higher priority. The main operations of the priority queue are:

add (n): inserts priority n. max: returns (but does not delete) the highest priority. removeMax(): removes a highest priority.

Write a tester class and name it Main.

Guidelines

The assignment is to be completed individually. Questions are based on the content studied in class on linked lists, stacks, queues, and their variations.

You are allowed to use all of the code given in the lectures. In those cases, make sure you properlycredit its source. For example, lets say that you decide to implement the deque class by inheritance from the queue class given in the lecture, then add comments on top of the queue class files stating its source.