Tuesday, 2 July 2013

Stacks, Queues, and Deques

Stacks
  • A stack is a container of objects that are inserted and removed according to the last-in, first-out (LIFO) principle.
  • Objects can be inserted at any time, but only the last (i.e., the most recently inserted) object can be removed.
  • Inserting an item is known as "pushing" onto the stack. "Popping" off the stack is synonymous with removing an item.
  • A PEZâ dispenser is an analogy:
 Lafore Stack Applet


  The Stack Abstract Data Type
  • A stack is an abstract data type (ADT) that supports two main methods:
    • push(o): Inserts object o onto top of stack.

    • Input: Object; Output: none
    • pop(): Removes the top object from the stack and returns it; if stack is empty an error occurs.

    • Input: none; Output: Object
  • The following support methods should also be defined:
    • size(): Returns the number of objects in stack.

    • Input: none; Output: integer
    • isEmpty(): Return a boolean indicating if stack is empty.

    • Input: none; Output: boolean
    • top(): Return the top object of the stack, without removing it. If the stack is empty, an error occurs.

    • Input: none; Output: Object




A Stack Interface in Java
  • While the stack data structure is a "built-in" class of the JDK java.util package, it is possible and sometimes preferable to define your own interface such as this one:
    public interface Stack {
    // accessor methodspublic int size(); //# return the number of elements stored in the stack
    public boolean isEmpty(); //# test whether the stack is empty
    public Object top() //# return the top elemet
                        throws StackEmptyException; //# thrown if called on an empty stack
    // update methods
    public void push (Object element); //# insert an element onto the stack
    public Object pop() //# return and remove the top element of the stack
                        throws StackEmptyException; //# thrown if called on an empty stack
    }
 Interface Stack
 Class StackEmptyException

An Array-Based Stack
  • Create a stack using an array by specifying a maximum size N for our stack, e.g., N = 1000.
  • The stack consists of an N-element array S and an integer variable t, the index of the top element in array S.
  • Array indices start at 0, so we initialize t to –1.
  • Pseudo-code

Algorithm size(): return t+1
Algorithm isEmpty():
return (t < 0)
Algorithm top():
if isEmpty() then throw a StackEmptyException return S[t]


An Array-Based Stack (contd.)
  • Pseudo-Code (contd.)

Algorithm push(o): if size() = N then throw a StackFullException t <-- t + 1
S[t] <-- o

Algorithm pop():
if isEmpty() then throw a StackEmptyException e <-- S[t]
S[t] <-- null
t <-- t – 1
return e

  • Each of the above methods runs in constant time (O(1)).
  • The array implementation is simple and efficient.
  • There is an upper bound N on the size of the array-based stack. This arbitrary value N may be too small for a given application or it may be too large and a waste of memory.

Array-Based Stack: a Java Implementation
public class ArrayStack implements Stack {
// Implementation of the Stack interface using an array.
public static final int CAPACITY = 1000; //# default capacity of the stack private int capacity; // maximum capacity of the stack.
private Object S[]; // S holds the elements of the stack
private int top = -1; // the top element of the stack.
public ArrayStack() { //# Initialize the stack with default capacity
  this(CAPACITY);
}
public ArrayStack(int cap) { //# Initialize the stack with given capacity
  capacity = cap;
  S = new Object[capacity];
}
 
public int size() { //# Return the current stack size
  return (top + 1);
}

Array-Based Stack in Java (contd.)
publicboolean isEmpty() { //# Return true iff the stack is empty
  return (top < 0);
} publicvoid push(Object obj) { //# Push a new object on the stack
  if (size() == capacity)
      throw new StackFullException("Stack overflow.");
  S[++top] = obj;
}
public Object top() //# Return the top stack element
                                throws StackEmptyException {
  if (isEmpty())
      throw new StackEmptyException("Stack is empty.");
  return S[top];
}

Array-Based Stack in Java (contd.)
public Object pop() //# Pop off the stack element
                    throws StackEmptyException {
Object elem;
if (isEmpty())
    throw new StackEmptyException("Stack is Empty.");
elem = S[top];
S[top--] = null; //# Dereference S[top] and decrement top
return elem;
}
}  Class StackFullException
 Class java.lang.RuntimeException
 Class java.util.Stack
 Class java.util.EmptyStackException
 Class java.util.Vector

