目 录CONTENT

文章目录

线性结构之-栈

Hello!你好!我是村望~!
2023-01-09 / 0 评论 / 0 点赞 / 130 阅读 / 1,150 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

线性结构之-栈

认识栈结构!

栈是一种常见的数据结构!我们知道数组也是一种线性结构,并且可以在数组的任意位置插入和删除元素!

但是有时候,我们为了实现某些功能,必须对这种任意性加以限制!而栈和队列就是比较常见的受限的线性数据结构!

下面是栈结构的示意图

JavaScript_算法与数据结构之 栈 -> Stack -> Last In First Out

数据结构——栈(Stack)(GIF图解)_wyq小白的博客-CSDN博客_数据结构栈图

从上图可以看出:

  • 其限制是仅允许在一端进行插入和删除运算,这一段通常成为栈顶,相对的把另一端叫做栈底
  • LIFO (Last in first out) 遵循 先进后出 (后进先出)的原则
  • 向一个栈插入新元素,又称作压栈,入栈或进栈
  • 向一个栈删除元素又称作出栈或退栈,把栈顶的元素删掉,使其相邻的元素成为新的栈顶

现实生活中有那些可以见到的栈结构呢?比如食堂的托盘,第一个洗好的放在最下面,最后一个洗好的放在最上面,被拿出用的时候,最后一个洗好的第一个被拿走!

函数调用栈

是否听说过,函数调用栈呢?

下面场景中函数之间相互调用:

function a(){
    b()
}

function b(){
    c()
}

function c(){
    d()
}

function d(){

}

A调用B,B中又调用C,C中又调用D.

那样在执行的过程中,

会先将A压入栈,A没有执行完,所以不会弹出栈.
在A执行的过程中调用了B,会将B压入到栈,这个时候B在栈顶,A在栈底.

如果这个时候B可以执行完,那么B会弹出栈.但是B有执行完吗?没有,
它调用了C.

所以C会压栈,并且在栈顶.而C调用了D,D会压入到栈顶.口所以当前的栈顺序是:

栈顶A->B->C->D栈顶
D执行完,弹出栈.C/B/A依次弹出栈.

所以我们有函数调用栈的称呼,就来自于它们内部的实现机制.(通过栈来实现的)

栈常见面试题

  • 有六个元素6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列? C
    • A. 5 4 3 6 1 2
    • B. 4 5 3 2 1 6
    • C. 3 4 6 5 2 1
    • D. 2 3 4 1 5 6

注意这个不是要你一次性压栈,可以边压栈边出栈,不然答案就只有一个 1,2,3,4,5,6了

栈结构封装

实现栈有两种比较常见的方式!

  • 基于数组
  • 基于链表

这里就先基于数组来实现!

interface IStack<T> {
  items: T[];
  push(ele: T): void; // 压栈
  pop(): T; // 出栈 并返回出栈的元素
  peek(): T; // 查看栈顶元素
  size(): number; // 查看栈元素数量
  toString(inline?: boolean): string; // 字符串查看方法
  isEmpty(): boolean; // 是否为空
}

export class Stack<T> implements IStack<T> {
  items: T[] = [];

  pop(): T {
    const last = this.peek();
    this.items.pop();
    return last;
  }

  push(ele: T): void {
    this.items.push(ele);
  }

  peek(): T {
    return this.items[this.items.length - 1];
  }

  size(): number {
    return this.items.length;
  }

  toString(inline: boolean = false): string { 
    // inline 控制打印 是否换行!
    let str = "";
    for (let i = this.items.length - 1; i >= 0; i--) {
      str += this.items[i] + (inline ? "" : "\n");
    }
    return str;
  }

  isEmpty(): boolean {
    return this.items.length === 0;
  }
}

代码测试!

import { Stack } from "./1. Stack/index";

const s1 = new Stack<number>();

// 压栈
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);

console.log(s1.toString());
console.log("栈顶", s1.peek());

s1.pop();
console.log("一次弹出栈");

console.log(s1.toString());

console.log("栈大小",s1.size());
console.log("栈是否为空",s1.isEmpty());

测试结果

10:39:11 - Found 0 errors. Watching for file changes.
4
3
2
1

栈顶 4
一次弹出栈
3
2
1

栈大小 3
栈是否为空 false

利用栈数据结构完成十转二进制算法

import { Stack } from "./index";

export default function (dec: number) {
  let s = new Stack<number>();
  while (dec > 0) {
    // 到后面小于 1 向下取整为0
    s.push(dec % 2);
    dec = Math.floor(dec / 2);
  }
  let res = "";

  while (!s.isEmpty()) {
    res += s.pop();
  }
  return res;
}

代码测试

import DecimalToBinary from "./1. Stack/DecimalToBinary";

const res0 = DecimalToBinary(10);
const res1 = DecimalToBinary(100);
const res2 = DecimalToBinary(1000);
const res3 = DecimalToBinary(10000);
console.log(res0); // 1010
console.log(res1); // 1100100
console.log(res2); // 1111101000
console.log(res3); // 10011100010000
0

评论区