阅读 79

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

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

我们都知道栈是一个坟场重要的数据的一种结构,它在我们的计算机很多方面都用到了,也包括我们的调用栈之类的,都有有关栈的知识。我们先说一下栈。网上有好多有数组的方法实现的,那样太简单了,但是我不想那样,因为我想自己实现一个,不想用数组的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. 写这篇文章的时候心里很不踏实,总感觉哪里写的不对,希望不要误人子弟,也希望大神们能指出我的错误,能让我更加的认识数据结构与栈和队列。
关注下面的标签,发现更多相似文章
评论