<![CDATA[
CSE143 Stack/Queue Examples handout #9
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
------------------------------
// Program that demonstrates some simple stack/queue operations
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);
System.out.println();
Stack<Integer> s = new ArrayStack<Integer>();
queueToStack(q, s);
System.out.println("after queueToStack:");
System.out.println(" queue = " + q);
System.out.println(" stack = " + s);
System.out.println();
s = makeRandomStack(10);
System.out.println("initial stack = " + s);
System.out.println("sum = " + sum(s));
System.out.println("after sum stack = " + s);
System.out.println();
stackToQueue(s, q);
System.out.println("after stackToQueue:");
System.out.println(" stack = " + s);
System.out.println(" queue = " + q);
}
// 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: Values from q moved to s (added in queue order, front to back);
// q is empty
public static void queueToStack(Queue<Integer> q, Stack<Integer> s) {
while (!q.isEmpty()) {
int n = q.dequeue();
s.push(n);
}
}
// post: Values from s moved to q (added in stack order, top to bottom);
// s is empty
public static void stackToQueue(Stack<Integer> s, Queue<Integer> q) {
while (!s.isEmpty()) {
int n = s.pop();
q.enqueue(n);
}
}
// 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 n = q.dequeue();
sum += n;
q.enqueue(n);
}
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 n = s.pop();
sum += n;
q.enqueue(n);
}
queueToStack(q, s);
stackToQueue(s, q);
queueToStack(q, s);
return sum;
}
}
]]>