Review Data Structures (linked lists, stacks, queues, trees) (Ch.10)
Stacks and Queues
Stack. Examine the item most recently added. Queue. Examine the item least recently added.
Copyright By PowCoder代写 加微信 powcoder
• A Stack is an iterable collection that is based on the last-in-first-out (LIFO) policy
• Stack overflow and underflow.
• Implementation of stack operations (empty, push, pop)
• Stack applications:
• Parsing in a compiler.
• Java virtual machine.
• Undo in a word processor.
• Back button in a Web browser.
• PostScript language for printers.
• Implementing function calls in a compiler.
• A Queue is an iterable collection that is based on the first-in-first-out (FIFO) policy
• Implementation of queues operations (enqueue, dequeue)
Linked List
Fundamental data types:
Value: collection of objects.
Operations: insert, remove, iterate, test if empty. Intent is clear when we insert.
Which item do we remove?
Doubly Linked List
• A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list
• A doubly linked list is an object with an attribute key , two other pointer attributes: next and prev and a value for data.
• Implementation of doubly linked list operations (search, insert, delete)
• Binary tree
• Attributes p, left, and right for pointers
• rooted tree with unbounded branching
Performance Characteristics
• In the linked-list implementations of the Bag, Queue, and Stack APIs, all operations take constant time in the worst case
4.3 Stacks and Queues
it is easy to convince yourself that it computes the proper value: any time the algo-
erator, all surrounded by parentheses, it leaves the result of performing that opera- Stack Example
rithm encounters a subexpression consisting of two operands separated by an op-
tion on those operands on the operand stack. The result is the same as if that value had appeared in the input instead of the sub-
• Example: Arithmetic expression evaluation
that would yield the same result. We can apply
(1+((2+3)*(4*5))) +((2+3)*(4*5))) ((2+3)*(4*5))) +3)*(4*5))) 3)*(4*5))) )*(4*5)))
Eva l ua t e (PROGRAM 4.3.5) is an implemen- • Value: push onto the value stack.
• Operator: push onto the operator stack.
terprets the computation specified by a given
*5))) 5)))
• Left parenthesis: ignore. string and performs the computation to ar-
rive at the result. A compiler is a program that
converts the string into code on a lower-level
• Right parenthesis: pop operator and two values; push
is a more complicated process than the step- the result of applying that operator to those values
onto the operand stack.
by-step conversion used by an interpreter, but it is based on the same underlying mechanism. Initially, Java was based on using an interpret- er. Now, however, the Java system includes a compiler that converts arithmetic expressions (and, more generally, Java programs) into code for the Java virtual machine, an imaginary ma- chine that is easy to simulate on an actual com- puter.
expression, so we can think of replacing the subexpression by the value to get an expression
• Goal.Evaluateinfixexpretshisiaorgnumse.ntagainandagainuntilwegeta single value. For example, the algorithm com- putes the same value of all of these expres-
Two-stack algorithm. [E. W. Dijkstra]
(1+((2+3)*(4*5))) (1+(5*(4*5)))
( 1 + ( 5 * 20 ) )
( 1 + 100 )
tation of this method. This code is a simple example of an interpreter: a program that in-
*(4 (4* * 5 ) 5 ) )
Trace of expression evaluation (Program 4.3.5)
machine that can do the job. This conversion
• Dijkstra’s two-stack algorithm demo
Dijkstra’s two-stack algorithm
Demo: http://algs4.cs.princeton.edu
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
infix expression (fully parenthesized)
value stack operator stack
operand operator
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
value stack operator stack
Dijkstra’s two-stack algorithm
Value: push onto the value stack.
Operator: push onto the operator stack.
Left parenthesis: ignore.
Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com