CodingGyan

Build a Stack Class

easy Object-Oriented Programming

Problem

Implement a stack and run commands. Each input line is push X, pop, peek or size. Print one line for each command: OK for push, the removed value for pop, the top value for peek, and the number of items for size. If pop or peek is used on an empty stack print Error: stack is empty.

Constraints

  • 1 <= commands <= 1000

Examples

Input

push 1
push 2
peek
pop

Output

OK
OK
2
2

Solutions

Best approachTime O(1) per operationSpace O(n)

A stack adds and removes items at the same end, so the last item pushed is the first one popped. We build it ourselves to learn how it works inside; the Java library has ArrayDeque for production code.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Process commands line by line.
 * Input   : Several lines of commands.
 * Output  : One answer line for each command.
 * Approach: Push and pop at the same end.
 * Time    : O(1) per operation
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
        // Step 1: A stack is last-in, first-out. This class keeps its items in an array that grows when it is full.
        static class IntStack {
            private int[] items = new int[2];
            private int count = 0;

            void push(int value) {
                // Step 2: When the array is full, make it twice as big and copy the items.
                if (count == items.length) {
                    items = java.util.Arrays.copyOf(items, items.length * 2);
                }
                items[count] = value;
                count++;
            }

            int pop() {
                if (count == 0) {
                    throw new IllegalStateException("stack is empty");
                }
                count--;
                return items[count];
            }

            int peek() {
                if (count == 0) {
                    throw new IllegalStateException("stack is empty");
                }
                return items[count - 1];
            }

            int size() {
                return count;
            }
        }

    // This method solves the task. It receives the input and returns the answer.
    static String[] solve(String[] lines) {
        IntStack stack = new IntStack();
        String[] output = new String[lines.length];

        for (int i = 0; i < lines.length; i++) {
            String[] parts = lines[i].split(" ");

            // Step 3: Run the command. Pop and peek throw an exception on an empty stack.
            try {
                if (parts[0].equals("push")) {
                    stack.push(Integer.parseInt(parts[1]));
                    output[i] = "OK";
                } else if (parts[0].equals("pop")) {
                    output[i] = String.valueOf(stack.pop());
                } else if (parts[0].equals("peek")) {
                    output[i] = String.valueOf(stack.peek());
                } else {
                    output[i] = String.valueOf(stack.size());
                }
            } catch (IllegalStateException error) {
                output[i] = "Error: " + error.getMessage();
            }
        }
        return output;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        java.util.List<String> all = new java.util.ArrayList<>();
        while (scanner.hasNextLine()) {
            String line = scanner.nextLine().trim();
            if (!line.isEmpty()) {
                all.add(line);
            }
        }
        String[] lines = all.toArray(new String[0]);
        System.out.println(String.join("\n", solve(lines)));
    }
}
Hints (2)
  1. Which item leaves first?
  2. What should pop do on an empty stack?

Try these next