【算法刷题篇】——算法入门 01 数据结构——栈（一）

🤵‍♂️ 个人主页: @北极的三哈 个人主页

👨‍💻 作者简介：CSDN内容合伙人，Python领域优质创作者。

📒 系列专栏：《牛客刷题-Python篇》《牛客刷题-SQL篇》《算法刷题篇》

🌐推荐：《牛客网》——找工作神器|笔试题库|面试经验|实习经验内推

👉 点击链接进行注册学习

算法入门 01 数据结构

AB1 【模板】栈

描述
请你实现一个栈。

操作：
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"

否则按对应操作输出。

示例1
输入：6
   push 1
   pop
   top
   push 2
   push 3
   pop
输出：1
   error
   3

代码：

class Stack:    def __init__(self): self.items = []    def isEmpty(self): return self.items == []    def push(self, item): self.items.append(item)    def pop(self): return self.items.pop()    def peek(self): return self.items[len(self.items) - 1]    def size(self): return self.items[len(self.items)]s = Stack()num = int(input())for i in range(num):    a = input()    if a[0:4] == "push": b = a.split(" ") s.push(int(b[1]))    if a == "pop": if s.isEmpty() == True:     print("error") else:     print(s.peek())     s.pop()    if a == "top": if s.isEmpty() == True:     print("error") else:     print(s.peek())

自测运行：

AB2 栈的压入、弹出序列

描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列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
输入：[1,2,3,4,5],[4,5,3,2,1]

返回值：true

说明：
可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2
输入：[1,2,3,4,5],[4,3,5,1,2]

返回值：false

说明：
由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

代码：

# -*- coding:utf-8 -*-# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可# @param pushV int整型一维数组# @param popV int整型一维数组# @return bool布尔型class Solution:    def IsPopOrder(self, pushV, popV): # stack中存入pushV中取出的数据 stack = [] while popV:     # 如果第一个元素相等，直接都弹出，根本不用压入stack     if pushV and popV[0] == pushV[0]:  popV.pop(0)  pushV.pop(0)     # 如果stack的最后一个元素与popV中第一个元素相等，将两个元素都弹出     elif stack and stack[-1] == popV[0]:  stack.pop()  popV.pop(0)     # 如果pushV中有数据，压入stack     elif pushV:  stack.append(pushV.pop(0))     # 上面情况都不满足，直接返回false。     else:  return False return True

自测运行：

保存提交：

相似企业真题

推 荐:牛客题霸-经典高频面试题库

🌐 找工作神器-|笔试题库|面试经验|大厂面试题 👉 点击链接进行注册学习