EECS2011A-F21: Fundamentals of Data Structures
Assignment 2 (15%)
Due: November 15, 2021 @ 9:00pm
Problem 1 [6 points]
Implement the Queue presented in Listing 1 using instances of Stack data structure. You are only allowed
to use standard Stack operations (as can be seen in Listing 2). You can use any number of Stack instances
to implement your Queue.
1 public interface Queue {
2 int size(); // Returns the number of elements in the queue.
3 boolean isEmpty (); // Tests whether the queue is empty.
4 void enqueue(E e); // Inserts an element at the rear of the queue.
5 E first (); //Returns , but does not remove , the first element of the queue.
6 E dequeue (); // Removes and returns the first element of the queue.
7 }
Listing 1: Queue Interface
1 public interface Stack {
2 int size(); // Returns the number of elements in the stack.
3 boolean isEmpty (); // Tests whether the stack is empty.
4 void push(E e); // Inserts an element at the top of the stack.
5 E top(); // Returns , but does not remove , the element at the top of the stack.
6 E pop(); // Removes and returns the top element from the stack.
7 }
Listing 2: Stack Interface
Hint & Constraint
First, you need to implement your Stack data structure using arrays (see section 6.1.2 in the text
book) and then leverage your Stack class to implement the Queue data structure.
Problem 2 [6 points]
In this problem, you will to do the opposite of what you have done in Problem 1. This time, implement the
Stack data structure using only instances of the Queue data structure.
Hint & Constraint
This time, you need to use singly linked list as the fundamental data structure (see section 6.2.3
in the text book) to implement your queue.
1
Problem 3 [10 points]
A Deque is a special kind of queue in which insertions and deletions can be done at both ends. Please
refer to section 6.3 in the text book for details on Deque. Implement a Deque using doubly linked list and
then by leveraging adapter design pattern implement Stack and Queue data structures using your Deque
implementation for which, you implement the following interface.
1 /**
2 * Interface for a double -ended queue; this interface
3 * is a simplified version of java.util.Deque.
4 */
5 public interface Deque {
6 int size(); // Returns the number of elements in the deque.
7 boolean isEmpty (); // Tests whether the deque is empty.
8 E first (); // Returns (but not remove) the first element of the deque.
9 E last(); // Returns (but not remove) the last element of the deque.
10 void addFirst(E e); // Inserts an element at the front of the deque.
11 void addLast(E e); // Inserts an element at the back of the deque.
12 E removeFirst (); // Removes and returns the first element of the deque.
13 E removeLast (); // Removes and returns the last element of the deque.
14 }
Listing 3: Deque Interface
Hint
In fact, the DoublyLinkedList class from Section 3.4.1 in the textbook, which we fully discussed in the
class, already implements the entire above Deque interface; you simply need to add the declaration
“implements Deque< E >” to that class definition in order to use it as a Deque.
2
Problem 4 [8 points]
Suppose you are given an array, A, containing n distinct integers that are listed in increasing order. Given
a number k, implement a recursive algorithm to find two integers in A that sum to k, if such a pair exists.
What is the running time of your algorithm?
Submission
Deliverables:
Submit one zip file named as Assignment2.zip including 4 folders (i.e., packages) each of which con-
taining related classes for the corresponding problem. Name the 4 packages as Problem1, Problem2,
Problem3 and, Problem4. For Problem 4, you need to have a Discussion.txt file in Problem4 folder
in which you explain the running time of your algorithm in one paragraph. In each folder you also
need to have a TestClass.java in which you test your implementation. The TA starts with this
class to grade your assignment.
3

欢迎咨询51作业君