There are two NetBeans projects involved in this handout:
ADequeDemo: illustrates basic ArrayDeque operations and gives
an user-defined implementation
ExprEvaluation: illustrates an ArrayDeque
as a stack used to create algorithmic solutions
to two well-known problems:
evaluating an arithmetic expression in postfix form.
converting an infix expression to postfix form.
ArrayDeque operations
The ArrayDeque is the array-based implementation.
of the Deque interface. Perhaps its key feature is
the ability to execute addFirst and removeFirst
operations in constant time; this is something the
ArrayList does not 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:
boolean push(e),
E pop(),
E element()
queue mode:
boolean add(e),
E remove(),
E element()
The difference is that in stack mode adds and removes affect
the same end,
whereas in queue mode adds and removes affect opposite ends.
The function getFirst
is an alternative for element, except that
getFirst, per se, is not defined in the Queue
interface.
In a valid Deque implementation, there is no
effective 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
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, the operation top is often
used for the element retrieval.
Other languages, like Php, use the "last" end for stack operations.
Java has a Queue interface but no Stack interface.
The reason is that there is another important implementation
of the Queue called
the PriorityQueue which is a
non-FIFO queue with a complicated internal structure.
In contrast the Deque implementations (LinkedList and
ArrayDeque) serve for any stack usage.
Java actually does have a Stack class per se,
but the documentation
indicates that it is deprecated and a Deque
implementation should be
preferred.
Sample program
Create a NetBeans project ADequeDemo and
make the code below
the content of the Main class. This demo program
illustrates two ArrayDeque objects, one operating in stack mode,
the other in queue mode.
Then insert the following content
( click to show )
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,
the array would look like this, 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.:
We also need two markers to identify the start and end of the content:
low: array position of data for the "_first" operations
high: array position after data for "_last" operations
In our above example we would have the values:
low = 37
high = 25
size = 28
The empty and full states are characterized by:
empty: size == 0 and low == high
full: size == capacity and low == high
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 postions 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 our inclusive/exclusive
scheme whereby
low points to an "element" position and
high points to an "open" position.
Furthermore, this inclusive/exclusive style is more
consistent with the Java API in which "toIndex" points
one above the last "in use" index.
Increasing capacity
As with the ArrayList, we must deal with enlarging
capacity
when adding a new element to a full
ArrayDeque, i.e.,
when size == capacity.
Although low could conceivable be positioned anywhere within the new
array, the easiest thing to do is to set
low = 0
high = (the old) capacity
and copy the old data into the new array at positions 0
to high-1..
ArrayDeque implementation (ADeque)
Create a Java Class:
Class Name: ADeque
package: adeque
Then insert the following content
( click to show )
Test programs
Add the import statement:
import adeque.ADeque;
The "main1" program can be used.
Simply replace the ArrayDeque implementations
by ADeque implementations.
//Deque<String> stack = new ArrayDeque<String>();
//Deque<String> queue = new ArrayDeque<String>();
Deque<String> stack = new ADeque<String>();
Deque<String> queue = new ADeque<String>();
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<Integer>();
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" );
}
Stack Algorithms
To say that they are "stack-based" means that
the algorithms use a list with only these restricted stack-mode operations:
boolean isEmpty(): as expected
void push(E e): add to the first
E pop(): remove the first element
E element() (or, E getFirst()):
retrieve the value of the first element
The main thing we want is that these operations should be constant-time.
Java has a Stack class in its collections, but it is
deprecated. These are common options for a Stack:
An ArrayDeque:
Deque<E> stack = new ArrayDeque<E>();
Use the pre-existing operations: push, pop, element.
A LinkedList in "deque mode":
Deque<E> stack = new LinkedList<E>();
Use the pre-existing operations: push, pop, element.
An ArrayList using the "last" end:
List<E> stack = new ArrayList<E>();
Here we cannot use the standard operations. They do not exist
in "list mode," and even if they did, they would be at the wrong
end, making push and pop be linear-time operations!
void push(E e) { stack.add(stack.size(), e); }
E pop() { return stack.remove(stack.size()-1); }
E element() { return stack.get(stack.size()-1); }
Postfix Expression Algorithms
This section illustrates two common
stack-based algorithms for arithmetic expression manipulation:
evaluating an arithmetic expression in postfix form.
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:
+, –, *, /
One key observation which we'll see in the infix-to-postfix conversion
algorithm is that:
the numbers stay in the same order as in the infix expression
Postfix expression evaluation
In the postfix expression evaluation algorithm,
the stack contains only numbers.
Here is the simple idea:
for each expression token:
if the token is a number:
push it
else (the token is an operator, OP):
pop 2 numbers => first, second
compute the result: "second OP first"
push the result on the stack
when there are no more tokens, pop the answer off the stack
For example, the expression
"( 7 + 3 ) * ( 11 – 4 * 2 )" has the following
postfix form and evaluation:
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.
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 top is left paren:
push it
else if the stack top is a lower precedence operator:
push it
else
pop and add to output all lower precedence operators
push it
when there are no more tokens,
pop and add to output all tokens 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 xamples:
The stack-based algorithms implementations below use the
ArrayDeque object for the stack implementation. You could just
as well use LinkedList or our user-defined ADeque class.
Create a NetBeans project ExprEvaluation.
The program below should become the content of Main:
The program combines both algorithms, first converting from infix
to postfix, then evaluating the postfix.
The algorithm works for expressions with the usual binary operators
+, -,
*.
and /.
One source of complexity is parsing of the expression string into
tokens. We make the restriction that two distinct tokens cannot
be adjacent. Thus this is OK:
12 + 3
but this is not OK
12+3
The static member function separationOK uses a complex regular
expression to determine whether such separation exists.
Here is the code:
( click to show )