数据结构与算法Java版——栈与队

拼搏现实的明天。 2022-06-13 01:24 145阅读 0赞

> 　　数据结构一般都是由c++来讲解并且实现的，所以如果像我这种没学过c++而学过Java的就很尴尬了，不过不要以为Java不能实现数据结构那些常用的表啊，树啊之类的（不知道有没有同学以为Java没有指针，所以一些功能无法实现呢？这是错误的噢）。这个学期学了数据结构这本书，所以我打算用Java实现其中表，队，栈，树。如果你有兴趣可以持续关注我后续操作。我的个人博客为[我的博客][Link 1]。

## 栈 ##

栈是一种很奇特的结构，因为它是“先进后出”的，也就是一批进去的元素中，第一个进去的元素最后一个出来，如下图所示：

![这里写图片描述][9442331.jpg]

看起来复杂的表面，其实底下仍然是数组实现的，也就是说，栈，其实是一种线性表，只是说进出元素都在栈底罢了。接下来就和各位一起实现一个简单的栈。

public class SequenceStack<T> {
        private Object[] elementData;
        private int size;   //栈中元素
        private int capacity;  //数组容量
    
        //栈总长为capacity
        public SequenceStack(int capacity) {
            elementData=new Object[capacity];
            this.capacity=capacity;
        }
    
        //获得栈中元素个数
        public int getLength(){
            return size;
        }
    
        //入栈
        public void push(T element){
            elementData[size]=element;
            size++;
        }
    
        //出栈
        public void pop(){
            elementData[size-1]=null;
            size--;
        }
    
        //判断是否为空
        public boolean isEmpty(){
            return size==0;
        }
    
        //清空栈中元素
        public void clear(){
            Arrays.fill(elementData, null);
            size=0;
        }
    
        //重写toString方法，让其输出栈中所有元素
        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<=size-1;i++)
            {
                sb=sb.append(elementData[i]+" ");
            }
            return sb+"";
        }
    }

撸以上几段小小代码，一个简单的栈就实现了，如果自己还想要什么方法，自己进行包装写出来就好了，之前说过LinkList是一个双向链表，如果查看API会发现它也提供了pop,peek,push等方法，这其实说明LinkList也是可以当作栈来用的，当然是链栈，链栈的实现基本和链表实现差不多，只是进出元素位置与单链表不同罢了。

## 队 ##

队列是一种和栈一样，被限制了的线性表，它一端来插入元素，另一端删除元素，也就像我们平时生活中排队那样，一头买东西，买了走人，一头排队等候。因此，所以它是“先进先出”的。如下图所示：

![这里写图片描述][52927447.jpg]

接下来重点讲解的是队的重要两种形式：

**- 顺序队列**  
**- 循环队列**

**顺序队列**

顺序队列：顾名思义，就是按照顺序排的，排成一条线，前面走，后面来。底层仍然是数组作为基础，循环队列也是如此。接下来就一起撸代码吧。

public class SequenceQuene<T>{
        private Object[] elementData;   //底层数组
        private int capacity;   //队容量
        private int front; //队头
        private int rear; //队尾
    
        //顺序队的构造函数，初始化的时候会将队头队尾都等于0
        public SequenceQuene(int capacity) {
            elementData=new Object[capacity];
            this.capacity=capacity;
            front=0;
            rear=0;
        }
    
        //判断队列是否为空
        public boolean isEmpty(){
            return front==rear;
        }
    
        //队中元素个数
        public int getLength(){
            return rear-front;
        }
    
        //入队，队尾rear执行
        public void insert(T element){
            //当队尾大于容量-1时，队满
            if(rear>capacity-1)
            {
                throw new IndexOutOfBoundsException("队满");
            }
            elementData[rear]=element;
            rear++;
        }
    
        //出队，队头front执行
        public void remove(){
            if(front==0){
                throw new IndexOutOfBoundsException("队空");
            }
            elementData[front]=null;
            front++;
        }
    
        //重写toString方法，让其输出队列
        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            for(int i=front;i<rear;i++)
            {
                sb=sb.append(elementData[i]+" ");
            }
            return sb+"";
        }
    
        //清空队列，记得要把队头队尾设为0
        public void clear(){
            Arrays.fill(elementData, null);
            front=0;
            rear=0;
        }
    }

