<![CDATA[
CSE143 Midterm Cheatsheet
Queues should be constructed using the Queue<E> interface and the
LinkedQueue<E> implementation. For example, to construct a queue of String
values, you would say:
Queue<String> q = new LinkedQueue<String>();
Stacks should be constructed using the Stack<E> interface and the
ArrayStack<E> implementation. For example, to construct a stack of String
values, we would say:
Stack<String> s = new ArrayStack<String>();
To transfer from a queue to a stack:
while (!q.isEmpty())
s.push(q.dequeue());
To transfer from a stack to a queue:
while (!s.isEmpty())
q.enqueue(s.pop());
-------------------------------------------------------------------------------
// Interface Queue defines a set of operations for manipulating a FIFO
// (First In First Out) structure that can be used to store objects.
public interface Queue<E> {
// post: given value inserted at the end of the queue
public void enqueue(E value);
// pre : !isEmpty()
// post: removes and returns the value at the front of the queue
public E dequeue();
// post: returns true if the queue is empty, false otherwise
public boolean isEmpty();
// post: returns the current number of elements in the queue
public int size();
}
-------------------------------------------------------------------------------
// Interface Stack defines a set of operations for manipulating a LIFO
// (Last In First Out) structure that can be used to store elements of
// type E.
public interface Stack<E> {
// post: given value is pushed onto the top of the stack
public void push(E value);
// pre : !isEmpty()
// post: removes and returns the value at the top of the stack
public E pop();
// post: returns true if the stack is empty, false otherwise
public boolean isEmpty();
// post: returns the current number of elements in the stack
public int size();
}
]]>