【算法训练营】--》读懂 数据结构——栈

简介: 读懂 数据结构——栈

什么是栈?

栈(stack)又名堆栈,它是一种运算受限的线性表。限定权在表尾进行插入和删除操作的线性表。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。

栈【模板】

push x:将 加x x\ x 入栈,保证 x x\ x 为 int 型整数。

pop:输出栈顶,并让栈顶出栈

top:输出栈顶,栈顶不出栈

输入描述:

第一行为一个正整数 n n\ n ,代表操作次数。(1≤n≤100000)(1 \leq n \leq 100000)(1≤n≤100000)

接下来的 n n\ n ,每行为一个字符串,代表一个操作。保证操作是题目描述中三种中的一种。

输出描述:

如果操作为push,则不输出任何东西。

如果为另外两种,若栈为空,则输出 "error“否则按对应操作输出。

letstack= [];
lettop=-1;
while ((line=readline())) {
vararr=line.split(" ");
// 将循环的次数跳过  if (!isNaN(parseInt(arr[0]))) {
continue;
  }
if (arr.length===2) {
stack[++top] =arr[1];
  } elseif (arr[0] ==="pop") {
if (top===-1) {
console.log("error");
    } else {
console.log(stack[top--]);
    }
  } else {
if (top===-1) {
console.log("error");
    } else {
console.log(stack[top]);
    }
  }
}

栈的压入、弹出系列

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

示例:

输入:[1,2,3,4,5],[4,5,2,3,1]

返回:true

说明:可以通过

push(1)=>push(2)=>(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()

这样的顺序得到[4,5,3,2,1]这个序列,返回true。

functionIsPopOrder(pushV, popV)
{
// write code hereletstack= []
for (letnodeofpushV){
stack.push(node);
while (stack[stack.length-1] ===popV[0]){
stack.pop();
popV.shift();
if (popV.length===0) returntrue;
        }
    }
while (stack.pop() ===popV.shift()){
if (popV.length===0) returntrue;
    };
returnfalse;
}
module.exports= {
IsPopOrder : IsPopOrder};

有效括号序列

给出一个仅包含字符'(',')','{','}','['和']',的字符串,判断给出的字符串是否是合法的括号序列

括号必须以正确的顺序关闭,"()"和"()[]{}"都是合法的括号序列,但"(]"和"([)]"不合法。

数据范围:字符串长度 0≤n≤100000\le n \le 100000≤n≤10000

要求:空间复杂度 O(n)O(n)O(n),时间复杂度 O(n)O(n)O(n)

示例:

输入:"()[]{}"

返回值:true

/**  *   * @param s string字符串   * @return bool布尔型  */functionisValid( s ) {
// write code hereconsttruely= ["()","[]","{}"]
functioncheck() {  
constcheckList=truely.filter( item=> {
returns.indexOf( item ) >-1        })
returncheckList.length    }
while(  check() >0 ) {
truely.forEach( item=> {
s=s.replace( item, "" )
        })
    }
if( s.length>0 ) {
returnfalse    }else {
returntrue    }
}
module.exports= {
isValid : isValid};

逆波兰表达式求值

给定一个逆波兰表达式,求表达式的值。

数据范围:表达式长度满足 1≤n≤104 1 \le n \le 10^4 \ 1≤n≤104  ,表达式中仅包含数字和 + ,- , * , / ,其中数字的大小满足 ∣val∣≤200 |val| \le 200 \ ∣val∣≤200 。

示例:

输入:["2","1","+","4","*"]

返回值:12

/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * *  * @param tokens string字符串一维数组  * @return int整型 */functionevalRPN( tokens ) {
// write code herevarstack= [];
for (leti=0;i<tokens.length;i++)
        {
if(tokens[i]!=='+'&&tokens[i]!=='-'&&tokens[i]!=='*'&&tokens[i]!=='/')
stack.push(parseInt(tokens[i]));
else {
letb=stack.pop()
leta=stack.pop()
switch(tokens[i]){
case'+' :
stack.push(a+b)
breakcase'-':
stack.push(a-b)
breakcase'*':
stack.push(a*b)
breakcase'/':
stack.push(parseInt(a/b))
break                }
            }
        }
returnstack.pop();
}
module.exports= {
evalRPN : evalRPN};

点击消除

牛牛拿到了一个字符串。

他每次“点击”,可以把字符串中相邻两个相同字母消除,例如,字符串"abbc"点击后可以生成"ac"。

但相同而不相邻、不相同的相邻字母都是不可以被消除的。

牛牛想把字符串变得尽可能短。他想知道,当他点击了足够多次之后,字符串的最终形态是什么?

输入描述:

一个字符串,仅由小写字母组成。(字符串长度不大于300000)

输出描述:

一个字符串,为“点击消除”后的最终形态。若最终的字符串为空串,则输出0。

示例:

输入:abbc

输出:ac

conststr=readline();
constinarr=str.split("");
constarr= [];
for( leti=0, l=inarr.length; i<l; i++ ) {
constitem=inarr[i];
if( i>0&&item===arr[arr.length-1] ) {
arr.pop()
    }else {
arr.push( item )
    }
}
if( arr.length>0 ) {
print(arr.join(""))
}else {
print(0)
}

表达式求值

请写一个整数计算器,支持加减乘三种运算和括号。

数据范围:0≤∣s∣≤1000\le |s| \le 1000≤∣s∣≤100,保证计算结果始终在整型范围内

要求:空间复杂度: O(n)O(n)O(n),时间复杂度 O(n)O(n)O(n)

示例:

输入:"1+2"

输出:3

/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * 返回表达式的值 * @param s string字符串 待计算的表达式 * @return int整型 */functionsolve( s ) {
// write code herereturneval(s)
}
module.exports= {
solve : solve};


目录
打赏
0
0
0
0
7
分享
相关文章
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
21 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
98 9
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
116 3
 算法系列之数据结构-Huffman树
|
6月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
297 77
|
4月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
105 22
|
5月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
74 11
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
139 29
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
195 25

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问