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

Posted on | Edited on | In

栈

栈 是一种按照 后进先出(LIFO, Last In First Out) 的原理运作的一种特殊串列形式的数据结构,　推入和弹出的元素都是在栈的顶端, 称为 栈顶元素

栈

创建栈

首先, 我们用链表的结构创建栈, 先定义栈元素的节点

1
2
3
4
function Node(data) {
  this.data = data;
  this.next = null;
}

定义栈的类

1
2
3
4
function Stack() {
  this.top = null;  // 栈顶指针
  this.length = 0;  // 记录栈的长度
}

实现栈的操作

栈有两种基本操作: 入栈(push)和出栈(pop)

  • 入栈: 将节点元素加入栈的顶端, 栈顶指针向后移动一位, 栈长加一
  • 出栈: 将节点元素从栈的顶端删除, 栈长减一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 入栈
Stack.prototype.push = function(data) {
  var node = new Node(data);

  node.next = this.top;
  this.top = node;  // 栈顶移动至新的节点元素
  this.length++;
};

// 出栈
Stack.prototype.pop = function() {
  if (!this.top) {
    return false;
  } else {
    this.top = this.top.next;
    this.length--;
  }
};

更多关于栈的操作实现代码

队列

队列 是一种 先进先出(FIFO, First In First Out) 的线性表, 队列只允许在后端插入元素, 在前端进行删除元素

队列

创建队列

在这里, 我们依然用链表的形式实现队列, 首先先定义队列的类, 其包括指向队列前端front的属性和指向队列末端rear的属性

1
2
3
4
5
function Queue() {
  this.front = null;  // 指向队列前端
  this.rear = null;  // 指向队列末端
  this.length = 0;  // 队列长度
}

实现队列的操作

队列也有两种基本操作: 入队(enqueue)和出队(dequeue), 按照先进先出的原则实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 入队
Queue.prototype.enqueue = function(data) {
  var node = new Node(data);

  if (!this.rear) {
    this.front = node;
    this.rear = node;
  }

  this.rear.next = node;
  this.rear = node;
  this.length++;
};

// 出队
Queue.prototype.dequeue = function() {
  if (!this.front) {
    console.log("Queue is empty!");
  }

  var e = this.front.data;  // 出队列的元素
  this.front = this.front.next;

  return e;
};

更多关于队列的操作实现代码