（一）栈结构、队列结构

01-线性结构-数组-栈结构

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

数组

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

可在数组的任意位置插入和删除数据

栈结构

简介

• 是一种受限的线性结构，先进后出
• 仅允许在表的一端进行插入和删除运算，即栈顶；另一端为栈底。
• 必须按照顺序来进出栈

习题练习：

题目

有六个元素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

答案解析：

A：65进栈，5出栈，4进栈出栈，3进栈出栈，6出栈，21进栈，1出栈，2出栈

B：654进栈，4出栈，5出栈，3进栈出栈，2进栈出栈，1进栈出栈，6出栈

D：65432进栈，2出栈，3出栈，4出栈，1进栈出栈，5出栈，6出栈

实现栈结构

// 封装一个栈
class ArrayStack {// 定义一个数组/链表。用于存储数据private data: any[] = []// 实现栈中相关的操作方法// 1.push方法：将一个元素压入到栈中push(element: any):void {this.data.push(element)}// 2.pop方法：将栈顶的元素弹出栈（返回出去，并且移除该项）pop():any {return this.data.pop()}// 3peek方法：看一眼栈顶元素，但是不进行任何操作peek(): any {return this.data[this.data.length - 1]}// 4.isEmpty：判断栈是否为空isEmpty(): boolean {return this.data.length === 0}// 5.size：返回栈的数据个数size(): number {return this.data.length}
}

对上述代码进行测试：

// 创建stack实例
const stack1 = new ArrayStack()
stack1.push("aaa")
stack1.push("bbb")
stack1.push("ccc")console.log(stack1.peek());//ccc
console.log(stack1.pop());//ccc
console.log(stack1.pop());//bbb
console.log(stack1.pop());//aaaconsole.log(stack1.isEmpty());//true
console.log(stack1.size());//0

相关应用

十进制转二进制

import ArrayStack from "./02-实现栈结构Stacks(重构)"function decimalToBinary(decimal: number): string {// 1.创建一个栈，用于存放余数const stack = new ArrayStack<number>()/* 2.使用循环 // while:不确定次数，只知道循环结束跳转// for:知道循环的次数*/while(decimal > 0) {const result = decimal % 2stack.push(result)decimal = Math.floor(decimal / 2)}//  3.所有的余数都已经放在stack中，依次取出即可let binary = ''while(!stack.isEmpty()) {binary += stack.pop()}return binary
}console.log(decimalToBinary(35));//100011
console.log(decimalToBinary(100));//1100100

有效的括号

20. 有效的括号 - 力扣（LeetCode）（考察栈）

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

解题：

import ArrayStack from "./02-实现栈结构Stacks(重构)"function isValid(s:string): boolean {// 1.创建一个栈结构const stack = new ArrayStack<string>()// 2.变量s中的所有括号for(let i = 0; i < s.length; i++) {const c = s[i]switch(c) {case "(":stack.push(")")breakcase "{":stack.push("}")breakcase "[":stack.push("]")breakdefault:if(c !== stack.pop()) return falsebreak}}return stack.isEmpty()
}console.log(isValid("()"));
console.log(isValid("()[]{}["));

02-队列结构-面试题

• 队列（queue)是一种先进先出的线性结构
• 数据元素按照顺序依次进入队列，最先进入的元素最先离开队列
• 类似于现实中的排队场景，比如排队买票，先到的人先离开队列
• 常见的队列结构

实现队列结构

1.定义队列结构接口

interface IQueue<T> {// 入队方法enqueue(element: T): void// 出队方法dequeue(): T | undefined// peek 方法peek(): T | undefined// 判断是否为空isEmpty(): boolean// 元素个数size(): number
}export default IQueue

2.实现队列结构

import IQueue from "./IQueue"
class ArrayQueue<T> implements IQueue<T> {// 内部通过数组或链表保存数据private data: T[] = []enqueue(element: T): void {this.data.push(element)}dequeue(): T | undefined {return this.data.shift()}peek(): T | undefined {return this.data[0]}isEmpty(): boolean {return this.data.length === 0}size(): number {return this.data.length}
}export default ArrayQueue

3.测试代码：

import ArrayQueue from "./01-实现队列结构";const queue = new ArrayQueue<number>()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
console.log(queue.dequeue());//1
console.log(queue.dequeue());//2
console.log(queue.size());//1

击鼓传花

要求：一群人围成一圈，获取最后剩下的人位置或名字

import ArrayQueue from "./01-实现队列结构"
function hotPotatao (names:string[],num:number) {if(names.length === 0) return -1// 创建队列结构const queue = new ArrayQueue<string>()// 2.将所有name入队操作for (const name of names) {queue.enqueue(name)}// 3.淘汰的规则while(queue.size()>1){// 1、2淘汰for(let i = 1;i<num; i++) {const name = queue.dequeue()if(name) queue.enqueue(name)}// 3淘汰queue.dequeue()}// return queue.dequeue()const Leftname = queue.dequeue()!// 拿到当前名字的索引return names.indexOf(Leftname)
}const leftName = hotPotatao(["张三","李四","王五","赵六","钱七"],3)
console.log(leftName);

约瑟夫环

0，1，...,n-1个数字围城一个圈，从数字0开始，每次删除圆圈中第m个数字（删除后从下一个数字计数）。求该圆圈剩下的最后一个数字。

import ArrayQueue from "./01-实现队列结构"
function lastRemaining(n:number,m:number) {// 输入参数校验if (n <= 0 || m <= 0) {throw new Error("参数 n 和 m 必须大于 0");}// 1.创建队列const queue = new ArrayQueue<number>()// 2.将所有数组加入到队列中for (let i = 0; i < n; i++) {queue.enqueue(i)}// 3.判断队列中是否还有数字while(queue.size()>1) {for(let i = 1; i<m; i++) {queue.enqueue(queue.dequeue()!)}queue.dequeue()}return queue.dequeue()!
}console.log(lastRemaining(5,3));//3console.log(lastRemaining(10,17));//2

动态规划思想实现：

function lastRemainingOptimized(n: number, m: number): number {if (n <= 0 || m <= 0) {throw new Error("参数 n 和 m 必须大于 0");}let result = 0;for (let i = 2; i <= n; i++) {result = (result + m) % i;}return result;
}// 测试用例
console.log(lastRemainingOptimized(5, 3)); // 输出: 3
console.log(lastRemainingOptimized(10, 17)); // 输出: 2