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 rightclick 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 arraybased 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:
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.
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()
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:
queue: add to the last end, remove from the first end
Demo Programs
Start by observing and running the main class 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 
3  25  40 
0  25  37  40 
1 ⇾ 1 + 40 = 39 2 ⇾ 2 + 40 = 38 3 ⇾ 3 + 40 = 37In particular, we write our own increment and decrement operations on an index in order to create the "wraparound" 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 : i1; }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:
high: array position after data for getLast,addLast,removeLast operations
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 nonempty 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: empty: size == 0 and low == high
 full: size == capacity and low == high
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 positionslow, low+1, ..., high1 (using "mod capacity" arithmetic)
into positions 0 to capacity1 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  1This 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:Test programs
Add the import statement:import adeque.ADeque;
// 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<>();
Stack Algorithms
To say that an algorithm is "stackbased" means that it uses a list with this restricted set of operations: boolean isEmpty()
 void push(E e)
 E pop()
 E element()

Using an ArrayDeque:
Deque<E> stack = new ArrayDeque<>();

A LinkedList in "deque mode":
Deque<E> stack = new LinkedList<>();

For either of the two previous implementations, you could use the "last" end:
push = addLast pop = removeLast element = getLast
 An ArrayList using the "last" end:
List<E> stack = new ArrayList<>();
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 lineartime 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 stackbased algorithms for arithmetic expression manipulation: evaluating an arithmetic expression written in postfix form.
 converting an infix expression to postfix form.
+, –, *, /
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 stackThe 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 = 1The 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 infixtopostfix 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 stackObserve 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 / +
Java Programs
These two programs are intended to be in the demo package. The Infix2Postfix program enters and processes an arithmetic expression (in standard infix form), generating an output of the arithmetic expression in postfix form. Operands are assumed to be unsigned nonnegative integers.Practice Problem 11 Solutions

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

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 + / 

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 +  