Deques & Stack Algorithms

ArrayDeque operations

The ArrayDeque is the array-based implementation. of the Deque interface. Perhaps its key feature is the ability to execute the addFirst and removeFirst operations in constant time, which is something the ArrayList cannot do.

Both LinkedList and ArrayDeque are common Deque implementations. As noted in the Linked Lists document, a Deque focuses on list access at the ends. The ArrayDeque, unlike the LinkedList, does not implement the List interface, and so we never think about using it for positional access.

Common subsets of the intended operations are these:
stack mode, provided by the Deque interface:
boolean push(e),  E pop(),  E element(),  boolean isEmpty()
queue mode, provided by both the Queue and Deque interfaces:
boolean add(e),  E remove(),  E element(),  boolean isEmpty()
The difference is that in stack mode, the push and pop operations do the element addition/removal to the same end, whereas in queue mode the add and remove operations affect opposite ends. The function getFirst is an alternative for element, except that it is not, per se, defined by the Queue interface.

In a valid Deque implementation, there is no difference between the "first" and "last" ends of the list, but Java makes these choices:
stack: operations access the first end
queue: add to the last end, remove from the first end

COMING SOON

Here is a visual depiction of the operations:
The Deque implementations (LinkedList and ArrayDeque) serve either for queue or stack usage. Java does have a Stack class but it is deprecated and should not be used. In the literature, the term LIFO (Last In First Out) is used to refer to the stack-mode access whereas FIFO (First In First Out) refers to queue-mode access. Also in the literature, top is often used as the name of the element retrieval operation. Other languages, like Php, Perl and Python use the "last" end for stack operations (Python prefers "append" to "push"). The Queue interface also supports the PriorityQueue implementation class, which is not a FIFO queue like the LinkedList and ArrayDeque classes.

Demo program

Create a NetBeans project ADequeDemo. Assuming you use the default setup of NetBeans, the main class will be named ADequeDemo. Change the content to the following:
adequedemo.ADequeDemo  
This demo program illustrates two ArrayDeque objects, one in stack mode, the other in queue mode.

ArrayDeque Description

For an array to act like a Deque, the simplest idea would be for it to allow an arbitrary range of positive and negative indices. For example, suppose we start with an empty array of capacity 40 in which we do 30 addLast operations, getting:



0 30 40
After 5 removeLast and 3 addFirst operations, if negative indices were allowed:



-3 25 40
In order to create the effect of negative indices without actual negative indices, we make the array "form a circle" shifting the "virtual" indices -1, -2, ... into the array from above like this:




0 25 37 40
The negative indices are mapped to non-negative indices by "adding capacity", e.g.:
-1  →  -1 + 40 = 39
-2  →  -2 + 40 = 38
-3  →  -3 + 40 = 37
In particular, we write our own increment and decrement operations on an index in order to create the "wrap-around" effect:
private int inc(int i) { return (i == capacity - 1) ? 0 : i+1; }
private int dec(int i) { return (i == 0) ? capacity - 1 : i-1; }
We also need two markers to identify the start and end of the content:
low: array position of data for the getFirst,addFirst,removeFirst operations
high: array position after data for getLast,addLast,removeLast operations
In our above example we would have the values:
low  = 37
high = 25
size = 28
The best way to conceive of how an ArrayDeque works is by visualizing it as a circle created by connecting the ends of the array.

In a non-empty ArrayDeque, the content is specified by elements in positions low (inclusive) to high (exclusive) going clockwise.

Full and empty

The empty and full states of the ArrayDeque are characterized by having low and high equal. We use the size parameter to differentiate between them:

Increasing capacity

As with the ArrayList, we must deal with enlarging capacity when a new element is added to a full ArrayDeque, i.e., when size == capacity. The low index could conceivably be positioned anywhere within the new array, and so the easiest thing to do is to copy the data from positions
low, low+1, ..., high-1   (using "mod capacity" arithmetic)
into positions 0 to capacity-1 in the new array and then reset
low = 0
high = (the old) capacity

Alternative (textbook) implementation

In our implementation the high index always points to the next unused position for an addLast operation. This makes it possible to express an empty deque (or queue) with low == high. Our textbook (as well as other authors) use a scheme whereby the index positions always point at used positions. The author refers to these positions as front and back. The correspondence to my position pointers are roughly this:
front = low
back  = high - 1
This the author's initial empty deque with capacity 40 would use:
front = 0
back  = 39  (i.e., -1 in "circular" terms)
In general, the author's scheme would express both empty and full as either:
inc(back) == front    or     back == dec(front)
In my opinion, this form is more complicated than the inclusive/exclusive scheme above. Furthermore, the inclusive/exclusive index range is more consistent with the Java API.

ArrayDeque implementation (ADeque)

Create the Java (adapter) class:
Class Name: DequeAdapter
package:    adeque
Then insert the following content
adeque.DequeAdapter  
Create the Java implementation class:
Class Name: ADeque
package:    adeque
Then insert the following content:
adeque.ADeque  

Test programs

Add the import statement:
import adeque.ADeque;
Then replace the ArrayDeque implementations in "main1" as follows:
//Deque<String> stack = new ArrayDeque<>();
//Queue<String> queue = new ArrayDeque<>();
 
