CSE143 Sample Program handout #10
Stack Interface
---------------
// Interface Stack defines a set of operations for manipulating a LIFO
// (Last In First Out) structure that can be used to store objects.
public interface Stack {
// 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
---------------
// 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 {
// 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();
}
Testing Program StackQueueTest.java
-----------------------------------
// Stuart Reges
// 4/18/05
//
// This program demonstrates some simple stack and queue manipulations.
import java.util.*;
public class StackQueueTest {
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
System.out.print("line to reverse? ");
reverseData(new Scanner(console.nextLine()));
System.out.println();
System.out.print("numbers to split? ");
split(new Scanner(console.nextLine()));
}
// pre : input != null
// post: reads all words (tokens) from the given Scanner, writing them to
// System.out in reverse order.
public static void reverseData(Scanner input) {
Stack s = new ArrayStack();
while (input.hasNext())
s.push(input.next());
while (!s.isEmpty())
System.out.print(s.pop() + " ");
System.out.println();
}
// pre : input != null
// post: reads ints from the given Scanner until the input ends or the next
// token is not an int. Writes integers to System.out with all
// negatives written before all nonnegatives and with the original
// order otherwise preserved.
public static void split(Scanner input) {
Queue q = new LinkedQueue();
while (input.hasNextInt()) {
int n = input.nextInt();
if (n >= 0)
q.enqueue(n);
else
System.out.print(n + " ");
}
while (!q.isEmpty())
System.out.print(q.dequeue() + " ");
System.out.println();
}
}
Log of execution of testing program StackQueueTest
--------------------------------------------------
line to reverse? four score and seven years ago
ago years seven and score four
numbers to split? 1 2 3 -8 6 8 -4 -2 -1 10 12
-8 -4 -2 -1 1 2 3 6 8 10 12