22.12.22 - [CtCI] Ch.3 Stacks and Queues

[suhyunsim]

Questions

• 3.1 Three in One
• 3.2 Stack Min
• 3.3 Stack of Plates
• 3.4 Queues via Stacks
• 3.5 Sort Stack
• 3.6 Animal Shelter

[suhyunsim]

3.1 Three in One

[suhyunsim]

3.2 Stack Min

[suhyunsim]

3.3 Stack of Plates

[suhyunsim]

3.4 Queues via Stacks

Hints

• The major difference between a queue and a stack is the order of elements. A queue removes the oldest item and a stack removes the newest item. How could you remove the oldest item from a stack if you only had access to the newest item?
• We can remove the oldest item from a stack by repeatedly removing the newest item (inserting those into the temporary stack) until we get down to one element. Then, after we've retrieved the newest item, putting all the elements back. The issue with this is that doing several pops in a row will require O(N) work each time. Can we optimize for scenarios where we might do several pops in a row?

Things to Consider

• Queue / Stack
  • FIFO / LIFO
• (1) To Flip Over -> peek(), pop() backward
  • stack1 -> stack2
  • peek/pop
  • stack2 -> stack1
• (2) Lazy way
  • stackNewest(inBox): new -> top (add())
  • stackOldest(outBox): last -> top (peek(), poll())

Solution

MyQueue

package main.java.com.poogle.cracking.Ch3StackQueue;

import java.util.Stack;

public class MyQueue<T> {
    /*
    stackNewest: new -> top (inBox) add
    stackOldest: last -> top (outBox) peek, poll
     */
    Stack<T> stackNewest, stackOldest;

    public MyQueue() {
        stackNewest = new Stack<>();
        stackOldest = new Stack<>();
    }

    public int size() {
        return stackNewest.size() + stackOldest.size();
    }

    public void add(T value) {
        // new -> top
        stackNewest.push(value);
    }

    // move newest -> oldest
    private void shiftStacks() {
        if (stackOldest.isEmpty()) {
            while (!stackNewest.isEmpty()) {
                stackOldest.push(stackNewest.pop());
            }
        }
    }

    public T peek() {
        shiftStacks();
        return stackOldest.peek();
    }

    public T remove() {
        shiftStacks();
        return stackOldest.pop();
    }
}

Codes for Test

package main.java.com.poogle.cracking.Ch3StackQueue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.concurrent.ThreadLocalRandom;

public class Main {
    public static void main(String[] args) {
        MyQueue<Integer> myQueue = new MyQueue<>();
        Queue<Integer> testQueue = new LinkedList<>();

        for (int i = 0; i < 100; i++) {
            int choice = ThreadLocalRandom.current().nextInt(1, 11);
            if (choice <= 5) {
                int element = ThreadLocalRandom.current().nextInt(1, 11);
                testQueue.add(element);
                myQueue.add(element);
                System.out.println("Enqueued: " + element);
            } else if (testQueue.size() > 0) {
                int top1 = testQueue.remove();
                int top2 = myQueue.remove();
                if (top1 != top2) {
                    System.out.println("Fail - Different Tops: " + top1 + ", " + top2);
                }
                System.out.println("Dequeued: " + top1);
            }

            if (testQueue.size() == myQueue.size()) {
                if (testQueue.size() > 0 && testQueue.peek() != myQueue.peek()) {
                    System.out.println("Fail - Different Tops: " + testQueue.peek() + ", " + myQueue.peek());
                }
            } else {
                System.out.println("Fail - Different Sizes");
            }
        }
    }
}

ETC

[suhyunsim]

3.5 Sort Stack

Hints

• One way of sorting an array is to iterate through the array and insert each element into a new array in sorted order. Can you do this with a stack?
• Imagine your secondary stack is sorted. Can you insert elements into it in sorted order? You might need some extra storage. What could you use for extra storage?
• Keep the secondary stack in sorted order, with the biggest elements on the top. Use the primary stack for additional storage.

Things to Consider

• Make logic with one additional stack
• What if I could use infinite stacks?
  • Using Merge Sort or Quick Sort

Solution

Using One More Stack

• time: O(N^2), space: O(N)

package main.java.com.poogle.cracking.Ch3StackQueue.Q5;

import java.util.Stack;
import java.util.concurrent.ThreadLocalRandom;

public class Solution {
    public static void sort(Stack<Integer> stack1) {
        //stack1 -> stack2 in sorted order
        Stack<Integer> stack2 = new Stack<>();
        while (!stack1.isEmpty()) {
            int temp = stack1.pop();
            while (!stack2.isEmpty() && stack2.peek() > temp) {
                stack1.push(stack2.pop());
            }
            stack2.push(temp);
        }
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
    }

    public static void main(String[] args) {
        Stack<Integer> stack1 = new Stack<>();
        for (int i = 0; i < 10; i++) {
            int r = ThreadLocalRandom.current().nextInt(1, 1001);
            stack1.push(r);
        }
        sort(stack1);
        while (!stack1.isEmpty()) {
            System.out.println(stack1.pop());
        }
    }
}

ETC

[suhyunsim]

3.6 Animal Shelter