Welcome to the Deque Tester! Choose capacity of deque (suggested is 8): 8 >h q : to quit h : for help ps : to print size of deque pr : to print item at rear of deque pf : to print item at front of deque pd : to print all items in deque rr : to remove item from rear rf : to remove item from front ir x : to insert string x at rear if x : to insert string x at front >ir the Inserting "the" at rear... Contents of deque: [ the ] >if in Inserting "in" at front... Contents of deque: [ in the ] >ps Size of deque is 2 >pd Contents of deque: [ in the ] >if cat Inserting "cat" at front... Contents of deque: [ cat in the ] >ps Size of deque is 3 >ir hat Inserting "hat" at rear... Contents of deque: [ cat in the hat ] >pf Front item is cat >pr Rear item is hat >if A Inserting "A" at front... Contents of deque: [ A cat in the hat ] >rf Removing item at front... Contents of deque: [ cat in the hat ] >ir croaked Inserting "croaked" at rear... Contents of deque: [ cat in the hat croaked ] >rr Removing item at rear... Contents of deque: [ cat in the hat ] >rf Removing item at front... Contents of deque: [ in the hat ] >rf Removing item at front... Contents of deque: [ the hat ] >rr Removing item at rear... Contents of deque: [ the ] >rf Removing item at front... Contents of deque: [ ] >q Goodbye. |
A double-ended queue (deque, for short) is a linear container structure, like a stack or a queue. In a stack, insertions and removals of elements occur at the same end (referred to as the top). In a queue, insertions occur at one end (the rear) and removals at the other (the front). A deque combines these capabilities by allowing both insertions and removals to occur at either end. (By convention, we refer to the two ends of a deque using the same terms as in a queue: front and rear.)
Array-based implementations of stacks and queues were covered in lecture. In particular, the array-based implementation of a queue imagined the array as being a "wraparound" or circular structure in which location zero is the immediate successor of location N−1 and, inversely, location N−1 is the immediate predecessor of location zero (where N is the length of the array). (See the links, on the CMPS 144 course web page, to relevant web pages about queues.)
For this activity, you are to complete the Java class DequeViaArray, which implements deques using a wraparound array-based representation. You will need these files:
Note that several methods (including three of the first four in this list) depend upon one of the last two, so it behooves you to ensure that successorLoc(), and predessorLoc() are made to be correct.
Your testing should be more thorough than what is shown there. In particular, you should make sure that among the insertions and removals that you carry out, there are more insertions than the length of the array. (Otherwise, the "wraparound" logic will never come into play.) Also make sure that removing the last item from a deque (whether it be removed from the front or the rear) not only leaves you with an empty deque but also one on which a subsequent insertion (at front or rear) works correctly.
As an example, consider the instance of DequeViaArray shown below. It represents a deque containing (going from front to rear) dog, cat, elk, and bug.
contents[]
0 1 2 3 4 5 6 7 frontLoc numItems
+---+---+---+---+---+---+---+---+ +---+ +---+
|elk|bug| - | - | - | - |dog|cat| | 6 | | 4 |
+---+---+---+---+---+---+---+---+ +---+ +---+
|
Think of the array contents[] as being circular in nature, so that location 0 is the successor of location 7 (and, inversely, 7 is the predecessor of 0). You can think of moving from a location to its succcessor (respectively, predecessor) as going clockwise (respectively, counterclockwise) by one position around a circle.
There are four mutator methods, because you can insert and remove at both the front and the rear. The following diagram shows how an instance of the DequeViaArray class would change as a particular sequence of calls of these methods were applied to it. (The dashes in the array elements indicate "don't care", meaning that the values there are irrelevant.)
contents[]
0 1 2 3 4 5 6 7 frontLoc numItems
+---+---+---+---+---+---+---+---+ +---+ +---+
|elk|bug|pig| - | - | - |dog|cat| | 6 | | 5 |
+---+---+---+---+---+---+---+---+ +---+ +---+
Three applications of removeFront() (each of which decreases
numItems by one) and moves frontLoc to its
successor location (first to 7, then to 0, then to 1) yields
contents[] 0 1 2 3 4 5 6 7 frontLoc numItems +---+---+---+---+---+---+---+---+ +---+ +---+ | - |bug|pig| - | - | - | - | - | | 1 | | 2 | +---+---+---+---+---+---+---+---+ +---+ +---+The values in the array locations in which the removed items were stored could be replaced by null, but that is not a necessity. Now suppose that insertAtFront(emu) and insertAtFront(ape) were the next two operations applied. Each one moves frontLoc to its predecessor location, places the new item into that location, and increases numItems by one. So we get contents[] 0 1 2 3 4 5 6 7 frontLoc numItems +---+---+---+---+---+---+---+---+ +---+ +---+ |emu|bug|pig| - | - | - | - |ape| | 7 | | 4 | +---+---+---+---+---+---+---+---+ +---+ +---+Suppose now that removeRear() is applied. All we need to do is to decrement numItems. We get contents[] 0 1 2 3 4 5 6 7 frontLoc numItems +---+---+---+---+---+---+---+---+ +---+ +---+ |emu|bug| - | - | - | - | - |ape| | 7 | | 3 | +---+---+---+---+---+---+---+---+ +---+ +---+Suppose that insertAtRear(eel) is applied next. Then eel should be placed into the location that is the successor of the location containing the rear, and numItems should be incremented. We get contents[] 0 1 2 3 4 5 6 7 frontLoc numItems +---+---+---+---+---+---+---+---+ +---+ +---+ |emu|bug|eel| - | - | - | - |ape| | 7 | | 4 | +---+---+---+---+---+---+---+---+ +---+ +---+ |