其实对比顺序栈和顺序队列，我们可以发现他们很相似，区别只是删除插入方式有些不同罢了。但是**上面这种方式实现的顺序队列有缺陷，比如当队头删除完(front=rear)，队尾添加满后（rear=capacity-1），就会发现队头等于队尾，这个时候既无法添加元素，也无法删除元素，这就造成了数组的浪费。**

针对以上这个问题，可以每次删除后，**将整个队列中元素向前移动一位，也就是front被固定，队尾rear=rear-1,但是这么做，如果队列大的话，每次移动的元素就太多，性能会大幅下降。**于是我们就有另一个比较好的办法：

**循环队列**

![这里写图片描述][47418938.jpg]

循环队列就很好的解决了上面那个问题，而且不需要移动任何元素，性能得到了很好的提升，不过需要注意几点：（front和rear为队头，队尾，capacity为数组容量）

**1. 返回队列长度时，需要搞清front和rear谁大，如果rear大则长度为\*\*\*\*rear-front，反之则为capacity-front+rear。**  
**2. 判断是否队列为空时，要同时满足rear=ftront和rear处的元素值为空。**  
**3. 插入删除元素时，如果rear和front达到临界值，下一次执行插入删除，rear和front需要“掉头”。**  
**4. 遍历时，要根据front和rear的大小进行遍历，若rear大,直接遍历一部分即可，如果front>rear,则分front-capacity和0-rear两部分遍历。**

接下来就是实现的具体步骤了：

public class CircleQuene<T> {
        private Object[] elementData;
        private int capacity;   //队容量
        private int front; //队头
        private int rear; //队尾
    
        public CircleQuene(int capacity) {
            elementData=new Object[capacity];
            this.capacity=capacity;
            front=0;
            rear=0;
        }
    
        //判断循环队列是否为空
        public boolean isEmpty(){
            return rear==front&&elementData[rear]==null;
        }
    
        //当队尾大于队头与队尾小于队头两种情况
        public int getLength(){
            return rear>front ? rear-front:capacity-front+rear;
        }
    
        public void insert(T element){
            if(front==rear&&elementData[rear]!=null)
            {
                throw new IndexOutOfBoundsException("队满");
            }
            elementData[rear++]=element;
            //如果rear到头了就从零开始
            if(rear>capacity-1){
                rear=0;
            }
        }
    
        //删除元素
        public void remove(){
            if(isEmpty()){
                throw new IndexOutOfBoundsException("队空");
            }
            elementData[front++]=null;
            //front达到临界值，“掉头”
            if(front>capacity-1){
                front=0;
            }
        }
    
        //清空队列
        public void clear(){
            Arrays.fill(elementData, null);
            front=0;
            rear=0;
        }
    
        //如果rear大于front，只需直接遍历即可，反之则分两部分遍历
        @Override
        public String toString() {
            StringBuilder sb=new StringBuilder();
            if(rear>front){
                for(int i=front;i<rear;i++)
                {
                    sb=sb.append(elementData[i]+" ");
                }
            }else{
                for(int i=front;i<capacity;i++)
                {
                    sb=sb.append(elementData[i]+" ");
                }
                for(int i=0;i<rear;i++)
                {
                    sb=sb.append(elementData[i]+" ");
                }
            }
            return sb+"";
        }
    }

到此，循环队列就实现了，队列还有其他一些类型，链队列，双向队列（LinkList也是一种特殊的双向链式队列，应该算是JDK提供的集合类里面方法 最多的了，毕竟这小伙子什么都沾边了）等，但是实现方法都与上面的类似，这里就不一一实现了。

今天分享到此结束啦，下一次就进入**树结构**啦。  
![这里写图片描述][6cb998536124e796.png]

> 　　生活不仅有技术，还有诗和远方。

[Link 1]: http://xichangblog.com
[9442331.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-22/9442331.jpg
[52927447.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-22/52927447.jpg
[47418938.jpg]: http://or0um8wrx.bkt.clouddn.com/17-6-22/47418938.jpg
[6cb998536124e796.png]: http://i4.buimg.com/519918/6cb998536124e796.png