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 \(s\),
MUL is equivalent to
s.push(s.pop() * s.pop()). All other elementary operations (
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 on the top of the second stack to the third stack would require the following two operations:
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 \(2\) 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 \(n\) a number has to be pushed to this stack in order to be fully converted can be expressed as a function \(f(n)\). What is \(f(n)\)?