Stack Problems (C, C++, Java)

Solution and explanation

Solution

A stack follows LIFO (Last In, First Out). push() inserts, pop() removes the top element, and peek() returns the top without removing it.

Step by step

1. Keep an array stack[MAX] and an index top, starting at -1 (empty stack).
2. push(x): if top == MAX - 1 the stack is full (overflow); otherwise increment top and store x at stack[top].
3. pop(): if top == -1 the stack is empty (underflow); otherwise return stack[top] and decrement top.
4. peek(): return stack[top] without changing top (or -1 when empty).

Dry run

C

#include <stdio.h>
#define MAX 100

int stack[MAX], top = -1;

void push(int x) {
    if (top == MAX - 1) {
        printf("Stack Overflow\n");
        return;
    }
    stack[++top] = x;
}

int pop(void) {
    if (top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return stack[top--];
}

int peek(void) {
    return top == -1 ? -1 : stack[top];
}

int main(void) {
    push(10);
    push(20);
    printf("%d\n", pop());  // 20
    printf("%d\n", peek()); // 10
    return 0;
}

C++

#include <iostream>
#include <stack>
using namespace std;

int main() {
    stack<int> s;
    s.push(10);
    s.push(20);

    cout << s.top() << '\n'; // 20
    s.pop();
    cout << s.top() << '\n'; // 10
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);

        System.out.println(stack.peek()); // 20
        System.out.println(stack.pop());  // 20
    }
}

Complexity

• push, pop and peek: O(1) time each.
• Space: O(n) for the array.

Note: in Java prefer ArrayDeque over the legacy Stack class, which is synchronized and therefore slower.

Solution and explanation

Solution

Push every character onto the stack, then pop each character into the output. Popping reverses the insertion order.

Step by step

1. Create an empty stack of characters.
2. Traverse the string from left to right and push each character.
3. Pop characters one by one and write them back from index 0; the last character pushed comes out first.

Dry run for "HELLO"

C

#include <stdio.h>
#include <string.h>

void reverse(char s[]) {
    int n = strlen(s);
    char stack[n + 1];
    int top = -1;

    for (int i = 0; i < n; i++)
        stack[++top] = s[i];

    for (int i = 0; i < n; i++)
        s[i] = stack[top--];
}

int main(void) {
    char s[] = "HELLO";
    reverse(s);
    printf("%s\n", s); // OLLEH
}

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    string s = "HELLO";
    stack<char> st;

    for (char c : s) st.push(c);

    for (char &c : s) {
        c = st.top();
        st.pop();
    }

    cout << s << '\n'; // OLLEH
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    public static void main(String[] args) {
        String s = "HELLO";
        Deque<Character> st = new ArrayDeque<>();

        for (char c : s.toCharArray()) st.push(c);

        StringBuilder result = new StringBuilder();
        while (!st.isEmpty()) result.append(st.pop());

        System.out.println(result); // OLLEH
    }
}

Complexity

• Time: O(n): each character is pushed once and popped once.
• Space: O(n) extra space for the stack.

Note: without a stack the same result needs only O(1) extra space by swapping s[i] and s[n-1-i] from both ends; the stack version is asked to test LIFO understanding.

Solution and explanation

Problem

Determine whether ({[]}) is balanced but ([)] is not.

Solution

Push opening brackets. For each closing bracket, verify that it matches the most recently opened bracket.

Step by step

