<![CDATA[
CSE143 Stack/Queue Examples handout #10
Stack Interface
---------------
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 element in the stack
public int size();
}
Queue Interface
---------------
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 element in the queue
public int size();
}
Sample Program StackQueue.java
------------------------------
import java.util.*;
public class StackQueue {
public static void main(String[] args) {
Queue<Integer> q = makeRandomQueue(10);
System.out.println("initial queue = " + q);
System.out.println("sum = " + sum(q));
System.out.println("after sum queue = " + q);
clear(q);
System.out.println("after clear queue = " + q);
System.out.println();
Stack<Integer> s = makeRandomStack(10);
System.out.println("initial stack = " + s);
System.out.println("sum = " + sum(s));
System.out.println("after sum stack = " + s);
clear(s);
System.out.println("after clear stack = " + s);
}
// pre : size >= 0
// post: returns a queue of size random values from 0 to 99
public static Queue<Integer> makeRandomQueue(int size) {
Random r = new Random();
Queue<Integer> q = new LinkedQueue<Integer>();
for (int i = 0; i < size; i++)
q.enqueue(r.nextInt(100));
return q;
}
// pre : size >= 0
// post: returns a stack of size random values from 0 to 99
public static Stack<Integer> makeRandomStack(int size) {
Random r = new Random();
Stack<Integer> s = new ArrayStack<Integer>();
for (int i = 0; i < size; i++)
s.push(r.nextInt(100));
return s;
}
// post: q is empty
public static void clear(Queue<Integer> q) {
while (!q.isEmpty())
q.dequeue();
}
// post: s is empty
public static void clear(Stack<Integer> s) {
while (!s.isEmpty())
s.pop();
}
// post: returns the sum of the values in q
public static int sum(Queue<Integer> q) {
int sum = 0;
for (int i = 0; i < q.size(); i++) {
int next = q.dequeue();
sum += next;
q.enqueue(next);
}
return sum;
}
// post: returns the sum of the values in s
public static int sum(Stack<Integer> s) {
int sum = 0;
Queue<Integer> q = new LinkedQueue<Integer>();
while (!s.isEmpty()) {
int next = s.pop();
sum += next;
q.enqueue(next);
}
while (!q.isEmpty())
s.push(q.dequeue());
while (!s.isEmpty())
q.enqueue(s.pop());
while (!q.isEmpty())
s.push(q.dequeue());
return sum;
}
}
Sample Execution of StackQueue
------------------------------
initial queue = front [66, 78, 6, 79, 84, 53, 72, 17, 46, 2] back
sum = 503
after sum queue = front [66, 78, 6, 79, 84, 53, 72, 17, 46, 2] back
after clear queue = front [] back
initial stack = bottom [15, 36, 75, 73, 4, 52, 10, 33, 61, 85] top
sum = 444
after sum stack = bottom [15, 36, 75, 73, 4, 52, 10, 33, 61, 85] top
after clear stack = bottom [] top
]]>