实现栈和队列、用栈实现队列，用队列实现栈。

一时失言乱红尘 2023-02-16 12:15 21阅读 0赞

### 一、实现一个栈 ###

就是一个指针下标，入栈加，出栈减。

/**
         * 我的栈
         */
        public  class  MyStack{
            private Integer[] arr;
            private Integer size;
    
            public MyStack(int initSize) throws IllegalAccessException {
                if(initSize < 0){
                    throw new IllegalAccessException("容量不能小于0");
                }
                arr = new Integer[initSize];
                size = 0;
            }
            public Integer peek(){
                if(size == 0){
                    return null;
                }
                return arr[size - 1];
            }
            public Integer pop(){
                if(size == 0){
                    throw new ArrayIndexOutOfBoundsException("栈已经空了");
                }
                return arr[--size];
            }
            public void push(Integer obj){
                if(size == arr.length){
                    throw new ArrayIndexOutOfBoundsException("栈已经满了");
                }
                arr[size++] = obj;
            }
        }

### 二、实现队列 ###

两个指针和一个size。

/**
         * 我的队列
         */
        public class MyQueue{
            private Integer[] arr;
            private Integer size;
            private Integer start;
            private Integer end;
    
            public MyQueue(int initsize) throws IllegalAccessException {
                if(initsize < 0){
                    throw new IllegalAccessException("容量不能小于0");
                }
                arr = new Integer[initsize];
                size = 0;
                start = 0;
                end = 0;
            }
            public Integer peek(){
                if(size == 0){
                    return null;
                }
                return arr[start];
            }
            public Integer pop(){
                if(size == 0){
                    throw new ArrayIndexOutOfBoundsException("队列为空");
                }
                size--;
                int temp =start;
                start = start == arr.length ? 0 :start + 1;
                return arr[temp];
            }
            public Integer push(Integer obj){
                if(size == arr.length){
                    throw new ArrayIndexOutOfBoundsException("队列已经满了");
                }
                size++;
                int temp = end;
                end = end == arr.length ? 0 : end + 1;
                return arr[temp];
            }
        }

# 三、用栈实现队列 #

有两个栈，一个是stackPush，一个是stackPop，如果有入队的，那么直接压入stackPush中，如果有出队的，判断stackPush是不是空，如果不是直接出队，如果是，那么stackPush中所有数依次出栈进入stakcPop然后再出队。

public class TwoStackQueue{
            private Stack<Integer> stackPush;
            private Stack<Integer> stackPop;
    
            public TwoStackQueue(){
                stackPush = new Stack<Integer>();
                stackPop = new Stack<Integer>();
            }
    
            public void push(int obj){
                stackPush.push(obj);
            }
            public int poll(){
                if(stackPush.isEmpty() && stackPop.isEmpty()){
                    throw new RuntimeException("Queue is Empty");
                }else if(stackPop.empty()){
                    while(!stackPush.empty()){
                        stackPop.push(stackPush.pop());
                    }
                }
                return stackPop.pop();
            }
            public int peek() {
                if (stackPop.empty() && stackPush.empty()) {
                    throw new RuntimeException("Queue is empty!");
                } else if (stackPop.empty()) {
                    while (!stackPush.empty()) {
                        stackPop.push(stackPush.pop());
                    }
                }
                return stackPop.peek();
            }
        }

### 四、两个队列实现一个栈 ###

两个队列queue和help，如果要入栈，那么直接入队到queue，如果要弹栈，那么queue中所有的元素都到help中，到最后一个元素的时候取出，然后弹栈，最后两个队列交换指针。

public class TwoQueueStack{
            private Queue<Integer> queue;
            private Queue<Integer> help;
            public TwoQueueStack(){
                queue = new LinkedList<Integer>();
                help = new LinkedList<Integer>();
            }
            public void push(int pushInt){
                queue.add(pushInt);
            }
            public int peek(){
                if(queue.isEmpty()){
                    throw new RuntimeException("Stack is empty!");
                }
                while(queue.size() != 1){
                    help.add(queue.poll());
                }
                int result = queue.poll();
                help.add(result);
                swap();
                return result;
            }
    
            public int pop() {
                if (queue.isEmpty()) {
                    throw new RuntimeException("Stack is empty!");
                }
                while (queue.size() > 1) {
                    help.add(queue.poll());
                }
                int res = queue.poll();
                swap();
                return res;
            }
    
            private void swap() {
                Queue<Integer> tmp = help;
                help = queue;
                queue = tmp;
            }
    
        }

### 五、一个例题 ###

在实现栈的基本功能的基础上，实现返回栈中最小元素的方法操作。

两个栈，一个放最小值的，如果插入的元素小于等于最小值栈顶元素，那么直接入最下栈，然后如果弹栈的是时候，这个值等于弹出的元素才跟着弹出栈

public class MyStackGetMin {
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;
    
        public MyStackGetMin(){
            stackData = new Stack<Integer>();
            stackMin = new Stack<Integer>();
        }
        public void push(int newNum){
            if(this.stackMin.isEmpty()){
                this.stackMin.push(newNum);
            }else if(this.getMin() >= newNum){
                this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
    
        }
        public int pop(){
            if(this.stackData.isEmpty()){
                throw new RuntimeException("Your stack is empty!");
            }
            int value = this.stackData.pop();
            if(value == this.getMin()){
                this.stackMin.pop();
            }
            return value;
        }
        public int getMin(){
            if(this.stackMin.isEmpty()){
                throw new RuntimeException("Your stack is empty!");
            }
            return this.stackMin.peek();
        }
    }