Java 刷题 -- 栈（栈最小元素/栈构造队列/递归逆序栈/栈排序）（左程云面试指南）

---

返回栈中最小元素

package abc;

import java.util.Stack;

/**
 * 实现一个特殊的栈，在实现基本功能的基础上，返回栈中最小元素的操作
 * pop push getMin时间复杂度都是O（1）
 * 设计的栈类型可以使用现成的栈结构
 */
public class P01GetMinStack {
    public static class MinStack1 {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MinStack1() {
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }

        public int pop(){
            if (this.stackData.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            this.stackMin.pop();
            return this.stackData.pop();
        }
        public void push(int i){
            if (stackMin.empty()){
                this.stackMin.push(i);
            } else {
                int tmp = stackMin.peek();
                if (tmp < i){
                    this.stackMin.push(tmp);
                } else {
                    this.stackMin.push(i);
                }
            }
            this.stackData.push(i);
        }
        public int getMin(){
            if (this.stackMin.isEmpty()) {
                throw new RuntimeException("Your stack is empty.");
            }
            return this.stackMin.peek();
        }
    }

    public static void main(String[] args){
        MinStack1 ms = new MinStack1();
        ms.push(3);
        ms.push(2);
        ms.push(4);
        ms.push(1);
        ms.push(5);
        System.out.println(ms.getMin());
        ms.pop();
        System.out.println(ms.getMin());
        ms.pop();
        System.out.println(ms.getMin());
        ms.pop();
        System.out.println(ms.getMin());
        ms.pop();
        System.out.println(ms.getMin());
    }
}

---

栈实现队列

package abc;

import java.util.Stack;

/**
 * 编写一个类，支持队列的基本操作（add poll peek）
 */
public class P02StackImplQueue {
    public static class TwoStackQueue {
        public Stack<Integer> stackPush;
        public Stack<Integer> stackPop;

        public TwoStackQueue() {
            stackPush = new Stack<Integer>();
            stackPop = new Stack<Integer>();
        }

        public void add(int i) {
            stackPush.push(i);
        }

        public int poll() {
            if (stackPush.empty() && stackPop.empty()){
                throw new RuntimeException("Queue is empty!");
            } else if (stackPop.empty()){
                while (! stackPush.empty()){
                    int tmp = stackPush.pop();
                    stackPop.push(tmp);
                }
            }
            return stackPop.pop();
        }

        public int peek() {
            if (stackPush.empty() && stackPop.empty()){
                throw new RuntimeException("Queue is empty!");
            } else if (stackPop.empty()){
                while (! stackPush.empty()){
                    int tmp = stackPush.pop();
                    stackPop.push(tmp);
                }
            }
            return stackPop.peek();
        }

    }

    public static void main(String[] args) {
        TwoStackQueue sq = new TwoStackQueue();
        sq.add(1);
        sq.add(2);
        sq.add(3);
        System.out.println(sq.peek());
        System.out.println(sq.poll());
        System.out.println(sq.peek());
        System.out.println(sq.poll());
        System.out.println(sq.peek());
        System.out.println(sq.poll());
    }
}

---

实现栈的逆序，仅用递归

package abc;

import java.util.Stack;

/**
 * 实现栈的逆序，仅用递归
 */
public class P03ReverseStack {
    public static void main(String[] args){
        Stack<Integer> test = new Stack<Integer>();
        test.push(1);
        test.push(2);
        test.push(3);
        test.push(4);
        test.push(5);
        reverse(test);
        while (!test.isEmpty()) {
            System.out.println(test.pop());
        }
    }

    private static void reverse(Stack<Integer> stack) {
        if (stack.empty()){
            return;
        }
        int tmp = getLast(stack);
        reverse(stack);
        stack.push(tmp);
    }

    private static int getLast(Stack<Integer> stack) {
        int result = stack.pop();
        if (stack.empty()){
            return result;
        } else {
            int last = getLast(stack);
            stack.push(result);
            return last;
        }
    }
}

---

栈排序

package abc;

import java.util.Stack;



/**
 * 一个栈中元素类型为整型，需要将该栈从顶到底按照从大到小顺序排序，只允许申请一个栈
 */
public class P05SortStack {
    public static void main(String[] args){
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(3);
        stack.push(1);
        stack.push(6);
        stack.push(2);
        stack.push(5);
        stack.push(4);
        sortStack(stack);
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }

    private static void sortStack(Stack<Integer> stack) {
        if (stack.empty()){
            return;
        }
        Stack<Integer> help = new Stack<Integer>();
        while (!stack.isEmpty()) {
            int cur = stack.pop();      // get top of stack
            while (!help.isEmpty() && help.peek() < cur) {
                stack.push(help.pop()); // push back in stack if top of help > top of stack
            }
            help.push(cur);             // push in help
        }
        while (!help.isEmpty()) {
            stack.push(help.pop());
        }
    }
}