What do you mean, "Not a symbol because it is abstract"? Any type can be
used for reference, including abstract classes and interfaces. This would
be partial code for what I think you want to do:

LinkedList<Symbol> stack = new LinkedList<Symbol>();
Queue<Symbol> queue = new LinkedList<Symbol>();
// ... Fill queue ...
while (!queue.isEmpty()) {
   Symbol head = queue.remove();
   if (head instanceof Operand) {
       stack.addLast(head);
   } else if (head instanceof Function) {
       // ... manipulate stack, etc.
   }
}

   There's no hard and fast rule, but as a rule of thumb, in this
situation you would use the least general type which is a supertype of all
the possible types you might get from your FIFO queue.

   The issue is that you will probably want to do something with each
element you take out of the queue. Usually, to "do something" involves
invoking a method. Which means the method you want to invoke must be part
of the type of the reference (or you could use casting, but that gets
messy).

   So say if you wanted to call the .doSomething() method on each
element, the type of the reference would need to be such that the
.doSomething() method is defined on that type. If the .doSomething()
method is defined in Symbol, then use Symbol as the type of the reference.
If the method is defined in Evaluate, then use Evaluate. If it's defined
in both, then it doesn't matter too much which one you use.

   - Oliver

 I have not fully understood your design, maybe I read not
 careful enough.

 I am also writing something like this, but have not yet
 published the full code. At least, I can try to quote relevant
 parts of the code here.

 Since I have not looked at this code for several month, it
 looks strange to me, too, but at least i already have written
 some documentation earlier.

 I am working with two stacks: on operator stack and one
 value stack (the »designation stack«). Operators and Values
 from the source code are considered to be »Tokens«. And
 a token is expected to know how to »enroll« itself to the
 stacks. This is what happens when parsing the source code
 to an internal representation.

 The interface »Token«:

interface Token extends de.dclj.ram.notation.programming.Designation
{ /** Enroll this token to the parser.
 Every token knows how to enroll itself to the parser.
 The stacks might be somewhat reduced, and
 then the token might push itself on one of the stacks.
 @param operatorStack the operator stack to be used for enrolling
 @param designationStack the designation stack to be used for enrolling */
 public void enroll
 ( final PlacementHint placementHint,
   final OperatorStack operatorStack,
   final DesignationStack designationStack );
 /** Whether this token is a Prefix context.
   +1 means that the next operator must be prefix.
   This is the case:
   At the start of a full expression.
   After opening parentheses (like, for example, »(«, »[«, »{«).
   After prefix or infix operators (like, for example, »+«, »*«, »/«, »-«, »,«, »;«)
   After prefixed function symbols (like, for example, »SIN«, »LOG«)
   0 means that the next operator must be infix.
   This is the case:
   After a numeral (like, for example, »0«)
   After a closing parentheses (like, for example »)«, »]«, »}«) */
 public boolean isPrefixContext(); }

 When the token is an operator, it usually is enrolled as follows.

 The method »acceptOperator«:

/** An operator is accepted by a stack pair given a placement hint.
The operator is pushed on the operator stack.
Possibly the stacks will be reduced before this happens
(depending on the priority of the given operators).
@param operatorToken an operator to be accepted
@param placementHint an instance of OperatorMustBePrefixPlacementHint if this operator
token appears in a context where a prefix operator is expected
@param operatorStack a stack of operators
@param designationStack a stack of designations */
public static void acceptOperator
( final OperatorToken operatorToken,
 final PlacementHint placementHint,
 final OperatorStack operatorStack,
 final DesignationStack designationStack )
{ int rightPriority;
 if( placementHint instanceof OperatorMustBePrefixPlacementHint )
 { rightPriority = getOperatorRightPriorityInPrefixContext( operatorToken ); }
 else
 { rightPriority = getOperatorRightPriorityInInfixContext( operatorToken ); }
 while( isReducible( operatorStack, rightPriority ))
 { OperatorToken operator = operatorStack.pop();
   operator.reduce( placementHint, operatorStack, designationStack ); }
 operatorStack.accept( operatorToken ); }

 This takes care of the fact that an operator character, like
 »-« might denote both a prefix operator and an infix operator.
 Therefore, context is used to figure out which to assume and
 then the appropriate priority is retrieved.

 The above while loops reduces the stack as long as indicated
 by the priority of the operators seen. Eventually, the operator
 then is pushed onto the operator stack by the final »accept«.

 A value, like a literal, is just pushed onto the operand stack:

 The methode »acceptLiteral«:

public static void acceptLiteral
( final LiteralToken literalToken,
 final PlacementHint placementHint,
 final OperatorStack operatorStack,
 final DesignationStack designationStack )
{ designationStack.accept( literalToken.value() ); }

 Some parameters are not used above, but given for consistency
 with the »acceptOperator« call.

 So, back to the »reduce« operation: Every operator token knows
 how to reduce itself to a designation of its operation (this
 is not the evaluation yet, but an internal representation of
 this application of this oprator including its operands):

 The interface »OperatorToken«:

