栈
栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。 后进者先出,先进者后出,这就是典型的“栈”结构。
当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。
实际上,栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈。
用数组实现的栈
class Stack {
constructor() {
this.items = [];
this.count = 0;
}
push(value) {
this.items.push(value);
++this.count;
return this.items;
}
pop() {
if (this.count === 0) return [];
return this.items.pop();
}
size() {
return this.items.length;
}
isEmpty() {
return this.items.length === 0;
}
peek() {
//返回栈顶的元素
if (this.isEmpty()) {
return undefined;
}
return this.items[this.count - 1];
}
clear() {
this.items.length = 0;
}
}
var stack = new Stack();
stack.push("Jack");
stack.push("Mike");
stack.push("Candy");
stack.print(); // Jack,Mike,Candy
stack.pop();
用 js 对象实现的栈
class Stack {
constructor() {
this.count = 0;
this.items = {}; // 选择对象来保存栈中元素
}
// 入栈
push(element) {
this.items[this.count] = element;
this.count++;
}
size() {
return this.count;
}
isEmpty() {
return this.count === 0;
}
// 出栈
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];
}
clear() {
this.items = {};
this.count = 0;
}
}
这里为什么使用对象来保存栈中元素?
因为在使用数组时,大部分方法的时间复杂度是 O(n)。
并且数组是元素的一个有序集合,为了保证元素排列有序,它会占用更多的内存空间。
用链表实现的栈
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class StackBasedLinkedList {
constructor() {
this.top = null;
}
push(value) {
const node = new Node(value);
if (this.top === null) {
this.top = node;
} else {
node.next = this.top;
this.top = node;
}
}
pop() {
if (this.top === null) {
return -1;
}
const value = this.top.element;
this.top = this.top.next;
return value;
}
// 为了实现浏览器前进后退
clear() {
this.top = null;
}
display() {
if (this.top !== null) {
let temp = this.top;
while (temp !== null) {
console.log(temp.element);
temp = temp.next;
}
}
}
}
// Test
const newStack = new StackBasedLinkedList();
newStack.push(1);
newStack.push(2);
newStack.push(3);
// 获取元素
let res = 0;
console.log("-------获取pop元素------");
while (res !== -1) {
res = newStack.pop();
console.log(res);
}
不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)
栈在函数调用中的应用
操作系统给每个线程分配了一块独立的内存空间,这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数,就会将临时变量作为一个栈帧入栈,当被调用函数执行完成,返回之后,将这个函数对应的栈帧出栈。
栈在表达式求值中的应用
编译器就是通过两个栈来实现的。其中一个保存操作数的栈,另一个是保存运算符的栈。
我们从左向右遍历表达式,当遇到数字,我们就直接压入操作数栈;当遇到运算符,就与运算符栈的栈顶元素进行比较。如果比运算符栈顶元素的优先级高,就将当前运算符压入栈;如果比运算符栈顶元素的优先级低或者相同,从运算符栈中取栈顶运算符,从操作数栈的栈顶取 2 个操作数,然后进行计算,再把计算完的结果压入操作数栈,继续比较。
栈在括号匹配中的应用
当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。
原文链接: https://jesse121.github.io/blog/articles/2020/05/02.html
版权声明: 转载请注明出处.