Casting with a Generic Stack
  • We can store generic objects in ArrayStack (and other data-structure classes) because every Java class is a subclass of the Object class.
  • When retrieving from an ADT, however, it is often necessary to cast the object back to its original type.
  • A Java code example:

public static Integer[] reverse(Integer[] a)
{
    ArrayStack S = new ArrayStack(a.length);
    Integer[] b = new Integer[a.length];
    for(int i = 0; i < a.length; i++)
        S.push(a[i]);
    for(int i = 0; i < a.length; i++)
        b[i] = (Integer)(S.pop());
    return b;
}


Stacks in the Java Virtual Machine
  • Each process running in a Java program has its own Java method stack.
  • Each time a method is called, it is pushed onto the stack. A frame in the stack stores information relevant to running and suspended methods (i.e., local variables, actual parameters, return values, etc.)
  • The choice of a stack for this operation allows Java to do several useful things:
    • Perform recursive method calls. Conceptually, as regards the Java method stack, there is no difference between a recursive call and a "regular" call.
    • Print stack traces so that users can locate an error.

Java Method Stack


Queues
  • A queue differs from a stack in that its insertion and removal routines follow the first-in, first out (FIFO) principle.
  • Elements may be inserted at any time, but only the element which has been in the queue the longest may be removed.
  • Elements are inserted at the rear (enqueued) and removed from the front (dequeued).
 Lafore Queue Applet  Interface Queue
 Class QueueEmptyException

The Queue Abstract Data Type
  • The Queue ADT supports two fundamental methods:

- enqueue(o)
Insert o at the rear of the queue.
Input: Object; Output: none

- dequeue()
Remove the object from the front of the queue and return it; an error occurs if the queue is empty.
Input: none; Output: Object
  • These support methods should also be defined:

- size():
Return the number of objects in the queue.
Input: none; Output: integer

- isEmpty():
Return a boolean value that indicates whether the queue is empty.
Input: none; Output: boolean

- front():
Return but do not remove the front element in the queue; an error occurs if the queue is empty.
Input: none; Output: Object

An Array-Based Queue
  • A maximum size N is specified, e.g., N = 1000.
  • The queue consists of an N-element array Q and two integer variables:
    • f, index of the front element, and
    • r, index of the element after the rear one, i.e., the insertion element.
  • "normal" array configuration
    As we enqueue elements, we increment r. As we dequeue elements, we increment f. But what do we do when r > N – 1?
    We will soon run out of array. One way to remedy this problem is to require that f = 0. Let’s consider this case.
     
     

    An Array-Based Queue (2)
enqueue operation, enqueue("I"), is O(1)
 
 

dequeue operation, myString = (String)dequeue(), is an O(n) operation.
Being that this solution is so costly, it is ineffective. We need to consider an alternative approach.

An Array-Based Queue (3)
Use a circular array to avoid O(n) operations in dequeueing.
Note that r < f is a possibility.
Q[f] = element at front of queue
Q[r-1] = element at rear of queue
  • Empty queue: f = r
  • Full queue: f = (r + 1) mod N
  • The modulo operator is the remainder of an integer division: .  In Java: use %
  • Incrementing f during a dequeue operation:
  • Incrementing r during an enqueue operation:

Pseudo-Code for an Array-Based Queue
Algorithm size():                                        O(1)
    return (Nf + r) mod N
Algorithm isEmpty():                                 O(1)
    return (f = r)
Algorithm front():                                       O(1)
    if isEmpty() then
        throw a QueueEmptyException
    returnQ[f]
