Programs Using Stacks#

Let’s look at a Java program, to see how stacks work.

import java.util.Stack;

Stack<String> candidates = new Stack<>();
String who1;
String who2;

candidates.push("Santa Claus");
candidates.push("Tooth Fairy");
who1 = candidates.pop();
who2 = candidates.peek();

System.out.print("Is this stack empty?  ");
System.out.println(candidates.empty() ? "yes" : "no");

candidates.push("Minnie Mouse");
candidates.push("Daisy Duck");
candidates.push(candidates.pop().toLowerCase());
candidates.pop();
candidates.pop();
candidates.pop();

System.out.print("Is this stack empty?  ");
System.out.println(candidates.empty() ? "yes" : "no");

Is this stack empty?  no
Is this stack empty?  yes



Here is a step-by-step visualization of this program:

Start

Stack<String> candidates = new Stack<>();
String who1;
String who2;
candidates start

1

candidates.push("Santa Claus");
candidates one

2

candidates.push("Tooth Fairy");
candidates two

3

who1 = candidates.pop();
candidates three

4

who2 = candidates.peek();
candidates four

5

System.out.print("Is this stack empty?  ");
System.out.println(candidates.empty() ? "yes" : "no");
candidates five

6

candidates.push("Minnie Mouse");
candidates six

7

candidates.push("Daisy Duck");
candidates seven

8

candidates.push(candidates.pop().toLowerCase());
candidates eight

9

candidates.pop();
candidates nine

10

candidates.pop();
candidates ten

11

candidates.pop();
candidates eleven

12

System.out.print("Is this stack empty?  ");
System.out.println(candidates.empty() ? "yes" : "no");
candidates twelve

Done



Note that we can print our stack at anytime using standard output, since Stack has a toString() method defined:

import java.util.Stack;

Stack<Integer> squares = new Stack<>();

squares.push(4);
squares.push(9);
squares.push(25);
squares.push(36);
squares.push(49);
squares.push(64);

System.out.println("My Stack is: " + squares);

My Stack is: [4, 9, 25, 36, 49, 64]



Practice Questions#

  1. In Java, make a stack to hold each letter of your name and then use this stack to print your name in reverse order.

  2. Assume we have a stack called “banana”. This stack contains more than two integers.
    a. Write the Java code to double the top item of the stack.
    b. Write the Java code to add the top two items together and place the result on top of the stack. Be careful that your stack still contains the original two items, just below your new item.

  3. Suppose that data is received in the following order:

    12, 15, 19, 4, 3, 35, 20, 36, 14, 42

    Create a stack which is sorted from bottom to top in ascending order (without using the built-in sort method; use only peek, push, pop and empty). Use one additional helper stack, but no additional primitive variables in your solution.

  4. Repeat the above question, writing the code in modular form, that is, with some of your own methods or putting some of your code into a method or methods.

To Solutions