【数据结构与算法（二）】栈和队列

系统管理员 2021-12-19 17:59 359阅读 0赞

## 栈Stack（LIFO） ##

*  后进先出（last in first out)

#### **主体** ####

public class Stack<E> { 
        private E data[];
        private int size;
    
        public Stack(int capacity){ 
            data=(E[])new Object[capacity];
            size=0;
        }
        public Stack(){ 
            this(10);
        }
    }

#### **各种方法** ####

*  时间复杂度均为O(1)\[有的为均摊复杂度\]

//入栈
        public void push(E e){ 
            if(size==data.length){ 
                resize(data.length*2);
            }
            data[size]=e;
            size++;
        }
    
        //出栈
        public E pop(){ 
            if(size==0)
                throw new IllegalArgumentException("pop failed,stack is empty!");
            E e=data[size-1];
            size--;
            data[size]=null;
            if(size==data.length/4&&data.length/2!=0){ 
                resize(data.length/2);
            }
            return e;
        }
    
        //查看栈顶元素
        public E peek(){ 
            if(size==0)
                throw new IllegalArgumentException("peek failed,stack is empty!");
            else
                return data[size-1];
        }
    
        public boolean isEmpty(){ 
            return size==0;
        }
    
        public int getSize(){ 
            return size;
        }
    
        public int getCapacity(){ 
            return data.length;
        }
    
        //变换容量
        private void resize(int newCapacity){ 
            E []newData=(E[])new Object[newCapacity];
            for(int i=0;i<size;i++){ 
                newData[i]=data[i];
            }
            data=newData;
        }

#### **可以利用Array编写栈** ####

*  栈中的数组可以用Array对象替代，这样就可以复用Array中已经编写好的函数了。

## 队列Queue（FIFO) ##

*  先进先出（first in first out)

#### **接口** ####

public interface Queue<E> { 
        public void enqueue(E e);//入队
        public E dequeue();//出队
        public E getFront();//查看队首
        public int getSize();
        public boolean isEmpty();
    }

#### **主体** ####

public class ArrayQueue<E> implements Queue<E> { 
    	//复用前面的Array,因为队列就是数组的一个子集
        private Array<E> array;
    
        public ArrayQueue(int capacity){ 
            array=new Array<>(capacity);
        }
    
        public ArrayQueue(){ 
            array=new Array<>();
        }
    }

#### **各种方法** ####

*  除了dequeue()时间复杂度为O(n)，其他均为O(1)

//获取元素个数
        @Override
        public int getSize(){ 
            return array.getSize();
        }
    
        //判断是否为空
        @Override
        public boolean isEmpty(){ 
            return array.isEmpty();
        }
    
        //入队，从队尾添加元素
        @Override
        public void enqueue(E e){ 
            //可能会触发扩容
            array.addLast(e);
        }
    
        //出队，从队首删除元素，后面的元素往前挪，时间复杂度O(n)
        @Override
        public E dequeue(){ 
            //可能会触发缩容
            return array.removeFirst();
        }
    
        //查看队首元素
        @Override
        public E getFront(){ 
            return array.getFirst();
        }

## 循环队列 ##

*  如果数组的容量为Capacity，则实际可用的容量为Capacity-1，总会浪费一个。
 *  用front表示队首元素的位置，用tail表示队尾元素后一个位置。
 *  font和tail进行加减都要（front/tail±常数)%数组实际长度。
 *  最好不要用front/tail减去一个数，因为会涉及到负数，使问题变得复杂。
 *  用front==tail判断循环队列是否为空。
 *  用（front+1)%数组长度==tail判断循环队列是否已满。

#### **主体** ####

public class LoopQueue<E> implements Queue<E> { 
    
        private E[] data;
        //front表示队首元素的位置，tail表示队尾元素位置+1
        private int front,tail;
    
        public LoopQueue(int capacity){ 
            //因为循环队列总有一个位置是浪费的，所以+1用来匹配用户想要的容量
            data=(E[])new Object[capacity+1];
            front=0;
            tail=0;
        }
        public LoopQueue(){ 
            this(10);
        }
    }

#### **主要方法** ####

*  时间复杂度均为O(1)

//判断是否为空
        @Override
        public boolean isEmpty(){ 
            return tail==front;
        }
    	//获取循环队列中元素的个数
        @Override
        public int getSize(){ 
            if(front<tail){ 
                return tail-front;
            }else{ 
                return data.length-front+tail;
            }
        }
    
        //获取实际能用的数组容量
        public int getCapacity(){ 
            return data.length-1;
        }
    
        //入队
        @Override
        public void enqueue(E e){ 
            //判断条件(tail+1)%数组容量==front表示数组实际容量已满，需要扩容
            if((tail+1)%data.length==front){ 
                resize(getCapacity()*2+1);
            }
            data[tail]=e;
            tail=(tail+1)%data.length;
        }
    
        //出队,均摊时间复杂度为O(1)
        @Override
        public E dequeue(){ 
            if(front==tail){ 
                throw new IllegalArgumentException("cannot dequeue from an empty queue");
            }
            E ret=data[front];
            data[front]=null;
            front=(front+1)%data.length;
            //空间浪费大，进行缩容
            if(getSize()==getCapacity() /4&&getCapacity()/2!=0){ 
                resize(getCapacity()/2+1);
            }
            return ret;
        }
    
        //查看队首元素
        @Override
        public E getFront(){ 
            if(isEmpty()){ 
                throw new IllegalArgumentException("cannot get first element from an empty queue");
            }
            return data[front];
        }
    
        //变换容量
        private void resize(int newCapacity){ 
            E[] newData=(E[])new Object[newCapacity];
            //让从front到tail-1中的元素全部复制到新数组中,有两种遍历方法(见toStirng())，用下面这种最方便
            for(int i=0;i<getSize();i++){ 
                newData[i]=data[(i+front)%data.length];
            }
            tail=getSize();
            front=0;
            //不能写在更新tail和front语句前，因为getSize()要用到原来的数组信息
            data=newData;
        }

#### **toString()和循环队列中的两种遍历方法** ####

@Override
        public String toString(){ 
            StringBuilder ret=new StringBuilder();
            ret.append(String.format("LoopQueue{size:%d,capacity:%d}\n front [",getSize(),getCapacity()));
            //循环队列有两种遍历方法
            /* for(int i=0;i<getSize();i++){ ret.append(data[(i+front)%data.length]); if((i+front+1)%data.length!=tail) ret.append(","); }*/
            for(int i=front;i!=tail;i=(i+1)%data.length){ 
                ret.append(data[i]);
                //循环队列中不要用到front\tail减去一个数，容易出现负数
                //这里不要用i!=(tail-1)%data.length
                if((i+1)%data.length!=tail){ 
                    ret.append(",");
                }
            }
            ret.append("] tail");
            return ret.toString();
        }

## 数组队列和循环队列的比较 ##

*  循环队列是数组队列的改进版，数组队列有一个缺点就是在出队（**dequeue()**）的时候时间复杂度为O(n)，而改进后的循环队列出队均摊复杂度为O(1)，这样可以大大提高性能。