/** An operator token. There will be several
kinds of operator tokens. */
interface OperatorToken extends Token
{ /** Reduces the stack by this operator token.
 It is assume that this token already has been removed
 from the operator stack. Now it will usually pop some
 designations from the designation stack, possibly evaluate
 some of them (»strict« arguments) and then build a
 reduction result and push it onto the designation stack.
 For example, »+« might take two designations, which might
 might be the number 2 and the number 3 and then push
 the number 5 on the designation stack.
 @param placementHint A placement hint indicates whether
 the reduction takes place in a context where certain
 types of operators are required or permissible
 see {@link PlacementHint}.
 */
 /* todoc: @params */
 public void reduce
 ( final PlacementHint placementHint,
   final OperatorStack operatorStack,
   final DesignationStack designationStack ); }

 An example is the »PRINT« keyword in a BASIC-like language.

 It takes its operand from the designation stack and
 pushes a new »print designation« on the designation stack.

 The method »reduce«:

public void reduce
( final PlacementHint placementHint,
 final OperatorStack operatorStack,
 final DesignationStack designationStack )
{ designationStack.accept
 ( new PrintDesignation
   ( designationStack.popOrProduceNull() )); }

 The »print designation« is an object representing the
 print operation including its argument.

 It has an »eval« operation, that can be called to
 actually do the printing:

 The method »eval«:

public de.dclj.ram.notation.programming.EvaluableDesignation
eval( de.dclj.ram.notation.programming.World world )
{ Value value =( Value )Evaluator.completeEvaluation
 ( argumentDesignation, world );
 if( value instanceof NumericValue )
 { java.lang.System.out.println
   ( value.getPrintRepresentation() + " " ); }
 else
 { java.lang.System.out.println
   ( value.getPrintRepresentation() ); }
 return new Ok(); }

 The result is a new designation indicating the success
 of the operation.

 In my implementation everything is considered to be built
 of operators and operands. Each operator is defined by
 two classes. The intention is to make extensions to the
 language easy by requiring them just to add two new classes
 per operator.

 For example, »if ... then ...« also would be considered to
 be an operator.

 For example, the operator »-« is being specified as follows.

 The class pair for the operator »-«:

/** A minus-operator token represents the operator "-". */
class MinusOperatorToken
extends DefaultInfixOperatorToken
implements PrefixOrInfixOperatorToken
{ public java.lang.String fixtext(){ return "-"; }
 public int infixLeftPriority(){ return 640; }
 public int infixRightPriority(){ return 639; }
 public int prefixLeftPriority(){ return 680; }
 public int prefixRightPriority(){ return 999 /* 681 */; }
 public boolean isPrefix(){ return this.isPrefix; }
 public void setPrefix(){ this.isPrefix = true; }
 public void reduce
 ( final PlacementHint placementHint,
   final OperatorStack operatorStack,
   final DesignationStack designationStack )
 { de.dclj.ram.notation.programming.EvaluableDesignation
   rightDesignation = designationStack.pop();
   if( placementHint instanceof OperatorMustBePrefixPlacementHint ||
     this.isPrefix() )
   { designationStack.accept
     ( new DifferenceDesignation
       ( new NumericValue( "0" ), rightDesignation )); }
   else
   { de.dclj.ram.notation.programming.EvaluableDesignation
     leftDesignation = designationStack.pop();
     designationStack.accept
     ( new DifferenceDesignation
       ( leftDesignation, rightDesignation )); }}
 public MinusOperatorToken newInstance(){ return new MinusOperatorToken(); }
 private boolean isPrefix = false;
 public java.lang.String toString()
 { return this.getClass().getName(); }}

/** A difference designation designates the difference of two designations. */
class DifferenceDesignation
implements de.dclj.ram.notation.programming.EvaluableDesignation
{ final de.dclj.ram.notation.programming.EvaluableDesignation leftDesignation;
 final de.dclj.ram.notation.programming.EvaluableDesignation rightDesignation;
 public DifferenceDesignation
 ( final de.dclj.ram.notation.programming.EvaluableDesignation leftDesignation,
   final de.dclj.ram.notation.programming.EvaluableDesignation rightDesignation )
 { this.leftDesignation = leftDesignation;
   this.rightDesignation = rightDesignation; }
 public de.dclj.ram.notation.programming.EvaluableDesignation
 eval( de.dclj.ram.notation.programming.World world )
 { final java.lang.Object l =
   Evaluator.completeEvaluation( leftDesignation, world );
   final java.lang.Object r =
   Evaluator.completeEvaluation( rightDesignation, world );
   final java.math.BigDecimal left =
   new java.math.BigDecimal((( NumericValue )l ).asDecimal(),
     (( BasicWorld )world ).config().getMathContext() );
   final java.math.BigDecimal right =
   new java.math.BigDecimal((( NumericValue )r ).asDecimal(),
     (( BasicWorld )world ).config().getMathContext() );
   final java.math.BigDecimal difference = left.subtract
   ( right, (( BasicWorld )world ).config().getMathContext() );
   return new NumericValue( difference.toString() ); }
 public de.dclj.ram.notation.programming.EvaluableDesignation
 continue_( final de.dclj.ram.notation.programming.World world )
 { return null; }
 public java.lang.String toString()
 { return "DIFFERENCE-DESIGNATION( \"" +
   leftDesignation + "\",\"" + rightDesignation + "\")" ; }}