1. Scan the string from left to right.
2. Opening bracket (, [ or {: push it.
3. Closing bracket: if the stack is empty there is nothing to close, so the string is unbalanced. Otherwise pop the top and check it is the matching opener () ↔ (, ] ↔ [, } ↔ {); a mismatch means unbalanced.
4. Other characters are ignored.
5. At the end the string is balanced only if the stack is empty (no opener left unclosed).

Dry run

C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool balanced(const char *s) {
    int n = strlen(s);
    char stack[n + 1];
    int top = -1;

    for (int i = 0; i < n; i++) {
        char c = s[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[++top] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            if (top == -1) return false;
            char t = stack[top--];
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{'))
                return false;
        }
    }
    return top == -1;
}

int main(void) {
    printf("%d\n", balanced("({[]})")); // 1
    printf("%d\n", balanced("([)]"));   // 0
    return 0;
}

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool balanced(string s) {
    stack<char> st;

    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')' || c == ']' || c == '}') {
            if (st.empty()) return false;

            char t = st.top();
            st.pop();

            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{'))
                return false;
        }
    }

    return st.empty();
}

int main() {
    cout << balanced("({[]})") << '\n'; // 1
    cout << balanced("([)]") << '\n';   // 0
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static boolean balanced(String s) {
        Deque<Character> st = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (st.isEmpty()) return false;
                char t = st.pop();
                if ((c == ')' && t != '(') ||
                    (c == ']' && t != '[') ||
                    (c == '}' && t != '{'))
                    return false;
            }
        }
        return st.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(balanced("({[]})")); // true
        System.out.println(balanced("([)]"));   // false
    }
}

Complexity

• Time: O(n), one pass.
• Space: O(n) in the worst case (all openers).

Solution and explanation

Problem

Evaluate 2 3 4 * +, which equals 2 + (3 × 4) = 14.

Solution

Push operands. When an operator appears, pop the right operand first, then the left operand; apply the operator and push the result.

Step by step

1. Read the tokens from left to right.
2. Number: push it.
3. Operator: pop b (right operand), then pop a (left operand), compute a op b and push the result. The order matters for - and /: 8 2 - is 8 − 2.
4. At the end the single value left on the stack is the answer.

Dry run

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

int evaluatePostfix(char *expr) {
    int stack[100], top = -1;
    char *token = strtok(expr, " ");

    while (token != NULL) {
        if (strlen(token) == 1 && strchr("+-*/", token[0])) {
            int b = stack[top--];
            int a = stack[top--];
            switch (token[0]) {
                case '+': stack[++top] = a + b; break;
                case '-': stack[++top] = a - b; break;
                case '*': stack[++top] = a * b; break;
                case '/': stack[++top] = a / b; break;
            }
        } else {
            stack[++top] = (int) strtol(token, NULL, 10);
        }
        token = strtok(NULL, " ");
    }
    return stack[top];
}

int main(void) {
    char expr[] = "2 3 4 * +";
    printf("%d\n", evaluatePostfix(expr)); // 14
    return 0;
}

C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int evaluatePostfix(vector<string> tokens) {
    stack<int> st;

    for (const string &t : tokens) {
        if (t == "+" || t == "-" || t == "*" || t == "/") {
            int b = st.top(); st.pop();
            int a = st.top(); st.pop();

            if (t == "+") st.push(a + b);
            else if (t == "-") st.push(a - b);
            else if (t == "*") st.push(a * b);
            else st.push(a / b);
        } else {
            st.push(stoi(t));
        }
    }

    return st.top();
}

int main() {
    cout << evaluatePostfix({"2", "3", "4", "*", "+"});
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static int evaluatePostfix(String expr) {
        Deque<Integer> st = new ArrayDeque<>();

        for (String t : expr.trim().split("\\s+")) {
            switch (t) {
                case "+", "-", "*", "/" -> {
                    int b = st.pop();
                    int a = st.pop();
                    st.push(switch (t) {
                        case "+" -> a + b;
                        case "-" -> a - b;
                        case "*" -> a * b;
                        default -> a / b;
                    });
                }
                default -> st.push(Integer.parseInt(t));
            }
        }
        return st.pop();
    }

    public static void main(String[] args) {
        System.out.println(evaluatePostfix("2 3 4 * +")); // 14
    }
}

Complexity

• Time: O(n), each token handled once.
• Space: O(n) for the stack.

Note: division here uses integer arithmetic and assumes valid input (no division by zero, enough operands).

Solution and explanation

Problem

Convert A+B*C to ABC*+.

Solution

Output operands immediately. Push operators onto a stack, respecting precedence and parentheses. Multiplication has higher precedence than addition.

Step by step (shunting-yard)

1. Operand (letter or digit): append it to the output.
2. (: push it.
3. ): pop operators to the output until (, then discard the (.
4. Operator: while the top of the stack is an operator with greater or equal precedence, pop it to the output; then push the new operator.
5. At the end, pop every remaining operator to the output.

Precedence: ^ (3) > * / (2) > + - (1).

Dry run for A+B*C

C

#include <stdio.h>
#include <ctype.h>

int precedence(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    if (c == '^') return 3;
    return 0;
}

void toPostfix(const char *s, char *out) {
    char stack[100];
    int top = -1, k = 0;

    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (c == ' ') continue;
        if (isalnum((unsigned char) c)) out[k++] = c;
        else if (c == '(') stack[++top] = c;
        else if (c == ')') {
            while (top != -1 && stack[top] != '(') out[k++] = stack[top--];
            if (top != -1) top--;               // discard '('
        } else {
            while (top != -1 && stack[top] != '(' && precedence(stack[top]) >= precedence(c))
                out[k++] = stack[top--];
            stack[++top] = c;
        }
    }
    while (top != -1) out[k++] = stack[top--];
    out[k] = '\0';
}

int main(void) {
    char out[100];
    toPostfix("A+B*C", out);
    printf("%s\n", out); // ABC*+
    return 0;
}

C++

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int precedence(char c) {
    if (c == '+' || c == '-') return 1;
    if (c == '*' || c == '/') return 2;
    if (c == '^') return 3;
    return 0;
}

string toPostfix(string s) {
    stack<char> st;
    string out;

    for (char c : s) {
        if (c == ' ') continue;

        if (isalnum((unsigned char)c)) out += c;
        else if (c == '(') st.push(c);
        else if (c == ')') {
            while (!st.empty() && st.top() != '(') {
                out += st.top();
                st.pop();
            }
            if (!st.empty()) st.pop();
        } else {
            while (!st.empty() && st.top() != '(' &&
                   precedence(st.top()) >= precedence(c)) {
                out += st.top();
                st.pop();
            }
            st.push(c);
        }
    }

    while (!st.empty()) {
        out += st.top();
        st.pop();
    }
    return out;
}

int main() {
    cout << toPostfix("A+B*C"); // ABC*+
}

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static int precedence(char c) {
        return switch (c) {
            case '+', '-' -> 1;
            case '*', '/' -> 2;
            case '^' -> 3;
            default -> 0;
        };
    }

    static String toPostfix(String s) {
        Deque<Character> st = new ArrayDeque<>();
        StringBuilder out = new StringBuilder();

        for (char c : s.toCharArray()) {
            if (c == ' ') continue;
            if (Character.isLetterOrDigit(c)) out.append(c);
            else if (c == '(') st.push(c);
            else if (c == ')') {
                while (!st.isEmpty() && st.peek() != '(') out.append(st.pop());
                if (!st.isEmpty()) st.pop();
            } else {
                while (!st.isEmpty() && st.peek() != '(' && precedence(st.peek()) >= precedence(c))
                    out.append(st.pop());
                st.push(c);
            }
        }
        while (!st.isEmpty()) out.append(st.pop());
        return out.toString();
    }

    public static void main(String[] args) {
        System.out.println(toPostfix("A+B*C")); // ABC*+
    }
}

Complexity

• Time: O(n): every character is output once and each operator is pushed and popped at most once.
• Space: O(n) for the stack and the output.

This compact version assumes single-character operands and left-associative operators.

Note: exponentiation requires a right-associativity adjustment. ^ (power) is right-associative, so A^B^C should give ABC^^. To support that, pop only when the top has strictly greater precedence for ^: change the condition to precedence(top) > precedence(c) || (precedence(top) == precedence(c) && c != '^').

Solution and explanation

Problem

For every element, find the first element to its right that is greater. If none exists, the answer is -1. For [4, 5, 2, 25] the answer is [5, 25, 25, -1].

Solution

Scan right to left; pop smaller or equal values and use the remaining top as the answer.

Step by step

1. Keep a stack of candidates from the right side, decreasing from bottom to top.
2. For index i from n-1 down to 0: pop every value <= a[i] (they can never be the answer for anything further left, because a[i] is bigger and closer).
3. If the stack is empty the answer is -1, otherwise the answer is the top.
4. Push a[i].

Dry run for [4, 5, 2, 25]

C

#include <stdio.h>

void nextGreater(int a[], int n, int res[]) {
    int st[n], top = -1;
    for (int i = n - 1; i >= 0; i--) {
        while (top != -1 && st[top] <= a[i]) top--;
        res[i] = top == -1 ? -1 : st[top];
        st[++top] = a[i];
    }
}

int main(void) {
    int a[] = {4, 5, 2, 25}, n = 4, res[4];
    nextGreater(a, n, res);
    for (int i = 0; i < n; i++) printf("%d ", res[i]); // 5 25 25 -1
    return 0;
}

C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> res(n);
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && st.top() <= a[i]) st.pop();
        res[i] = st.empty() ? -1 : st.top();
        st.push(a[i]);
    }
    return res;
}

