One impact that stacks have had in the area of computer organization is in the realization of so-called stack machines. Here, the entries in a stack are arithmetic operands and the machine instruction set contains arithmetic operators.
For example for a stack , MUL
is equivalent to s.push(s.pop() * s.pop())
. All other elementary operations (ADD
, DIV
, SUB
) are defined in a similar way. What will POP
return once the stack machine evaluates the operations below?
1 2 3 4 5 6 7 8 9 |
|
The objective of Towers of Hanoi puzzle is to move all discs to stack three, obeying the following simple rules:
We can consider each stack as a stack object. For example moving the purple disk (the top disk on the second stack) to the third stack would require the following two operations:
stack_2.pop()
stack_3.push(purple)
In general, moving a disk from the top of one stack to the top of another will require two operations in a row. Consider the nearly complete puzzle below
How many operations are needed if the above puzzle is solved using the fewest number of stack operations?
Consider the standard algorithm for converting a decimal number (base 10) into a binary number (base 2). This algorithm makes use of a single stack and works by continually taking the modulo of the number and also continually dividing it by two. This allows us to finally obtain the bits of the integer.
The number of times a number has to be pushed to this stack in order to be fully converted can be expressed as a function . What is ?