Section 20

Tie-In to Problem Set 8
Lists, stacks and queues

Tie-In to Problem Set 8

Detecting a palindrome using a stack

Download these files first

Download the Stack.java interface and the LLStack.java implementation and place them in the same directory.

Suppose we have the following static method palindrome that takes a string and should return true if the string is a palindrome and false if the string is not a palindrome. (A palindrome is a string that reads the same way forwards as it does backwards.)

public static boolean palindrome(String str) {
    Stack<char> stack = new Stack<char>();

    // push the first half of the string onto the stack
    for (int i = 0; i < str.length() / 2; i++) {
        stack.push(str.charAt(i));
    }

    // pop the second half from the stack and compare
    for (int i = str.length() / 2; i < str.length(); i++) {
        char c = stack.pop();

        if (c != str.charAt(i)) {
            return false;
        } else {
            return true;
        }
    }

    return true;
}

Download the Palindrome.java file, which includes this method.

This method uses a stack to determine whether a string is a palindrome by checking that the string’s first half matches the second half, taking advantage of the fact that the stack will pop() off the characters that are push()‘d onto it in reverse order. However, this method has several bugs. Identify and fix them all. ¹

Lists, stacks and queues

Recall from lecture the concepts of the stack and queue abstract data types. Stacks and queues are both collections, and they offer similar operations, but organize data differently.

A stack is a last in, first out (LIFO) abstract data type. Removing an item from a stack (popping an item from the stack) produces the item most recently added. Adding an item to a stack (pushing an item) inserts the item after the most recently added item.

All stack operations can be done in O(1) time, as long as the stack has a fixed capacity. Stacks have numerous applications to computer science, most notably the call stack, which we have seen is used to keep track of currently executing methods in the Java virtual machine.

A queue is a first in, first out (FIFO) abstract data type. Removing an item from a queue (dequeueing an item) produces the item that has been in the queue the longest. Adding an item (enqueueing an item) adds the item behind the item that has been in the queue the shortest.

There are many possible queue implementations. Most implementations with linked lists allow for O(1) enqueueing and O(n) dequeueing, but an implemenation can be tailored to a specific application, achieving O(1) efficiency for all operations, if necessary. Queues are also commonly used in computer science for processing tasks fairly.

Given the following stack, depicted here from top to bottom:
```
+   +
| f |
| e |
| a |
| c |
| b |
+---+
```
What would the stack look like after the following sequence of pushes and pops? ²
```
pop();
push(x);
push(w);
pop();
pop();
push(z);
```
Given the following queue, depicted here from the back of the queue to the front:
```
+-------------------+
| d | e | m | b | n |
+-------------------+
```
What would the queue look like after the following sequence of inserts and removes? ³
```
remove();
insert(t);
insert(w);
remove();
insert(r);
remove();
```
Suppose a number of insert() and remove() operations are performed on a queue Q. The insert() operations put the integers 0 through 9 in Q in order, and the remove() operations print the value of the removed item. Which of the following sequences of remove()s could not occur (there may be more than one)? ⁴
1. 0 1 2 3 4 5 6 7 8 9
2. 0 1 2 3 9 8 7 6 5 4
3. 4 3 2 1 0 5 6 9 8 7
4. 9 8 7 6 5 4 3 2 1 0
Suppose a number of pop() and push() operations are performed on a stack S. The push() operations put the integers 0 through 9 onto S in order, and the pop() operations print the value of the popped item. Which of the following sequences of pop()s could not occur (there may be more than one)? ⁵
1. 9 8 7 6 5 4 3 2 1 0
2. 8 7 6 5 4 3 2 1 0 9
3. 4 3 2 1 0 5 6 7 8 9
4. 4 6 8 7 5 3 2 9 0 1

You didn’t think we’d give you the solution to a homework problem, did you? ↩
The altered stack would resemble the following:
```
+   +
| z |
| e |
| a |
| c |
| b |
+---+
```
↩

The altered queue would resemble the following:

+---+---+---+---+---+
| r | w | t | d | e |
+---+---+---+---+---+

↩

a: Can be done with all enqueue()s followed by all dequeue()s.
b: Cannot be done. 4 must follow 3 in the sequence.
c: Cannot be done. 4 cannot come before 0 if 0 is enqueued first.
d: Cannot be done. 9 cannot come before 0 if 0 is enqueued first. ↩
a: Can be done with all push()es followed by all pop()s.
b: Can be done with push(0) through push(8), followed by nine pop()s, then a single push(9) and pop().
c: Can be done with push(0) through push(4), followed by five pop()s, then a sequence of alternating push(x) and pop()s for the remaining numbers.
d: Cannot be done; the following sequence almost works: push(0), push(1), push(2), push(3), push(4), pop() = 4, push(5), push(6), pop() = 6, push(7), push(8), pop() = 8, pop() = 7, pop() = 5, pop() = 3, pop() = 2, push(9), pop() = 9; however, 0 and 1 remain on the stack, with 1 on top; therefore there is no way to get 0 out first. ↩

Last updated on July 27, 2026.