int main() {
    for (int x : nextGreater({4, 5, 2, 25})) cout << x << ' '; // 5 25 25 -1
}

Java

import java.util.*;

public class Main {
    static int[] nextGreater(int[] a) {
        int n = a.length;
        int[] res = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && st.peek() <= a[i]) st.pop();
            res[i] = st.isEmpty() ? -1 : st.peek();
            st.push(a[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{4, 5, 2, 25}))); // [5, 25, 25, -1]
    }
}

Complexity

• Time: O(n): each element is pushed once and popped at most once.
• Space: O(n) for the stack.

Solution and explanation

Problem

For every element, find the nearest element to its left that is greater; -1 if none. For [10, 4, 2, 20, 40, 12, 30] the answer is [-1, 10, 4, -1, -1, 40, 40].

Solution

Scan left to right; remove smaller or equal elements from the monotonic stack.

Step by step

1. The stack holds values seen so far in decreasing order (bottom → top).
2. For each a[i], pop values <= a[i].
3. The remaining top (if any) is the previous greater element; otherwise -1.
4. Push a[i].

Dry run (first five)

C

#include <stdio.h>

void previousGreater(int a[], int n, int res[]) {
    int st[n], top = -1;
    for (int i = 0; i < n; i++) {
        while (top != -1 && st[top] <= a[i]) top--;
        res[i] = top == -1 ? -1 : st[top];
        st[++top] = a[i];
    }
}

