Upgrade ResizingArrayStack class

Start with ResizingArrayStack.java (generic version).

Add a method dup() to Stack that creates a second copy of the topmost element and pushes it onto the stack.

Add a method exch() to Stack that exchanges the top two elements on the stack.

Add a method size() to Stack that returns the number of elements on the stack.

All those methods must be public

File name = ResizingArrayStack.java

Implement Queue class which uses a linked list with only one access pointer.

Start with Queue.java using linked list. Refer to the book for the details (Algorithm 1.3 in Section 1.3)

Re-implement a queue, so that

with all operations taking constant time,

but only one instance variable (instead of two of Node first or Node last). So delete one of those two.

Hint: use a circular linked list, maintaining a pointer to the last item.

File name = Queue.java

_____________________________________________________________________________________

ResizingArrayStack

import java.util.Iterator; public class ResizingArrayStack implements Iterable { private Item[] a = (Item[]) new Object[1]; // stack items private int N = 0; // number of items public boolean isEmpty() { return N == 0; } public int size() { return N; } private void resize(int max) { // Move stack to a new array of size max. Item[] temp = (Item[]) new Object[max]; for (int i = 0; i < N; i++) temp[i] = a[i]; a = temp; } public void push(Item item) { // Add item to top of stack. if (N == a.length) resize(2*a.length); a[N++] = item; } public Item pop() { // Remove item from top of stack. Item item = a[--N]; a[N] = null; // Avoid loitering (see text). if (N > 0 && N == a.length/4) resize(a.length/2); return item; } public Iterator iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements Iterator { // Support LIFO iteration. private int i = N; public boolean hasNext() { return i > 0; } public Item next() { return a[--i]; } public void remove() { } } }

_________________________________________________

Queue 

public class Queue implements Iterable { private Node first; // link to least recently added node private Node last; // link to most recently added node private int N; // number of items on the queue private class Node { // nested class to define nodes Item item;

Node next; }

public boolean isEmpty() { return first == null; } // Or: N == 0. public int size() { return N; } public void enqueue(Item item) { // Add item to the end of the list. Node oldlast = last; last = new Node(); last.item = item; last.next = null; if (isEmpty()) first = last; else oldlast.next = last; N++; }

public Item dequeue() { // Remove item from the beginning of the list. Item item = first.item; first = first.next; if (isEmpty()) last = null; N--; return item; } }