<![CDATA[
(courtesy Stuart Reges -- GY added top and front)
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(Object value);
// pre : !isEmpty()
// post: removes and returns the value at the top of the stack
public Object pop();
// pre : !isEmpty()
// post: returns the value at the top of the stack
public Object top(); // also called peek
// 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(Object value); // also called offer
// pre : !isEmpty()
// post: removes and returns the value at the front of the queue
public Object dequeue(); // variants include remove and poll
// pre : !isEmpty()
// post: returns the value at the front of the queue
public Object front(); // also called peek
// 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.
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(new Integer(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
Stack implementation ArrayStack.java
------------------------------------
// ArrayStack provides an implementation of the Stack interface that uses an
// ArrayList to store the elements of the stack. All operations will execute
// in O(1) time.
import java.util.*;
public class ArrayStack implements Stack {
private ArrayList elements;
// post: constructs an empty stack
public ArrayStack() {
elements = new ArrayList();
}
// post: given value is pushed onto the top of the stack
public void push(Object value) {
elements.add(value);
}
// pre : !isEmpty()
// post: removes and returns the value at the top of the stack
public Object pop() {
if (isEmpty())
throw new IllegalStateException("attempt to pop empty stack");
return elements.remove(elements.size() - 1);
}
// pre : !isEmpty()
// post: returns the value at the top of the stack
public Object top() {
if (isEmpty())
throw new IllegalStateException("attempt to pop empty stack");
return elements.get(elements.size() - 1);
}
// post: returns true if the stack is empty, false otherwise
public boolean isEmpty() {
return elements.isEmpty();
}
// post: returns the current number of element in the stack
public int size() {
return elements.size();
}
// post: returns a String representation of the stack contents
public String toString() {
return "bottom " + elements + " top";
}
}
Queue implementation LinkedQueue.java
-------------------------------------
// LinkedQueue provides an implementation of the Queue interface that uses a
// LinkedList to store the elements of the queue. All operations will execute
// in O(1) time.
import java.util.*;
public class LinkedQueue implements Queue {
private LinkedList elements;
// post: constructs an empty queue
public LinkedQueue() {
elements = new LinkedList();
}
// post: given value inserted at the end of the queue
public void enqueue(Object value) {
elements.addLast(value);
}
// pre : !isEmpty()
// post: removes and returns the value at the front of the queue
public Object dequeue() {
if (isEmpty())
throw new IllegalStateException("attempt to dequeue empty queue");
return elements.removeFirst();
}
// pre : !isEmpty()
// post: removes and returns the value at the front of the queue
public Object front() {
if (isEmpty())
throw new IllegalStateException("attempt to dequeue empty queue");
return elements.getFirst();
}
// post: returns true if the queue is empty, false otherwise
public boolean isEmpty() {
return elements.isEmpty();
}
// post: returns the current number of element in the queue
public int size() {
return elements.size();
}
// post: returns a String representation of the queue contents
public String toString() {
return "front " + elements + " back";
}
}
]]>