Stacks and Queues
An Introduction with Examples in Java |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
1 | . | . |
1 | 2 | . |
/** * A Stack (of Object objects) * * This implementation uses contiguous memory * * @version 1.0 * @author Prof. David Bernstein, James Madison University */ public class Stack { private int top; private Object[] contents; public static final int CAPACITY = 100; /** * Construct a new (empty) Stack */ public Stack() { top = -1; contents = new Object[CAPACITY]; } /** * Pop an Object off of the top of this Stack * * @return The Object on the top of this Stack */ public Object pop() { Object value; if (top != -1) { value = contents[top]; top = top - 1; } else { value = null; } return value; } /** * Push an Object onto the top of this Stack * * @param first The Object to push */ public void push(Object first) { if (top < CAPACITY-1) { top = top + 1; contents[top] = first; } } }
Node
Class/** * A Node (containing an Object) in a singly-linked * data structure * * Note: This class is not public. Hence, it will only * be visible to classes in this package. (This is an * example of package visibility.) * * @author Prof. David Bernstein, James Madison University * @version 1.0 */ class Node { Object value; Node next; }
Stack
/** * A Stack (of Object objects) * * This implementation uses linked memory * * @version 1.0 * @author Prof. David Bernstein, James Madison University */ public class Stack { private Node top; /** * Construct a new (empty) Stack */ public Stack() { top = null; } /** * Pop an Object off of the top of this Stack * * @return The Object on the top of this Stack */ public Object pop() { Object value; if (top != null) { value = top.value; top = top.next; } else { value = null; } return value; } /** * Push an Object onto the top of this Stack * * @param first The Object to push */ public void push(Object first) { Node temp; temp = new Node(); temp.value = first; temp.next = top; top = temp; } }
1 | . | . |
1 | 2 | . |
/** * A Queue (of Object objects) * * This implementation uses contiguous memory * * @version 1.0 * @author Prof. David Bernstein, James Madison University */ public class Queue { private int back; private Object[] contents; public static final int CAPACITY = 100; /** * Construct a new (empty) Queue */ public Queue() { back = -1; contents = new Object[CAPACITY]; } /** * Pop an Object off of the front of this Queue * * @return The Object at the front of this Queue */ public Object pop() { int i; Object value; if (back != -1) { value = contents[0]; // Shuffle for (i=0; i < back; i++) { contents[i] = contents[i+1]; } back = back - 1; } else { value = null; } return value; } /** * Push an Object onto the back of this Queue * * @param last The Object to push */ public void push(Object last) { if (back < CAPACITY-1) { back = back + 1; contents[back] = last; } } }
Queue
/** * A Queue (of Object objects) * * This implementation uses linked memory * * @author Prof. David Bernstein, James Madison University * @version 1.0 */ public class Queue { private int size; private Node back, front; /** * Construct a new (empty) Queue */ public Queue() { front = null; size = 0; } /** * Pop an Object off of the front of this Queue * * @return The Object at the front of this Queue */ public Object pop() { Object value; if (front != null) { value = front.value; front = front.next; size--; } else { value = null; } return value; } /** * Push an Object onto the back of this Queue * * @param last The Object to push */ public void push(Object last) { Node temp; temp = new Node(); temp.value = last; temp.next = null; size++; if (front == null) { front = temp; } else { back.next = temp; } back = temp; } /** * Return the number of elements currently * in this Queue */ public int size() { return size; } }