Skip to content

栈结构

线性结构

线性结构(Linear List)是由 n(n>=0)个数据元素(结点)a[0]、a[1]、a[2]...a[n-1]组成的有限序列

  • 数据元素的个数 n 定义为表的长度=list.length()list.length()=0 时称为空表)
  • 将非空的线性表(n>=1)记作:(a[0]、a[1]、a[2]...a[n-1])
  • 数据元素 a[i](0<=i<=n-1)只是个抽象符号,其具体含义在不同情况下可以不同

上面是维基百科对于线性结构的定义,有一点点抽象,其实我们只需要记住几个常见的线性结构即可

  • 数据结构(Array)
  • 栈结构(Stack)
  • 队列结构(Queue)
  • 链表结构(LinkedList)

数组

  • 几乎每种编程语言都会提供一种原生数据结构
  • 并且我们可以借助数组结构来实现其他的数据结构,比如栈(Stack)、队列(Queue)、堆(Heap)

通常数组的内存是连续的,所以数组在知道下标值的情况下,访问效率是非常高的

image-20230519101401245

栈结构

  • 栈也是一种非常常见的数据结构,并且在程序中的应用非常广泛
  • 数组
    • 我们知道数组是一种 线性结构,并且可以在数组的 任意位置 插入和删除数据
    • 但是有时候,我们为了实现某些功能,必须对这种 任意性 加以 限制
    • 栈和队列 就是比较常见的受限的线性结构

image-20230519102813445

栈(Stack),它是一种受限的数据结构,后进先出(LIFO)

  • 其限制是仅允许在 表的一端 进行插入和删除运算。这一端被称为 栈顶,相对地,把另一端称为 栈底
  • LIFO(last in first out)表示就是后进入的元素,第一个弹出栈空间。类似于自动餐托盘,最后放上的托盘,往往先把它拿出去使用
  • 向一个栈插入新元素又称作 进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为栈顶元素
  • 从一个栈删除元素又称作出 栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素

题目

有六个元素 6、5、4、3、2、1 的顺序进栈,问下面哪一个不是合法的出栈序列?

  • 5、4、3、6、1、2
  • 4、5、3、2、1、6
  • 3、4、6、5、2、1 ×
  • 2、3、4、1、5、6

实现栈结构有两种比较常见的方式:

  • 基于数组实现
  • 基于链表实现

实现栈

  • 创建一个 Stack,用户创建栈的类,可以顶一个泛型类
  • 在构造函数中,定义了一个变量(数组类型),这个变量可以用于保存当前栈对象中所有的元素
  • 之后不论是压栈操作还是出栈操作,都是从数组中添加和删除元素
typescript
class Stack<T> {
  private data: T[] = []
}

在 node 环境下执行 ts 代码

bash
$ npm i -g ts-node

栈的操作

  • push(element):添加一个新元素到栈顶位置
  • pop():移除栈顶的元素,同时返回被移除的元素
  • peek():返回栈顶的元素,不会对栈做任何修改
  • isEmpty():如果栈里面没有任何元素就返回 true,否则返回 false
  • size():返回栈里的元素个数。这个方法和数组的 length 属性很类似
typescript
class ArrayStack {
  private data: any[] = []
  // push:将一个元素压入栈中
  push(element: any) {
    this.data.push(element)
  }
  // pop:将栈顶元素弹出栈(返回出去,并且从栈顶移除)
  pop(): any {
    return this.data.pop()
  }
  // peek:看一眼栈顶元素,但是不进行任何操作
  peek(): any {
    return this.data[this.data.length - 1]
  }
  // isEmpty:判断栈是否为空
  isEmpty(): boolean {
    return this.data.length === 0
  }
  // size:返回栈的数据个数
  size(): number {
    return this.data.length
  }
}

const stack1 = new ArrayStack()
stack1.push('aaa')
stack1.push('bbb')

console.log(stack1.peek())
console.log(stack1.pop())
console.log(stack1.pop())
console.log(stack1.isEmpty())
console.log(stack1.size())

泛型重构栈

typescript
class ArrayStack<T> {
  private data: T[] = []
  push(element: T) {
    this.data.push(element)
  }
  pop(): T | undefined {
    return this.data.pop()
  }
  peek(): T | undefined {
    return this.data[this.data.length - 1]
  }
  isEmpty(): boolean {
    return this.data.length === 0
  }
  size(): number {
    return this.data.length
  }
}

接口抽离和封装

typescript
import { IStack } from './IStack'

class LinkedStack<T> implements IStack<T> {
  private data: T[] = []
  push(element: T) {
    this.data.push(element)
  }
  pop() {
    return this.data.pop()
  }
  peek() {
    return this.data[this.data.length - 1]
  }
  isEmpty() {
    return this.data.length === 0
  }
  size() {
    return this.data.length
  }
}

使用接口定义栈的结构

typescript
interface IStack<T> {
  push(element: T): void
  pop(): T | undefined
  peek(): T | undefined
  isEmpty(): boolean
  size(): number
}

export { IStack }

栈结构题

十进制转二进制

为什么需要十进制转二进制

  • 现实生活中,我们主要使用十进制
  • 在计算机科学中,二进制非常重要,因为计算机里所有内容都是二进制数字表示的(0 和 1)
  • 没有十进制和二进制相互转换的能力,与计算机交流就很困难
  • 转换二进制是计算机科学和编程领域中经常使用的算法

如何实现十进制转二进制

  • 要把十进制转换成二进制,我们可以将十进制数字和 2 整除(二进制是满二进一),直到结果是 0 为止
typescript
import ArrayStack from './stack_refactor'

function decimalToBinary(decimal: number): string {
  // 1.创建一个栈,用于存放余数
  const stack = new ArrayStack<number>()

  // 2.使用循环 while(不确定次数,只知道循环结束条件) for(知道循环的次数)
  while (decimal > 0) {
    const result = decimal % 2
    stack.push(result)
    decimal = Math.floor(decimal / 2)
  }

  // 3.所有的余数都已经放在 stack 中,依次取出即可
  let binary = ''
  while (!stack.isEmpty()) {
    binary += stack.pop()
  }
  return binary
}

有效括号

20.有效括号

给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效

有效字符串需满足:

  • 左括号必须用相同类型的右括号闭合
  • 左括号必须以正确的顺序闭合
  • 每个右括号都有一个对应的相同类型的左括号
typescript
import ArrayStack from './stack_refactor'

function isValid(s: string): boolean {
  // 创建栈结构
  const stack = new ArrayStack<string>()
  // 2.遍历s中所有的括号
  for (let i = 0; i < s.length; i++) {
    const c = s[i]
    switch (c) {
      case '(':
        stack.push(')')
        break
      case '{':
        stack.push('}')
        break
      case '[':
        stack.push(']')
        break
      default:
        if (c !== stack.pop()) return false
        break
    }
  }
  return stack.isEmpty()
}

常备不懈,才能有备无患