Exercises
Stacks #2

1. Assume that `x, y, z` are integer variables and that `s` is a stack of integers, state the output of each program fragment.

``` x = 3; y = 5; z = 2; s.makeEmpty( ); s.push(x); s.push(4); s.pop(z); s.push(y); s.push(3); s.push(z); s.pop(x); s.push(2); s.push(x); while(! s.isEmpty( )) {    s.pop(x);    System.out.println(x); } ```

2. ``` y = 1; s.makeEmpty( ); s.push(5); s.push(7); s.pop(x); x += y; s.pop(x); s.push(x); s.push(y); s.push(2); s.pop(y); s.pop(x); while (! s.isEmpty( )) {    s.pop(y);    System.out.println(y); } System.out.println("x = " + x); System.out.println("y = " + y); ```

3. Show what is written by the following program fragments, where `s1` and `s2` are stacks of integers. `j, k, m` are integer variables.

``` s1.makeEmpty( ); s2.makeEmpty( ); for (j = 0; j < 9; j++)    s1.push(j); while (! s1.isEmpty( )) {    s1.pop(j);    if(j % 2 == 0)       s2.push(j); } while (! s2.isEmpty( )) {    s2.pop(j);    System.out.println(j); } ```

• ``` j = 1; s1.makeEmpty( ); s2.makeEmpty( ); while ( j * j < 50) {    k = j * j;    s1.push(k);    j++; } for (j = 1; j < 6; j++) {    s1.pop(k);    s2.push(k); } s1.pop(j); for (k = 1; k <= j; k++) {    s2.pop(m);    s1.push(m); } while (! s1.isEmpty( )) {    s1.pop(j);    System.out.println(j); } ```

4. ``` S.makeEmpty( ); x = 3; y = 5; z = y % 2; S.push (x); S.push (x); S.pop (x); S.push ( x + z); S.push (y); while ( ! S.isEmpty( )) {    S.pop (y);    System.out.println("   " + y);```

``` } System.out.println(z + y + x); ```

5. ``` S.makeEmpty( ); T.makeEmpty( ); for (index = 0; index < 20; index++) S.push ( index); while ( ! S.isEmpty( )) {    S.pop ( x);    if (x % 4 == 0)       T.push ( x); } while ( ! T.isEmpty( )) {    T.pop (x);    System.out.print("   " + x); } ```

6. To convert a number from decimal to binary, you simply divide by two until a quotient of zero is reached, then use the successive remainders in reverse order as the binary representation. For example, to convert 35base10 to binary, you perform the following computation.

If you examine the remainders from the last division to the first one, writing them down as you go, you will get the following sequence: `100011`. 100011base2=35base10.

Using stack operations, write a procedure which accepts a non-negative base 10 integer as a parameter, and writes out its binary representation.

Continue to:  Unit 5 / Prev / Next