前端数据结构--线性结构-队列、栈

2021年11月26日 阅读数:4
这篇文章主要向大家介绍前端数据结构--线性结构-队列、栈,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

  栈是一种特殊的的线性表结构,只容许在一端插入和删除操做。容许插入和删除的一端是栈顶,另外一端是栈底,不包含任何数据的叫空栈,栈具备后进者先出(Last in first out)简称LIFO,栈的操做主要有入栈、出栈 如数组

线性表、链表都是线性结构中的一种,只是存储方式不同,叫不一样的名称。浏览器

实现栈

  栈既能够用数组来实现,也能够用链表来实现。用数组实现的栈,叫做顺序栈,用链表实现的栈,叫做链式栈。数据结构

 1 /*
 2  栈:只能在栈的一边进行插入、删除操做,具备后进先出的特色
 3  用数组实现的栈,叫做顺序栈、用链表实现的栈,叫做链式栈。
 4  */
 5 
 6 class Stack {
 7   constructor () {
 8     this.size = 0
 9     this.stackList = []
10   }
11   // 入栈
12   pushStack (data) {
13     this.stackList.unshift(data)
14     this.size++
15     return true
16   }
17   // 出栈
18   popStack () {
19     if (this.size < 0) return false
20     this.stackList.shift()
21     this.size--
22   }
23   get length () {
24     return this.size
25   }
26 }
27 
28 let stack = new Stack()
29 stack.pushStack(1)
30 stack.pushStack(2)
31 stack.pushStack(3)
32 console.log(stack)
33 console.log(stack.length)
34 
35 stack.popStack()
36 
37 console.log(stack)
38 console.log(stack.length)

在线 codepen函数

应用场景

当某个数据集合须要在一端插入和删除操做,而且知足后进先出、先进后出的特性,那么应该用栈这种数据结构。flex

浏览器的前进、后退功能

  浏览器的前进后退基本原理很简单,使用两个栈X、Y,在浏览的时候把数据压入X栈,当点击后退的时候从X中出栈,且把数据压入Y栈。当点击前进的时候把Y栈中的数据出栈,而后再压入X栈。当栈 X 中没有数据时,那就说明没有页面能够继续后退浏览了。当栈 Y 中没有数据,那就说明没有页面能够点击前进按钮了。this

还有不少应用场景,好比 撤销回退、js 执行的函数调用栈、递归调用栈等等。spa

队列

  队列与栈结构相似一样是一种特殊的的线性表结构,不一样的是队列只容许在一端进行插入操做,在另外一端进行删除操做,好比生活中的排队买票,等电梯等先来的先上,后来的人只能依次排队,不容许插队。队列具备先进者先出的特色。code

实现队列

  队列跟栈同样,也是一种抽象的数据结构。它具备先进先出的特性,支持在队尾插入元素,在队头删除元素,队列既能够用数组来实现,也能够用链表来实现。用数组实现的栈,叫做顺序队列,用链表实现的栈,叫做链式队列。orm

 1 /*
 2   队列:只能在栈的一边进行插入、另一边进行删除操做,具备先进先出的特色
 3   用数组实现的栈,叫做顺序队列、用链表实现的栈,叫做链式队列。
 4  */
 5 class QueueList {
 6   constructor () {
 7     this.size = 0
 8     this.queueList = []
 9   }
10   // 入队
11   enqueue (data) {
12     this.queueList.push(data)
13     this.size++
14   }
15   // 出队
16   dequeue () {
17     if (this.size < 0) return false
18     this.queueList.shift()
19     this.size--
20   }
21   clear () {
22     this.queueList = []
23   }
24   get length () {
25     return this.size
26   }
27   get isEmptyQueue () {
28     return !this.queueList.length
29   }
30 }
31 let queue = new QueueList()
32 queue.enqueue(1)
33 queue.enqueue(2)
34 queue.enqueue(3)
35 queue.dequeue()
36 
37 console.log(queue)
38 console.log(queue.length)

在线 codepenblog

队列的概念很好理解,基本操做也很容易掌握。

队列与栈

  • 栈:先进后出
  • 队列:先进先出