Deques & Stack Algorithms

The ListDeque Application

The examples in this and the two previous documents all part of the Java Application ListDeque. Download the source archive ListDeque.zip and install it as a Java Application with Existing Sources. See the Using NetBeans document for details.

Like others, the ListDeque project has multiple Main Classes intended to illustrate various independent features. The simplest way to run the various classes is to right-click the file and select Run File either in the file itself or from the listing in the Projects window.

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
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 Programs

Start by observing and running the main class demo.ADequeDemo1.
demo.ADequeDemo1  

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 == data.length - 1) ? 0 : i+1; }
private int dec(int i) { return (i == 0) ? data.length - 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)

We start, as usual, with an adapter class:
adapter.DequeAdapter  
From this basis, we create our user-defined class:
util.ADeque  

Test programs

Add the import statement:
import adeque.ADeque;
Then replace the ArrayDeque or LinkedList implementations in ADequeDemo1 as follows:
//    Deque<String> stack = new ArrayDeque<>();
//    Queue<String> queue = new ArrayDeque<>();
//    Deque<String> deque = new ArrayDeque<>();
 
//    Deque<String> stack = new LinkedList<>();
//    Queue<String> queue = new LinkedList<>();
//    Deque<String> deque = new <>();
 
    Deque<String> stack = new ADeque<>();
    Queue<String> queue = new ADeque<>();
    Deque<String> deque = new ADeque<>();
A second test program, ADequeDemo2, is illustrated by the following code. It uses a non-standard member function, info, which reveals information about the internal variables.
demo.ADequeDemo2  

Stack Algorithms

To say that an algorithm is "stack-based" means that it uses 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. Using an ArrayDeque:
    Deque<E> stack = new ArrayDeque<>();
    Use the pre-existing operations: push, pop, element.
  2. A LinkedList in "deque mode":
    Deque<E> stack = new LinkedList<>();
    Use the pre-existing operations: push, pop, element.
  3. For either of the two previous implementations, you could use the "last" end:
    push    = addLast
    pop     = removeLast
    element = getLast
    
  4. An ArrayList using the "last" end:
    List<E> stack = new ArrayList<>();
  5. 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 "last" end to avoid linear-time operations!
    void push(E elt) { stack.add(elt); }
    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 / +

Practice Problem 11 Solutions

  1. Convert:   19 - ( 7 - 4 * 3 + 2 ) * ( 7 - 5 )
    token   stack           output
    -----   -----           ------
    19                      19
    -       [-]
    (       [(,-]
    7                       19 7
    -       [-,(,-]        
    4                       19 7 4
    *       [*,-,(,-]       
    3                       19 7 4 3
    +       [+,(,-]         19 7 4 3 * -
    2                       19 7 4 3 * - 2
    )       [-]             19 7 4 3 * - 2 +
    *       [*,-]
    (       [(,*,-] 
    7                       19 7 4 3 * - 2 + 7
    -       [-,(,*,-]
    5                       19 7 4 3 * - 2 + 7 5
    )       [*,-]           19 7 4 3 * - 2 + 7 5 -
    END     []              19 7 4 3 * - 2 + 7 5 - * -
    
    Evaluate:   19 7 4 3 * - 2 + 7 5 - * -
    token           stack
    -----           -----
    19, 7, 4, 3     [3, 4, 7, 19]
    *               [12, 7, 19]
    -               [-5, 19]
    2               [2, -5, 19]
    +               [-3, 19]
    7, 5            [5, 7, -3, 19]
    -               [2, -3, 19]
    *               [-6, 19]
    -               [25]
    END             []           => 25
    
    
  2. Convert:   3 - 7 * 15 / ( 2 + 3 )
    token   stack           output
    -----   -----           ------
    3 	[]		3 
    - 	[-]		 
    7 	[-]		3 7 
    * 	[*, -]
    15 	[*, -]		3 7 15 
    / 	[/, -]		3 7 15 * 
    ( 	[(, /, -]
    2 	[(, /, -]	3 7 15 * 2 
    + 	[+, (, /, -]
    3 	[+, (, /, -]
    ) 	[/, -]		3 7 15 * 2 3 + 
    END     []		3 7 15 * 2 3 + / - 
    
    
    
  3. Convert:   17 - ( 22 - ( 11 - 8 + 2 ) )
    token   stack              output
    -----   -----              ------
            []
    17                         17
    -       [-]
    (       [(, -]       
    22                         17 22
    -       [-, (, -]
    (       [(, -, (, -]
    11                         17 22 11
    -       [-, (, -, (, -]
    8                          17 22 11 8
    +       [+, (, -, (, -]    17 22 11 8 -
    2                          17 22 11 8 - 2
    )       [-, (, -]          17 22 11 8 - 2 +
    )       [-]                17 22 11 8 - 2 + -
    END     []                 17 22 11 8 - 2 + - -
    


© Robert M. Kline