CSC 477/677 Priority Queue Unfulfilled Obligations
University of Nevada Las Vegas
Howard R. Hughes
College of Engineering
School of Computer Science
My Home Page
Computer Science 477/677
A Stack Contains Unfulfilled Obligations
Revised October 18, 2005
Under Construction
There are two ways to write an algorithm that uses a stack. One way is
to find the algorithm in a book, copy the code, and hope for the best.
This way requires no more knowledge of stacks than driving a car
requires knowledge of the theory of internal combustion engines.
Clearly, it is better to understand how a stack algorithm works.
To do this, remember the rule: The items on a stack represent
unfulfilled obligations.
This rule holds for all other priority queues as well, such as
queues and heaps.
A Stack Algorithm for Evaluating a Postfix Arithmetic Expression
A postfix arithmetic expression uses numbers
and operators for addition, subtraction, multiplication, division,
and negation. Subtraction and negation are represented by different
symbols. We describe an algorithm that reads a postfix arithmetic
expression and computes its value, using a stack. The stack holds only
numbers.
A Stack Algorithm for Evaluating an Infix Arithmetic Expression
An infix arithmetic expression uses numbers, parentheses,
and operators for addition, subtraction, multiplication, division,
and negation. But subtraction and negation are represented by the same
symbol, a minus sign. We describe an algorithm that reads an arithmetic
expression and computes its value, using a stack. The stack can hold
left parentheses, operator symbols, and numbers. We must use different
stack symbols for negation and subtraction.
A Stack Algorithm for Evaluating a Prefix Arithmetic Expression
A prefix arithmetic expression uses numbers,
and operators for addition, subtraction, multiplication, division,
and negation. Subtraction and negation are represented by different
symbols. We describe an algorithm that reads a prefix arithmetic
expression and computes its value, using a stack. The stack can hold
operator symbols and numbers.
Also we present a stack
algorithm, by Dijkstra, for converting an infix experession to an
postfix (reverse Polish) expression.
Recursion is implemented by the use of a runtime stack.
Two Stack Algorithms for Depth First Search