线性结构之-栈

认识栈结构！

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

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

下面是栈结构的示意图

从上图可以看出：

• 其限制是仅允许在一端进行插入和删除运算，这一段通常成为栈顶，相对的把另一端叫做栈底
• 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