栈和队列

栈和队列

栈：数据先进后出，犹如弹匣

队列：数据先进先出，好似排队

双向链表实现 栈和队列

 static class DoubleNode<T>{
        T value;
        DoubleNode last;
        DoubleNode next;
        public DoubleNode(T value) {
            this.value = value;
        }
   }
​
   public static class DoubleEndsQueue<T> {
        DoubleNode<T> pre=null;
        DoubleNode<T> tail=null;
        public void addHead(T t){
            DoubleNode node=new DoubleNode(t);
            if (pre==null){
                pre=node;
                tail=node;
            }else{
                node.next=pre;
                pre.last=node;
                pre=node;
            }
        }
​
        public void addTail(T t){
            DoubleNode node=new DoubleNode(t);
            if (pre==null){
                pre=node;
                tail=node;
            }else{
                tail.next=node;
                node.last=tail;
                tail=node;
            }
        }
​
        public T removeHead(){
            if (pre==null)return null;
            DoubleNode<T> node = pre.next;
            T t=pre.value;
            if (tail==pre){
                tail=null;
                pre=null;
                return t;
            }
            pre.next=null;
            node.last=null;
            pre=node;
            return  t;
        }
​
​
        public T removeTail(){
            if (tail==null)return null;
            DoubleNode<T> node = tail.last;
            T t=tail.value;
            if (tail==pre){
                tail=null;
                pre=null;
                return t;
            }
            tail.last=null;
            node.next=null;
            tail=node;
            return t;
        }
    }
​
    public static class MyStack<T>{
        DoubleEndsQueue <T> stack=new  DoubleEndsQueue<T>();
        public void add(T t){
            stack.addTail(t);
        }
        public T pop(){
            return stack.removeTail();
        }
    }
​
    public static class MyQueue<T>{
        DoubleEndsQueue <T> stack=new  DoubleEndsQueue<T>();
        public void add(T t){
            stack.addHead(t);
        }
        public T pop(){
            return stack.removeHead();
        }
    }

数组实现队列

public static class MyQueue{
        int size;
        int push;
        int pop;
        int limit;
        int[]arr;
        public MyQueue(int limit) {
            size=0;
            push=0;
            pop=0;
            arr=new int[limit];
            this.limit = limit;
        }
        public void pushNode(int value){
            if (size==limit)throw new RuntimeException("数组已经满了");
            arr[push]=value;
            size++;
            if (push<limit-1){
                push++;
            }else{
                push=0;
            }
        }
        public Integer pop(){
            if (size==0)throw new RuntimeException("数组没有数据");
            Integer num=arr[pop];
            size--;
            if (pop<limit-1){
                pop++;
            }else{
                pop=0;
            }
            return num;
        }
    }

题目一

实现一个特殊的栈，在基本功能的基础上，再实现返回栈中最小元素的功能

1）pop、push、getMin操作的时间复杂度都是 O(1)。

2）设计的栈类型可以使用现成的栈结构。

//空间换时间的方式  每次加入新元素 就要往minStack栈中加入最小元素
public static class stack1{
        Stack<Integer> dataStack=new Stack<Integer>();  //放入数据的栈
        Stack<Integer> minStack=new Stack<Integer>();   //最小元素的栈
​
        public Integer getMin(){
            if (minStack.isEmpty())throw new RuntimeException("stack is Empty");
            return minStack.peek();
        }
​
        public void push(Integer data){
            dataStack.add(data);
            if (minStack.isEmpty()){
                minStack.add(data);
            }else if(data<getMin()){ //新加入的数据比最小栈的栈顶数小 放入当前数
                minStack.add(data);
            }else{
                minStack.add(minStack.peek());
            }
        }
 
        public Integer pop(){  //同时弹出两个栈的数据
            if (dataStack.isEmpty())throw new RuntimeException("stack is Empty");;
            minStack.pop();
            return dataStack.pop();
        }
    }
    
    /**
     * 时间换空间 加入的数《= minStack的栈顶元素  放入minStack
     * 弹出的时候判断 是否<=minStack栈顶的元素 ==》弹出
     *
     */
    public static class stack2{
        Stack<Integer> dataStack=new Stack<Integer>();
        Stack<Integer> minStack=new Stack<Integer>();
​
        public Integer getMin(){
            if (minStack.isEmpty())throw new RuntimeException("stack is Empty");
            return minStack.peek();
        }
​
        public void push(Integer data){
            dataStack.add(data);
            if (minStack.isEmpty()){
                minStack.add(data);
            }else if(data<=getMin()){
                minStack.add(data);
            }
        }
​
        public Integer pop(){
            if (dataStack.isEmpty())throw new RuntimeException("stack is Empty");;
            Integer data=dataStack.pop();
            if (data<=getMin()){
                minStack.pop();
            }
            return data;
        }
    }

如何用栈结构实现队列结构

    Stack<Integer> stackData=new Stack<Integer>();
    Stack<Integer> stackPop=new Stack<Integer>();
​
    public void push(Integer a){
        stackData.push(a);
        if (stackPop.isEmpty()){  //stackPop为空才能往里面放数据 
            while(!stackData.isEmpty()){
                stackPop.push(stackData.pop());
            }
        }
    }
​
    public Integer pop(){
        if (stackPop.isEmpty()) throw new RuntimeException("queue is empty");
        return stackPop.pop();
    }

如何用队列结构实现栈结构

    Queue<Integer> queue=new LinkedList<Integer>();
    Queue<Integer> help=new LinkedList<Integer>();
​
    public void push(Integer a){
        queue.offer(a);
    }
​
    public Integer pop(){
        while(queue.size()!=1){
            help.offer(queue.poll());
        }
        Integer ans = queue.poll();
        Queue<Integer> temp=queue;
        queue=help;
        help=temp;
        return ans;
    }