Computer Science

Stacks

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 (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 PUSH 5 PUSH 2 PUSH 10 PUSH 2 PUSH 9 MUL ADD DIV SUB 

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)$$?

The objective of Towers of Hanoi puzzle is to move all discs to stack three, obeying the following simple rules:

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

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:

• stack_2.pop()
• stack_3.push(purple)

Consider the nearly complete puzzle below

How many operations are needed if the above puzzle is solved using the fewest number of stack operations?

×