1.1使用数组实现栈

public class MyStack {
    private int[] arr;
    private int top;
    private int size;
    private final int limit;

    public MyStack(int limit) {
        arr = new int[limit];
        top = -1;
        size = 0;
        this.limit = limit;
    }

    public void push(int value) {
        if (size == limit) {
            throw new RuntimeException("栈满了，不能继续添加");
        }
        size++;
        arr[++top] = value;
    }

    public int pop() {
        if (size == 0) {
            throw new RuntimeException("栈为空");
        }
        size--;
        return arr[top--];
    }

}

1.2使用数组实现队列

public class MyQueue {
    private int[] arr;
    private int pushi;
    private int polli;
    private int size;
    private final int limit;

    public MyQueue(int limit) {
        arr = new int[limit];
        pushi = 0;
        polli = 0;
        size = 0;
        this.limit = limit;
    }

    public void push(int value) {
        if (size == limit) {
            throw new RuntimeException("队列满了，不能继续添加");
        }
        size++;
        arr[pushi] = value;
        pushi = nextIndex(pushi);
    }

    public int pop() {
        if (size == 0) {
            throw new RuntimeException("队列空了，不能再拿出了");
        }
        size--;
        int ans = arr[polli];
        polli = nextIndex(polli);
        return ans;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private int nextIndex(int i) {
        return i < limit - 1 ? i + 1 : 0;
    }

}

2.1两个队列实现一个栈

  • 两个队列queue1, queue2。不管是插入还是弹出，保证总有一个队列为空。

  • 入栈操作：总是往有数据的列队插入，默认两个列队空，插入queue1

  • 出栈操作：从非空列队中删除数据并插入空列队，一直到非空列队剩下一个元素，该元素就是出栈的元素

public class TwoQueuesStack {
    Queue<Integer> q1;
    Queue<Integer> q2;

    public TwoQueuesStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(Integer value) {
        if (q1.isEmpty() && q2.isEmpty()) {
            q1.add(value);
        } else if (q1.size() > 0) {
            q1.add(value);
        } else if (q2.size() > 0) {
            q2.add(value);
        }
    }

    public Integer pop() {
        if (q1.isEmpty() && q2.isEmpty()) {
            return null;
        }
        if (q2.size() == 0) {
            while (q1.size() != 1) {
                q2.add(q1.poll());
            }
            return q1.poll();
        } else { //q1为空的情况
            while (q2.size() != 1) {
                q1.add(q2.poll());
            }
            return q2.poll();
        }
    }

}

2.2两个栈实现队列

  • 有两个栈pushStack 和 popStack
  • 先将数据存到第一个栈里，再将第一个栈里的元素全部出栈到第二个栈，第二个栈出栈，即可达到先进先出
public class TwoStacksQueue {
    private Stack<Integer> pushStack;
    private Stack<Integer> popStack;

    public TwoStacksQueue() {
        pushStack = new Stack<>();
        popStack = new Stack<>();
    }

    //pushStack向popStack倒入数据
    private void push2pop() {
        if (popStack.empty()) {
            while (!pushStack.empty()) {
                popStack.push(pushStack.pop());
            }
        }
    }

    public void add(int value) {
        pushStack.push(value);
        push2pop();
    }

    public Integer poll() {
        if (pushStack.empty() && popStack.empty()) {
            return null;
        }
        push2pop();
        return popStack.pop();
    }

    public Integer peek() {
        if (pushStack.empty() && popStack.empty()) {
            return null;
        }
        push2pop();
        return popStack.peek();
    }

    public boolean empty() {
        return pushStack.empty() && popStack.empty();
    }

}

hhhhh