棧

棧是一種遵從后進先出（LIFO）原則的有序集合。新添加或待刪除的元素都保存在棧的同一端，稱作棧頂，另一端就叫棧底。在棧里，新元素都靠近棧頂，舊元素都接近棧底。

基于數組的棧

時間復雜度O(n),占用較多的內存空間。

export interface Stack<T = any> {push(...elements: T[]): void; // 添加一個（或幾個）新元素到棧頂；pop(): T | undefined; // 移除棧頂元素，同時返回被移除的元素；peek(): T | undefined; // 返回棧頂的元素，不對棧做任何修改；isEmpty(): boolean; // 如果棧里沒有任何元素就返回true，否則返回false；clear(): void; // 移除棧里所有元素；size(): number; // 返回棧里的元素個數。
}export class Stack<T = any> implements Stack<T> {#items: T[] = [];push(...elements: T[]): void {this.#items.push(...elements);}pop(): T | undefined {return this.#items.pop();}peek(): T | undefined {return this.#items[this.#items.length - 1];}isEmpty(): boolean {return this.#items.length === 0;}clear(): void {this.#items = [];}size(): number {return this.#items.length;}
}

import { describe, test, expect } from "@jest/globals";
import { Stack } from "./index";
describe("index module", () => {test("stack", () => {const stack = new Stack<number>();stack.push(1, 2, 3);expect(stack.pop()).toBe(3);expect(stack.peek()).toBe(2);expect(stack.isEmpty()).toBe(false);expect(stack.size()).toBe(2);stack.clear();expect(stack.isEmpty()).toBe(true);expect(stack.size()).toBe(0);});
});

基于對象的棧

時間復雜度O(1),占用較少的內存空間。

export interface Stack<T = any> {push(...elements: T[]): void; // 添加一個（或幾個）新元素到棧頂；pop(): T | undefined; // 移除棧頂元素，同時返回被移除的元素；peek(): T | undefined; // 返回棧頂的元素，不對棧做任何修改；isEmpty(): boolean; // 如果棧里沒有任何元素就返回true，否則返回false；clear(): void; // 移除棧里所有元素；size(): number; // 返回棧里的元素個數。
}export class Stack<T = any> implements Stack<T> {#count: number = 0;#items: { [key: number]: T } = {};push(...elements: T[]): void {for (let index = 0; index < elements.length; index++, this.#count++) {const element = elements[index];this.#items[this.#count] = element;}}pop(): T | undefined {if (this.isEmpty()) {return undefined;}this.#count--;const result = this.#items[this.#count];delete this.#items[this.#count];return result;}peek(): T | undefined {if (this.isEmpty()) {return undefined;}return this.#items[this.#count - 1];}isEmpty(): boolean {return this.#count === 0;}clear(): void {this.#items = {};this.#count = 0;}size(): number {return this.#count;}
}

import { describe, test, expect } from "@jest/globals";
import { Stack } from "./stack-array";
describe("index module", () => {test("stack", () => {const stack = new Stack<number>();stack.push(1, 2, 3);expect(stack.pop()).toBe(3);expect(stack.peek()).toBe(2);expect(stack.isEmpty()).toBe(false);expect(stack.size()).toBe(2);stack.clear();expect(stack.isEmpty()).toBe(true);expect(stack.size()).toBe(0);});
});