Stacks and queues are basic data structures that all programmers should be familiar with. Each has many uses -- if you'd like to browse through some of these uses, visit these sites:

• https://www.geeksforgeeks.org/stack-data-structure/ (Links to an external site.)
• https://www.geeksforgeeks.org/queue-data-structure/ (Links to an external site.)

Java has convenient implementations of both these abstract data structures. For the most part, as a user of these Java classes, it is not important for you to know exactly how your stack or queue is implemented, provided it provides the functionality you expect from a stack or a queue. For your information, however, stacks are usually implemented with arrays, while queues are often implemented using another structure called a linked list (which you will learn about later in the quarter).

As programmers, you probably should have a sense of how these structures could be implemented. The following .java files give array implementations for both:

-see below for code

The ArrayStack is just implemented to accept integers, while the ArrayQueue can accept any type of Java object (i.e. it is implemented using generics). I suggest reading through the Stack implementation first.

Similar to the practice exercise for Week 6, I want you to read through the code and answer the following questions in a .pdf or a .doc file.

When answering the questions, be detailed about the changes that take place -- specify array sizes and index numbers where appropriate. If items need to be copied or moved around, discuss this. What methods are being called in order to complete the task? What do the methods do? Show that you understand how the data is being manipulated in each case to provide the desired results and functionality.

1. What happens when the 11th item is added to a stack or queue?

2. What is the number of the next item, after the 11th, that would cause the same process you just described (in Question 1) to occur?

3. Assume you have 5 items in a stack and 5 items in a queue. Thinking about the underlying structure (i.e. the array) holding the data, what happens when you remove one item from the stack and one item from the queue?

4. Can you "pop" from a queue -- in other words, is there any reason why you couldn't just copy over the method (after modifying it for generics) to use it in the queue class?

5. Look at the pre-condition and post-condition for nextInt (reproduced below):

private int nextIndex(int i) // Precondition: 0

• What method uses nextIndex( )?
• Why is the precondition necessary?
• Why does the behavior described postcondition make sense?

6. Work on one of the tasks below for no more than 1 hour (use the STARTER CODE):

TASKS:

• You are only allowed to use integer arrays and ArrayStack data structures. You can step through the array from index 0 to n only. Given an array of numbers from 1 to 9, in order, reverse the array so that the numbers are now in decreasing order.
• You have been given an ArrayQueue to which the following numbers have been added: 3, 5, 2, 1, 4. Using only the commands to add and remove values from the queue, sort the ArrayQueue (you can use variables to store some information and you may create more ArrayQueue structures, but no other data storage structures). I consider this the harder of the two tasks.

The output of the program with both problems solved should be:

-see below

7. After one hour, look at one possible solution for your chosen task. Comment on where you got stuck (if you did). Try to understand what the code in the solution provided is doing and explain this in English (not code) here. If you got the solution within the hour allotted, explain your solution instead.

// Double the capacity and add 1; this works even if many Items is o. However, in // case that many Items*2 + 1 is beyond Integer .MAX_VALUE, there will be an // arithmetic overflow and the bag will fail. ensureCapacity (manyItems*2 + 1); } data[manyItems] = item; manyItems++; } /** * Accessor method to determine the number of items in this stack. @return the number of items in this stack public int size() return manyItems; } Reduce the current capacity of this stack to its actual size (i.e., the number of items it contains). Postcondition: This stack's capacity has been changed to its current size. @exception OutOfMemoryError Indicates insufficient memory for altering the capacity. **/ public void trimtosize() int trimmedArray[ ]; if (data. length != many Items) { trimmedArray = (int[]) new int[many Items]; System.arraycopy(data, o, trimmedArray, o, manyItems); data = trimmedArray; S/ The output of the program with both problems solved should be: Stack_Queue_Solutions [Java Application] OPTION 1 My stack: bottom~1~2~3~4~5~6~7~8~9~top My reversed stack: bottom~9~8~7~6~5~4~3~2~1~top OPTION 2 My queue: front~3~5~2~1~4~back My sorted queue: front-1-2-3-4-5-back Page Postcondition: . This queue's capacity has been changed to its current size. @exception out of everyError Indicates insufficient nenpry for altering the capacity. **/ @suppresswarnings ("unchecked) public void tran Toize!! El trindarray: int 11, 2; if (data length == ranyitens) 1/ No change needed return; else if (hanyIters == 0) // Just change the size of the array to a because the queue is empty. data - (ECT) new object[a] else if (front c= rear) { // Create trimmed array and copy data front)...data[rear] into it. trimmedArray) neu Object (ranya! Systen.arraycopy data, front, trimedarray, front, many Iters): data = trintedArray: } else { // Create a trimmed array, hut be careful about copying icers into it. The queue iters 17 occur in tu segrets. The first segment goes from date [front] to the end of the 17 array, and the second segrent goes froe data[6] to data(rear). The variables ni 1 and 2 will be set to the number of iters in these two segments. We will copy. // these segments to triedarray[e...any Items-1). triedarray()) neu object[rany]: n1 = data. Length front; n2 = rear + 1; Systen.arraycopy data, frant, trimmedarray, 6, 2); Systen.arraycopyidata, o, trivredArray, ni, n2); front = 0; rear = nany Iters-1; data - trivedArray: front, , 6, 13)