Description
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.
Students are expected to structure the code as indicated in the UML class diagram:
Main
+static void main(String[] args)
+Main()
Deque
-int SIZE
+Deque()
-int[] list
-int count
+boolean isEmpty()
+void push(int x)
+int pop()
+void inject(int x)
+int eject()
+int getFront()
+getRear()
+Deque(int size)
-int front
-int rear
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.
Students are expected to structure the code as indicated in the UML class diagram:
Main
+static void main(String[] args)
+Main()
Stack
+Stack()
-Node first
+boolean isEmpty()
+void push(int x)
+void pop()
+int peek()
Node
-int info
-Node next
+Node()
+void setInfo(int i)
+void setNext(Node l)
+int getInfo()
+Node getNext()
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.
Students are expected to structure the code as indicated in the UML class diagram:
Main
+static void main(String[] args)
+Main()
PriorityQueue
+PriorityQueue()
-Node first
+boolean isEmpty()
+void add(int x)
+int max()
+void removeMax()
Node
-int info
-Node next
+Node()
+void setInfo(int i)
+void setNext(Node p)
+int getInfo()
+Node getNext()
-Node prev
+setPrev(Node p)
+Node getPrev()
-Node last