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 (N – f + 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;
    }
}
 
    :::::::::::
}