Web全栈~23.数据结构(栈和队列)

傷城~ 2023-01-08 08:16 100阅读 0赞

# Web全栈~23.数据结构(栈和队列) #

## [上一期][Link 1] ##

### 相关博客 ###

[栈和队列的基本概念][Link 2]

[顺序栈和链栈][Link 3]

[顺序栈和链栈的应用][Link 4]

[顺序队和链队][Link 5]

## JavaScript回顾 ##

在JavaScript中也提供了一种让数组的行为类似于其他数据结构的方法。就比如说,数组可以表现得像栈。栈是一种可以限制插入和删除的数据结构,其本质更像是一种受限制的线性表。栈既可以用数组表示也可以用链表表示,而在这里自然是数组表示的顺序栈。

push()方法可以接收任意数量的参数,把它们逐个添加到数组末尾,并且返回修改数组的长度。而pop()方法则是从数组末尾移除最后一项,减少length值。然后返回移除的项。

//创建一个数组
    	   var arr = new Array();
    	   //推入两项
    	   var count = arr.push("alvin","bob");
    	   alert(count);	//2
    	   //再推入一个
    	   count = arr.push("finally");
    	   alert(count);
    	   //取得最后一项
    	   var item = arr.pop();
    	   alert(item);  //这里返回的是 finally。 也就是最后一项
    	   //结果
    	   alert(arr);

接着我们说说队列。队列和栈一样都是受限制的线性表。然后队列和栈是相反的数据结构,可以参考博客[栈和队列的基本概念][Link 2]。栈是先进后出,而队列则是先进先出。由于push()是向数组末尾添加项的方法,所以模拟队列就需要一个从数组前端取的项的方法。而实现这个操作的方法则是shift()。它能够移除数组的第一项并且返回该项,然后数组长度-1。shift和push结合可以让数组用起来像是队列。

//创建一个数组
    	   var arr = new Array();
    	   //推入两项
    	   var count = arr.push("alvin","bob");
    	   alert(count);	//2
    	   //再推入一个
    	   count = arr.push("finally");
    	   alert(count);
    	   //取得最后一项
    	   var item = arr.shift();
    	   alert(item);  //这里返回的是 finally。 也就是最后一项
    	   //结果
    	   alert(arr);

我们发现代码其实没什么改变,只是把pop换成了shift而已~

## Java语言实现 ##

/** * 栈 */
    class Stack{ 
        //数组引用
        private Object []data;
        //栈顶
        private Integer top = -1;
        //栈长
        private Integer size;
        public Stack(){ 
            this(10);
        }
    
        /** * 初始化 * @param init */
        public Stack(int init){ 
            data = new Object[init];
            size = 0;
        }
    
        /** * 返回栈的长度 * @return */
        public Integer size(){ 
            return size;
        }
    
        /** * 入栈 * @param o */
        public void put(Object o){ 
            data[++top] = o;
        }
    
        /** * 出栈 * @return */
        public Object pop(){ 
            Object p = data[top];
            data[top--] = null;
            return p;
        }
    
        /** * 重写toString * @return */
        public String toString(){ 
            return Arrays.toString(data);
        }
    }
    
    /** * 队列 */
    class Queue{ 
        private Object []data;
        private Integer rear = -1;
    
        public Queue(){ 
            this(10);
        }
    
        /** * 初始化 * @param init */
        public Queue(Integer init){ 
            data = new Object[init];
        }
    
        /** * 进队 * @param o */
        public void put(Object o){ 
            data[++rear] = o;
        }
    
        /** * 出队列 * @return */
        public Object pop(){ 
            //保存要出队列的值
            Object datum = data[0];
            //作为引用
            Object []temp = data;
            //将后面的元素前移
            for(int i = 1; i < data.length; i++){ 
                temp[i - 1] = data[i];
            }
            //赋值
            data = temp;
            return datum;
        }
    
        public String toString(){ 
            return Arrays.toString(data);
        }
    }

[Link 1]: https://blog.csdn.net/qq_41424688/article/details/112833156
[Link 2]: https://blog.csdn.net/qq_41424688/article/details/107586625
[Link 3]: https://blog.csdn.net/qq_41424688/article/details/107631321
[Link 4]: https://blog.csdn.net/qq_41424688/article/details/107643349
[Link 5]: https://blog.csdn.net/qq_41424688/article/details/107681132