为什么要使用栈

我们可以在数组的任意位置上删除和添加元素。然而，有时候还需要一种能在添加或删除元素时进行更多控制的数据结构，有两种类似于数组的数据结构在添加和删除元素时更为可控，就是栈和队列。

栈的概念

栈是一种遵从后进先出(LIFO)即Last_Input_First_Out原则的有序集合。新添加或待删除的元素都保存在栈的同一端，称作栈顶，另一端就叫栈底。在栈里，新元素都靠近栈顶，旧元素都接近栈底。如果你把书堆叠起来，上面的书会比下面的书先拿。或者当你在网上浏览时，后退按钮会引导你到最近浏览的页面。

栈也被用在编程语言的编译器和内存中保存变量和方法调用等。

创建一个基于数组的栈

创建一个类StackArray用来表示用数组创建的栈。

class StackArray<T> {
  constructor() {
  }
}
//使用泛型，因为不确定，我们后面传入进来的元素属于什么类型。

这样我们有了一个StackArray类来表示栈，但是我们还需要一种数据结构来保存栈里的元素。可以选择数组。数组允许我们在任何位置添加或删除元素。由于栈遵循LIFO原则，需要对元素的插入和删除功能进行限制。

class StackArray<T> {
  private items: T[];

  constructor() {
    this.items = []; //选择数组作为栈存储元素的基础结构
  }
}

为栈声明方法

1. push(element(s)):添加一个(或几个)新元素到栈顶。
2. pop():移出栈顶的元素，同时返回被移出的元素。
3. peek():返回栈顶的元素，不对栈做任何修改(该方法不会移出栈顶的元素，仅仅返回它)。
4. isEmpty():如果栈里没有任何元素就返回true，否则就返回false。
5. clear():移出栈里的所有元素。
6. size():返回栈里的元素个数。该方法和数组的length属性很类似。

/**
 * description: StackArray
 * date: 2022/4/7 20:15
 * author: xinyu
 * version: 1.0
 */
class StackArray<T> {
    private items: T[];

    constructor() {
        this.items = [];
    }

    push(element: T) {
        this.items.push(element);
    }

    pop() {
        return this.items.pop();
    }

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

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

    size() {
        return this.items.length;
    }
    
    clear() {
        this.items = [];
    }

    toArray() {
        return this.items;
    }

    toString() {
        return this.items.toString();
    }
}

简单使用

/**
 * description: useStackArray
 * date: 2022/4/7 20:38
 * author: xinyu
 * version: 1.0
 */
import StackArray from "./StackArray";

let stackArray = new StackArray<number>();//创建一个只能操作number的对象

console.log(stackArray.isEmpty());//检查栈是否为空,因为什么也没添加 所以为true

stackArray.push(5); //栈里添加元素
stackArray.push(8);

console.log(stackArray.peek()); //8

console.log(stackArray.size()) // 2

console.log(stackArray.isEmpty()); // 因为添加了两个元素 所以为false

创建一个基于对象的栈

如果数组的元素很多的话，运算需要的时间会很长，因为数组是元素的一个有序集合，为保证元素的有序排列，会占更多的内存空间。

直接获取元素，占用较少的内存空间，并且仍然保证所有元素按照我们的需要排列，就可以使用对象来存储所有的栈元素。

StackObj类：

/**
 * description: StackObj
 * date: 2022/4/7 21:13
 * author: xinyu
 * version: 1.0
 */
export default class StackObj<T> {
    private count: number; //count属性用来记录栈的大小
    private items: any;

    constructor() {
        this.count = 0;
        this.items = {};
    }

    push(element: T) {
        this.items[this.count] = element;
        this.count++;
    }

    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        this.count--;
        const result = this.items[this.count];
        delete this.items[this.count];
        return result;
    }

    peek() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items[this.count - 1];
    }

    isEmpty() {
        return this.count === 0;
    }

    size() {
        return this.count;
    }

    clear() {
        this.items = {};
        this.count = 0;
    }

    toString() {
        if (this.isEmpty()) {
            return '';
        }
        let objString = `${this.items[0]}`;
        for (let i = 1; i < this.count; i++) {
            objString = `${objString},${this.items[i]}`;
        }
        return objString;
    }
}

基于对象的栈的使用和上面数组的差不多。