int main(void) {
    int a[] = {10, 4, 2, 20, 40, 12, 30}, n = 7, res[7];
    previousGreater(a, n, res);
    for (int i = 0; i < n; i++) printf("%d ", res[i]); // -1 10 4 -1 -1 40 40
    return 0;
}

C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> previousGreater(const vector<int>& a) {
    vector<int> res;
    stack<int> st;
    for (int x : a) {
        while (!st.empty() && st.top() <= x) st.pop();
        res.push_back(st.empty() ? -1 : st.top());
        st.push(x);
    }
    return res;
}

int main() {
    for (int x : previousGreater({10, 4, 2, 20, 40, 12, 30})) cout << x << ' ';
}

Java

import java.util.*;

public class Main {
    static int[] previousGreater(int[] a) {
        int[] res = new int[a.length];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < a.length; i++) {
            while (!st.isEmpty() && st.peek() <= a[i]) st.pop();
            res[i] = st.isEmpty() ? -1 : st.peek();
            st.push(a[i]);
        }
        return res;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(previousGreater(new int[]{10, 4, 2, 20, 40, 12, 30})));
    }
}

Complexity

• Time: O(n). Space: O(n).

Solution and explanation

Problem

The span of a day's price is the number of consecutive days up to and including today with price <= today's price. For [100, 80, 60, 70, 60, 75, 85] the spans are [1, 1, 1, 2, 1, 4, 6].

Solution

Maintain indices in a decreasing-price stack; calculate the distance to the previous greater price.

Step by step

1. Store indices, not prices, so the distance can be computed.
2. For day i, pop indices whose price is <= price[i].
3. Span = i + 1 if the stack is empty (all earlier prices are smaller), otherwise i - top (distance to the previous greater price).
4. Push i.

Dry run

C

#include <stdio.h>

void stockSpan(int price[], int n, int span[]) {
    int st[n], top = -1;
    for (int i = 0; i < n; i++) {
        while (top != -1 && price[st[top]] <= price[i]) top--;
        span[i] = top == -1 ? i + 1 : i - st[top];
        st[++top] = i;
    }
}

int main(void) {
    int p[] = {100, 80, 60, 70, 60, 75, 85}, n = 7, s[7];
    stockSpan(p, n, s);
    for (int i = 0; i < n; i++) printf("%d ", s[i]); // 1 1 1 2 1 4 6
    return 0;
}

C++

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

vector<int> stockSpan(const vector<int>& price) {
    int n = price.size();
    vector<int> span(n);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && price[st.top()] <= price[i]) st.pop();
        span[i] = st.empty() ? i + 1 : i - st.top();
        st.push(i);
    }
    return span;
}

int main() {
    for (int x : stockSpan({100, 80, 60, 70, 60, 75, 85})) cout << x << ' ';
}

Java

import java.util.*;

public class Main {
    static int[] stockSpan(int[] price) {
        int n = price.length;
        int[] span = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && price[st.peek()] <= price[i]) st.pop();
            span[i] = st.isEmpty() ? i + 1 : i - st.peek();
            st.push(i);
        }
        return span;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(stockSpan(new int[]{100, 80, 60, 70, 60, 75, 85})));
    }
}

Complexity

• Time: O(n). Space: O(n).

Solution and explanation

Problem

Design a stack that supports push, pop, top and getMin, all in O(1).

Solution

Store each value alongside the minimum so far, or maintain a second minimum stack.

Step by step (two stacks)

1. main holds all values; mins holds the minimum at each depth.
2. push(x): push x to main; push min(x, mins.top) to mins (or x if empty).
3. pop(): pop both stacks, so mins.top is again the minimum of what remains.
4. getMin(): return mins.top.

Dry run

C

#include <stdio.h>
#define MAX 100

int mainSt[MAX], minSt[MAX], top = -1;

