当前位置：首页 > news >正文

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

news 来源：原创 2024/5/3 19:21:04

在这里插入图片描述

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

👨‍💻 作者简介：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