# JS数据结构

**Repository Path**: weiaigewang/js-data-structure

## Basic Information

- **Project Name**: JS数据结构
- **Description**: 个人自己学习的js数据结构
- **Primary Language**: JavaScript
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 2
- **Forks**: 0
- **Created**: 2021-03-28
- **Last Updated**: 2022-12-08

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# 一、JS数据结构

## 1、介绍
个人js数据结构学习

# 二、线性结构

## 1、数组
## 2、链表

# 三、栈（stack）

## 3.1、概念
栈（stack）又名堆栈，它是一种运算受限的线性表。**限定仅在表尾进行插入和删除操作的线性表**。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

![栈的示意图](https://segmentfault.com/img/remote/1460000018032192)

## 3.2栈的操作

- push(): 添加新元素到栈顶
- pop(): 移除栈顶的元素，同时返回被移除的元素
- peek(): 返回栈顶的元素，不对栈做任何修改
- isEmpty(): 如果栈里没有任何元素就返回true，否则返回false
- clear(): 移除栈里的所有元素
- size(): 返回栈里的元素个数

## 3.3栈的示意操作
![栈的示意操作](https://segmentfault.com/img/remote/1460000018032193)

## 3.4代码实现
```javascript
function Stack() {
  let items = []
  // 添加元素到栈顶，也就是栈的末尾
  this.push = function (element) {
    items.push(element)
  }
  // 栈的后进先出原则，从栈顶出栈
  this.pop = function () {
    return items.pop()
  }
  // 查看栈顶的元素，访问数组最后一个元素
  this.peek = function () {
    return items[items.length - 1]
  }
  // 检查栈是否为空
  this.isEmpty = function () {
    return items.length == 0
  }
  // 返回栈的长度，栈的长度就是数组的长度
  this.size = function () {
    return items.length
  }
  // 清空栈 
  this.clear = function () {
    items = []
  }
  // 打印栈元素
  this.print = function () {
    console.log(items.toString())
  }
}
```
ES6的实现
```javascript
class Stack {
  constructor () {
    this.items = []
  }
  push (element) {
    this.items.push(element)
  }
  pop () {
    return this.items.pop()
  }
  peek () {
    return this.items[items.length - 1]
  }
  isEmpty () {
    return this.items.length == 0
  }
  size () {
    return this.items.length
  }
  clear () {
    this.items = []
  }
  print () {
    console.log(this.items.toString())
  }
}
let stack = new Stack()
stack.push(1)
console.log(stack.isEmpty())
stack.print()
```

## 3.5栈的应用
栈的应用场景非常广泛，例如：存储访问过的任务或路径、撤销的操作
- 1、将一个10进制8转化为2进制数的过程，接下来看看用栈是如何实现的

```javascript
function conver(num, radix) {
  let stack = new Stack()
  let binaryString = ''
  let digits = '0123456789ABCDEF'
  while (num > 0) {
    stack.push(num % radix)
    num = parseInt(num / radix)
  }
  while (!stack.isEmpty()) {
    binaryString += digits[stack.pop()]
  }
  console.log(binaryString)
}
conver(8, 2) // 1000
```