void push(int x) {
    mainSt[++top] = x;
    minSt[top] = (top == 0 || x < minSt[top - 1]) ? x : minSt[top - 1];
}
void pop(void) { if (top >= 0) top--; }
int peek(void) { return mainSt[top]; }
int getMin(void) { return minSt[top]; }

int main(void) {
    push(5); push(3); push(7);
    printf("%d\n", getMin()); // 3
    pop(); pop();
    printf("%d\n", getMin()); // 5
    return 0;
}

C++

#include <iostream>
#include <stack>
using namespace std;

class MinStack {
    stack<int> st, mins;
public:
    void push(int x) {
        st.push(x);
        mins.push(mins.empty() ? x : min(x, mins.top()));
    }
    void pop() { st.pop(); mins.pop(); }
    int top() { return st.top(); }
    int getMin() { return mins.top(); }
};

int main() {
    MinStack s;
    s.push(5); s.push(3); s.push(7);
    cout << s.getMin() << '\n'; // 3
    s.pop(); s.pop();
    cout << s.getMin() << '\n'; // 5
}

Java

import java.util.*;

class MinStack {
    private final Deque<Integer> st = new ArrayDeque<>();
    private final Deque<Integer> mins = new ArrayDeque<>();

    void push(int x) {
        st.push(x);
        mins.push(mins.isEmpty() ? x : Math.min(x, mins.peek()));
    }
    void pop() { st.pop(); mins.pop(); }
    int top() { return st.peek(); }
    int getMin() { return mins.peek(); }
}

public class Main {
    public static void main(String[] args) {
        MinStack s = new MinStack();
        s.push(5); s.push(3); s.push(7);
        System.out.println(s.getMin()); // 3
        s.pop(); s.pop();
        System.out.println(s.getMin()); // 5
    }
}

Complexity

• Time: O(1) per operation.
• Space: O(n) extra for the minimum stack. (An O(1)-extra-space variant stores 2x − min when a new minimum arrives.)

Solution and explanation

Problem

Sort a stack so the largest element is on top, using only another stack. [34, 3, 31, 98, 92, 23] (bottom → top) becomes [3, 23, 31, 34, 92, 98].

Solution

Use a second stack to insert each element in sorted order.

Step by step

1. sorted keeps elements in ascending order bottom → top.
2. Pop tmp from the input.
3. While sorted.top > tmp, move that element back to the input stack (it will be re-inserted later).
4. Push tmp onto sorted. Repeat until the input is empty.

Dry run (input top is 23)

C

#include <stdio.h>

int sortStack(int in[], int n, int out[]) {
    int inTop = n - 1, outTop = -1;
    while (inTop >= 0) {
        int tmp = in[inTop--];
        while (outTop >= 0 && out[outTop] > tmp) in[++inTop] = out[outTop--];
        out[++outTop] = tmp;
    }
    return outTop + 1;
}

int main(void) {
    int in[] = {34, 3, 31, 98, 92, 23}, out[6];
    int n = sortStack(in, 6, out);
    for (int i = 0; i < n; i++) printf("%d ", out[i]); // 3 23 31 34 92 98
    return 0;
}

C++

#include <iostream>
#include <stack>
using namespace std;

stack<int> sortStack(stack<int> in) {
    stack<int> sorted;
    while (!in.empty()) {
        int tmp = in.top(); in.pop();
        while (!sorted.empty() && sorted.top() > tmp) {
            in.push(sorted.top());
            sorted.pop();
        }
        sorted.push(tmp);
    }
    return sorted;
}

int main() {
    stack<int> s;
    for (int x : {34, 3, 31, 98, 92, 23}) s.push(x);
    stack<int> r = sortStack(s);
    while (!r.empty()) { cout << r.top() << ' '; r.pop(); } // 98 92 34 31 23 3
}

Java

import java.util.*;

public class Main {
    static Deque<Integer> sortStack(Deque<Integer> in) {
        Deque<Integer> sorted = new ArrayDeque<>();
        while (!in.isEmpty()) {
            int tmp = in.pop();
            while (!sorted.isEmpty() && sorted.peek() > tmp) in.push(sorted.pop());
            sorted.push(tmp);
        }
        return sorted;
    }

    public static void main(String[] args) {
        Deque<Integer> s = new ArrayDeque<>();
        for (int x : new int[]{34, 3, 31, 98, 92, 23}) s.push(x);
        System.out.println(sortStack(s)); // [98, 92, 34, 31, 23, 3] (top first)
    }
}

Complexity

• Time: O(n²) in the worst case (each insertion may move all sorted elements).
• Space: O(n) for the second stack.