Deque<String> stack = new ADeque<>();
Queue<String> queue = new ADeque<>();
A second test program, main2, is illustrated by the following code. It uses a non-standard member function, info, which is intended to reveal information about the internal variables. Change main to call main2 instead of main1.
  public static void main2(String[] args) {
    Deque<Integer> D = new ADeque<>();
    for (int i = 1; i <= 5; ++i) {
      D.addFirst(i);
    }
    for (int i = 6; i <= 10; ++i) {
      D.addLast(i);
    }
    System.out.println(D);
    System.out.println( "--> info: " + ((ADeque<Integer>)D).info() + "\n" );
 
    D.addLast(11);
    System.out.println(D);
    System.out.println( "--> info: " + ((ADeque<Integer>)D).info() + "\n" );
 
    D.addFirst(12);
    D.addFirst(13);
    D.addLast(14);
    System.out.println(D);
    System.out.println( "--> info: " + ((ADeque<Integer>)D).info() + "\n" );
  }
select

Stack Algorithms

To say that they are "stack-based" means that the algorithms use a list with this restricted set of operations: The push, pop and element operations must all access the same end of a list, either first or last. Java uses the first end for these operations. The other key point is that the operations must be constant-time, O(1). These are the viable options for a stack in Java:
  1. An ArrayDeque:
    Deque<E> stack = new ArrayDeque<>();
    select
    Use the pre-existing operations: push, pop, element.
  2. A LinkedList in "deque mode":
    Deque<E> stack = new LinkedList<>();
    select
    Use the pre-existing operations: push, pop, element.
  3. An ArrayList using the "last" end:
    List<E> stack = new ArrayList<>();
    select
    In this case the standard operations are not available because ArrayList does not implement the Deque interface. Furthermore, we cannot use either end of the list; instead we must use the "wrong" end to avoid linear-time operations!
    void push(E e) { stack.add(e); }
    E pop() { return stack.remove(stack.size()-1); }
    E element() { return stack.get(stack.size()-1); }
    

Arithmetic Expression Evaluation

This section illustrates two common stack-based algorithms for arithmetic expression manipulation:
  1. evaluating an arithmetic expression written in postfix form.
  2. converting an infix expression to postfix form.
Converting an infix expression (the usual form) to postfix means to write the expression so that the operators come after the operands. There are no parentheses in such expressions. For simplicity we'll look at only the standard binary operators:
+, –, *, /

Postfix expression evaluation

In the postfix expression evaluation algorithm, the stack contains only numbers. Here is a sketch of the algorithm:
for each expression token:
  if the token is a number:
    push it
  else (the token is an operator, OP):
    second = pop();
    first = pop();
    compute: result = first OP second
    push the result on the stack

when there are no more tokens, pop the answer off the stack
The arithmetic expressions 4 - ( 2 - 3 ) and 4 - 2 - 3 have these respective postfix expressions and evaluations:
4 2 3 - -

token    stack
-----    -----
         []
  4      [4]
  2      [2, 4]
  3      [3, 2, 4]
  -      [-1, 4]
  -      [5]
 END     []    ⇒ answer = 5
4 2 - 3 -

token    stack
-----    -----
         []
  4      [4]
  2      [2, 4]
  -      [2]
  3      [3, 2]
  -      [-1]
 END     []    ⇒ answer = -1
The arithmetic expression ( 7 + 3 ) * ( 11 – 4 * 2 ) has the following postfix form and evaluation:
7 3 + 11 4 2 * – *

token    stack
-----    -----
         []
  7      [7]
  3      [3, 7]
  +      [10]
  11     [11, 10]
  4      [4, 11, 10]
  2      [2, 4, 11, 10]
  *      [8, 11, 10]
  –      [3, 10]
  *      [30]
 END     []    ⇒ answer = 30

Infix to Postfix conversion

The infix-to-postfix conversion algorithm is more complicated. It is extremely simple if all operators have the same precedence (such as "+" and "") and there are no parentheses. Adding parentheses and operators of differing precedence introduces complications.

The goal of the algorithm is to construct an output string which is the equivalent postfix form of a given infix expression. The stack will hold operators and left parentheses. One key observation is that the numbers stay in the same order as in the infix expression.

Here is a sketch of the algorithm:
for each expression token:
  if the token is a number:
    add it to output
  else if the token is a left paren:
    push it
  else if the token is a right paren:
    pop and add to output all tokens on stack up to left paren
    pop the left paren, but don't add to output
  else if the token is an operator:
    if stack is empty or the top is a left paren:
       push it
    else if the stack top is a lower precedence operator:
       push it
    else
       pop and add to output all operators of higher or equal precedence 
       push it

when there are no more tokens,
  pop and add to output all remaining operators on stack
Observe in the way numbers are handled that the numbers appear in the same order as in the infix expression. Here are some examples:
7 - 3 + 5 - 2

token   stack     output
-----   -----     ------
        []
  7               7
  -     [-]
  3               7 3
  +     [+]       7 3 -
  5               7 3 - 5
  -     [-]       7 3 - 5 +
  2               7 3 - 5 + 2
 END    []        7 3 - 5 + 2 -
7 + ( 3 + 5 - 4 ) - 2

token    stack        output
-----    -----        ------
         []
  7                   7
  +      [+]
  (      [ (, +]
  3                   7 3
  +      [+, (, +]
  5                   7 3 5
  -      [-, (, +]    7 3 5 +
  4                   7 3 5 + 4
  )      [+]          7 3 5 + 4 -
  -      [-]          7 3 5 + 4 - +
  2                   7 3 5 + 4 - + 2
 END     []           7 3 5 + 4 - + 2 -
7 + 10 * 6 / 4

token   stack         output
-----   -----         ------
        []        
  7                   7
  +     [+]
  10                  7 10
  *     [*, +]
  6                   7 10 6
  /     [/, +]        7 10 6 *
  4                   7 10 6 * 4
 END    []            7 10 6 * 4 / +


© Robert M. Kline