数据结构-js实现栈和队列

Dear 丶 2022-01-19 02:55 272阅读 0赞

我们都知道数据结构对我们非常重要，我在几场笔试题中遇到了非常多的有关数据结构的问题。因为我学习数据结构在一年多以前了，有点忘了，所以今天想好好温习一下数据结构的知识，先从简单的数据结构说起吧。

1.  栈

### 我们都知道栈是一个坟场重要的数据的一种结构，它在我们的计算机很多方面都用到了，也包括我们的调用栈之类的，都有有关栈的知识。我们先说一下栈。网上有好多有数组的方法实现的，那样太简单了，但是我不想那样，因为我想自己实现一个，不想用数组的API。 ###

*  栈的特点
    
     *  后进先出（LIFO）（先进后出）
     *  只允许操作栈顶，不能操作栈底
 *  栈示例 偷偷地到了一张图，如有侵权马上撤回。我就不多介绍栈了，相信大家都很清楚。 我们就来说一下栈的操作吧。

1.  初始化栈(init、构造函数)
2.  获取栈顶元素（Top）
3.  出栈 （Pop）
4.  入栈 （Push）
5.  获取栈的长度 （Length）
6.  判断栈是否为空 （isEmpty）
7.  清空栈 （Clear）
8.  输出栈内元素 （List）

我罗列的可能不清楚或者是不专业，请大家多多指正。（这只是我个人理解的栈的实现）

class Stack {
        constructor(){
        	this.stacks = [];
        	this.length = 0;
        }
        Top(){
        	return this.stacks[this.length - 1];
        }
        Pop(){
        	return this.stacks.splice(-- this.length, 1)[0];
        }
        Push(val){
        	this.stacks[this.length ++] = val;
        }
        Length(){
        	return this.length;
        }
        isEmpty(){
        	return this.length === 0;
        }
        Clear(){
        	this.stacks = [];
        	this.length = 0;
        }
        List(){
        	for (var i = this.length - 1; i >= 0; i --) {
        		console.log(this.stacks[i]);
        	}
        }
    }
    复制代码

我们来验证一下

console.log('-------------栈-----------------');
    let stack = new Stack();
    console.log("为空" + stack.isEmpty());
    console.log("长度" + stack.Length());
    stack.Push(0);
    stack.Push(1);
    stack.Push(2);
    console.log("长度" + stack.Length());
    stack.List();
    console.log("栈顶元素" + stack.Top());
    console.log("出栈" + stack.Pop());
    console.log("出栈" + stack.Pop());
    console.log("栈顶元素" + stack.Top());
    stack.Clear();
    console.log("清栈");
    console.log("长度" + stack.Length());
    stack.List();
    复制代码

我觉得栈是一种思想，对数据的管理或者是操作的方式，我觉得每一个人都有每一个人实现的方式和对栈的理解，所以我觉得不必非得按照什么样的格式，只要实现了这样一个操作就行。

*  栈的应用
    
     *  进制转换
     *  括号或者是成对的匹配问题
     *  等等

前面聊完了栈，那么就一定有一个跟它思想类似的队列要说一下。下面我们来聊一聊队列。

1.  队列

*  队列在我们的计算机中也是大量的应用，比如我们的消息队列之类的。
 *  特点
    
     *  先进先出（FIFO）
     *  队尾插入，队头删除
 *  实例

就像是我们平常的排队一样。

*  基本操作

1.  初始化（构造函数、init）
2.  入队（EnQueue）
3.  出队（DeQueue）
4.  队头元素（Top）
5.  长度（Length）
6.  判断队是否为空（QueueEmpty）
7.  输出队内元素（List）
8.  清空队列（ClearQueue）

*  代码

class Queue{
        constructor(){
        	this.queue = [];
        	this.length = 0;
        }
        EnQueue(val){
        	this.queue[this.length ++] = val;
        }
        DeQueue(){
        	this.length --;
        	return this.queue.splice(0, 1)[0];
        }
        List(){
        	for (var i = 0; i < this.length; i++) {
        		console.log( this.queue[i] );
        	}
        }
        Top(){
        	return this.queue[0];
        }
        Length(){
        	return this.length;
        }
        QueueEmpty(){
        	return this.length === 0;
        }
        ClearQueue(){
        	this.queue = [];
        	this.length = 0;
        }
    }
    复制代码

*  操作示例

let queue = new Queue();
    console.log("长度" + queue.Length());
    console.log("为空" + queue.QueueEmpty());
    queue.EnQueue(0);
    queue.EnQueue(1);
    queue.EnQueue(2);
    console.log("长度" + queue.Length());
    console.log("队头" + queue.Top());
    console.log("出队" + queue.DeQueue());
    console.log("出队" + queue.DeQueue());
    console.log("队头" + queue.Top());
    queue.List();
    queue.ClearQueue();
    console.log('清空队列');
    console.log("长度" + queue.Length());
    console.log("为空" + queue.QueueEmpty());
    复制代码

*  输出
 *  遗憾

队列还有好几种，比如说循环队列，就是队头、队尾两个指针，用能力的人可以实现以下。

*  总结

1.  这次算是自己的温习，也想让大神们监督和指出错误。好久没有写过栈和队列的实现了，记得一年以前在上大二的时候，我们用C语言实现栈和队列，现在想起来还意犹未尽。记得那时候用队列和栈实现一个停车场进出车的功能。
2.  写这篇文章的时候心里很不踏实，总感觉哪里写的不对，希望不要误人子弟，也希望大神们能指出我的错误，能让我更加的认识数据结构与栈和队列。

转载于:https://juejin.im/post/5ce557f8e51d45777621badf