Algorithm dequeue():                                 O(1)
    if isEmpty() then
        throw a QueueEmptyException
    temp <-- Q[f]
    Q[f] <-- null
    f <-- (f + 1) mod N
    returntemp
Algorithm enqueue(o):                              O(1)
    if size() = N – 1 then
        throw aQueueFullException
    Q[r] <-- o
    r <-- (r + 1) mod N
 Class QueueFullException

Implementing a Queue with a Singly Linked List
  • The nodes are connected in a chain by links.
  • Note the absence of a sentinel node. Not necessary if the allowable operations are restricted.
  • The head of the list is the front of the queue and the tail of the list is the rear of the queue.
  • Why not the opposite?

Dequeuing
Removing at the head
  • Advance head reference

 

Enqueuing
Inserting at the Tail
  • Create a new node.
  • Chain it and move the tail reference.

Double-Ended Queues
  • A double-ended queue, or deque, supports insertion and deletion from both the front and back.
  • The Deque ADT

- insertFirst(e):
Insert e at the front of the deque. Input: Object; Output: none

- insertLast(e):
Insert e at the end of the deque. Input: Object; Output: none

- removeFirst():
Removes and returns the first element. Input: none; Output: Object

- removeLast():
Removes and returns the last element. Input: none; Output: Object
  • Additionally supported methods include:
    • first()
    • last()
    • size()
    • isEmpty()
 Interface Deque
 Class DequeEmptyException

Implementing Stacks and Queues with Deques
  • Stacks with Deques (e.g., Class DequeStack):
Stack Method
Deque Implementation
size() size()
isEmpty() isEmpty()
top() last()
push(e) insertLast(e)
pop() removeLast()
  • Queues with Deques (e.g., Class DequeQueue)
Queue Method
Deque Implementation
size() size()
isEmpty() isEmpty()
front() first()
enqueue(e) insertLast(e)
dequeue() removeFirst()

The Adapter Pattern
  • Using a deque to implement a stack or queue is an example of the adapter pattern. Adapter patterns implement a class by using methods of another class.
  • In general, adapter classes specialize general classes.
  • Two such applications:
    • Specialize a more general ADT class.

Example: Implementing a stack via a deque.
    • Specialize the types of objects used by a general class.

Example: Defining an IntegerArrayStack class that adapts ArrayStack to only store integers.

Implementing Deques with Doubly Linked Lists
  • Recall that deletions at the tail of a singly linked list cannot be done in constant time.
  • To implement a deque, we use a doubly linked list with special header and trailer sentinel nodes.
  • A node of a doubly linked list has a next and a prev link. It supports the following methods:
    • setElement(Object e)
    • getElement()
    • setNext(Object newNext)
    • setPrev(Object newPrev)
    • getNext()
    • getPrev()
  • When the Deque ADT is implemented via a doubly linked list, all methods have constant (i.e., O(1)) time.
 Class DLNode
 DLNode.java
 Class MyDeque

Implementing Deques with Doubly Linked Lists (cont.)
  • When implementing doubly linked lists, we add two special nodes to the ends of the lists: the header and trailer nodes.
    • The header goes before the first list element. It has a valid next reference but a null prev reference.
    • The trailer node goes after the last element. It has a valid prev reference but a null next reference.
  • The header and trailer nodes are sentinel or "dummy" nodes because they do not store elements.

Implementing Deques with Doubly Linked Lists (cont.)
  • Here’s a visualization of the removeLast method:

Implementing Deques with Doubly Linked Lists (cont.)
  • Let’s look at the removeLast() method of class MyDeque.
public class MyDeque implements Deque {
    DLNode header, trailer; // sentinels
    int size; // number of elements
    ::::::::::     public Object removeFirst() throws DequeEmptyException {
       if (isEmpty())
           throw new DequeEmptyException(
                          "Illegal removal request.");
        DLNode first = header.getNext();
        Object o = first.getElement();
        DLNode second = first.getNext();
        header.setNext(second);
        second.setPrev(header);
        size--;
        return o;
    }
}
 
    :::::::::::
}