首页 > 试题广场 >

设计getMin功能的栈

[编程题]设计getMin功能的栈
  • 热度指数:14753 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
实现一个特殊功能的栈,在实现栈的基本功能的基础上,再实现返回栈中最小元素的操作。

输入描述:
第一行输入一个整数N,表示对栈进行的操作总数。

下面N行每行输入一个字符串S,表示操作的种类。

如果S为"push",则后面还有一个整数X表示向栈里压入整数X。

如果S为"pop",则表示弹出栈顶操作。

如果S为"getMin",则表示询问当前栈中的最小元素是多少。


输出描述:
对于每个getMin操作,输出一行表示当前栈中的最小元素是多少。
示例1

输入

6
push 3
push 2
push 1
getMin
pop
getMin

输出

1
2

备注:
1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作
#include <vector>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>

using namespace std;

template <class T>
class minstack
{
public:
    minstack()
    {
        realstack = new stack<T>;
        min = new stack<T>;
    }
    ~minstack()
    {
        delete realstack;
        delete min;
    }
    void push(T value)
    {
        realstack->push(value);
        if(min->empty())
        {
            min->push(value);
        }
        else
        {
            if(value < min->top())
                min->push(value);
            else
                min->push(min->top());
        }
    }
    T getmin()
    {
        return min->top();
    }
    void pop()
    {
        if(realstack->empty())
            cout << "this stack is empty" << endl;
        else
        {
            realstack->pop();
            min->pop();
        }
    }

private:
    stack<T>* realstack;
    stack<T>* min;
};

int main()
{
    int N;
    cin >> N;
    string str;
    minstack<int> hh;
    vector<int> res;
    N = N + 1;
    while (N--)
    {
        getline(cin, str);
        stringstream ss(str);
        string op;
        ss >> op;
        if(op == "push")
        {
            int num;
            ss >> num;
            hh.push(num);
        }
        if(op == "getMin")
        {
            res.push_back(hh.getmin());
        }
        if(op == "pop")
        {
            hh.pop();
        }
    }
    for(auto a:res)
        cout << a << endl;
    return 0;
}

发表于 2019-08-12 19:23:44 回复(0)
更多回答
#include <bits/stdc++.h>
using namespace std;

int main(){
    stack<int> S, M;
    int n, x;
    string s;
    cin>>n;
    while(n--){
        cin>>s;
        if(s=="push"){
            cin>>x;
            if(S.empty())
                S.push(x);
            else if(x<S.top())
                S.push(x);
            else
                S.push(S.top());
            M.push(x);
        }else if(s=="pop"){
            S.pop();
            M.pop();
        }else
            cout<<S.top()<<endl;
    }
    return 0;
}

发表于 2020-01-30 00:20:37 回复(1)
python3代码如下:
思路:增加一个栈,其中push方法是关键。
易错:注意对空栈的判断

import sys 

class GetMinStack(object):
    def __init__(self):
        self.stackData=[]
        self.stackMin=[]
    def push(self,num):
        self.stackData.append(num)
        if len(self.stackMin)==0 or num<=self.getMin():
            self.stackMin.append(num)
        else:
            self.stackMin.append(self.getMin())
    def pop(self):
        if len(self.stackData)==0:
            raise Exception("stack is empty")
        self.stackMin.pop()
        return self.stackData.pop()
    def getMin(self):
        if len(self.stackMin)==0:
            raise Exception("stack is empty")
        return self.stackMin[-1]

N = int(sys.stdin.readline().strip())
getMinStack = GetMinStack()
for i in range(N):
    line = sys.stdin.readline().strip()
    words = line.split()
    if words[0] == "push":
        getMinStack.push(int(words[1]))
    elif words[0] == "pop":
        getMinStack.pop()
    else:
        print(getMinStack.getMin())


发表于 2019-08-11 12:15:23 回复(0)
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct {
    int *data;
    int top;
} stack;

stack *new_stack(int cap) {
    stack *st = (stack *) malloc(sizeof(stack));
    st->data = (int *) malloc(sizeof(int) * cap);
    st->top = -1;
    return st;
}

void push(stack *st, int val) {
    st->data[++st->top] = val;
}

int pop(stack *st) {
    return st->data[st->top--];
}

int top(stack *st) {
    return st->data[st->top];
}

bool is_empty(stack *st) {
    return st->top == -1;
}

void destroy_stack(stack *st) {
    free(st->data);
    free(st);
}

int main(void) {
    int n, x;
    char opt[10];
    scanf("%d", &n);
    stack *nums = new_stack(n);
    stack *mins = new_stack(n);
    for (int i = 0; i < n; i++) {
        scanf("%s", opt);
        if (strcmp(opt, "push") == 0) {
            scanf("%d", &x);
            push(nums, x);
            if (is_empty(mins) || x <= top(mins)) {
                push(mins, x);
            }
        } else if (strcmp(opt, "pop") == 0) {
            x = pop(nums);
            if (x == top(mins)) {
                pop(mins);
            }
        } else {
            printf("%d\n", top(mins));
        }
    }
    destroy_stack(nums);
    destroy_stack(mins);
    return 0;
}

发表于 2022-02-15 20:37:54 回复(0)
用双栈进行求解,一个为正常栈,另一个为最小栈(保证栈顶一直为最小值):
(1) 对于压栈操作,正常栈直接压栈;而最小栈需要判断当前要压入的元素是否比栈顶小,如果小,直接压入,否则仍然压入此时的栈顶元素,以同步保证栈顶为截至到目前为止正常栈的最小值。
(2) 弹栈只需要同时弹出两个栈的栈顶元素。
(3) 获得最小值只需要返回最小栈的栈顶即可。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

class MinStack {
    public Stack<Integer> stack = new Stack<>();
    public Stack<Integer> minStack = new Stack<>();
    
    public MinStack() {}
    
    public void push(int val) {
        stack.push(val);
        if(minStack.isEmpty()) {
            minStack.push(val);
            return;
        }
        if(minStack.peek() >= val)
            minStack.push(val);               // 比当前最小值小就直接压入minStack
        else
            minStack.push(minStack.peek());   // 否则还是压入当前的最小值
    }
    
    public void pop() {
        minStack.pop();
        stack.pop();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        MinStack stack = new MinStack();
        for(int i = 0; i < n; i++){
            String[] params = br.readLine().trim().split(" ");
            String op = params[0];
            if(op.equals("push")){
                int elem = Integer.parseInt(params[1]);
                stack.push(elem);
            }else if(op.equals("pop"))
                stack.pop();
            else
                System.out.println(stack.getMin());
        }
    }
}

发表于 2021-06-03 12:55:19 回复(0)
#include <stack>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>

#define  COMMADN_LEN  100

int t1_getMin()
{
    std::stack<long> st, stackMin;
    char buf[COMMADN_LEN];
    char str_nums[10];
    int nums = 0;

    fgets(str_nums, 10, stdin);
    nums = atoi(str_nums);

#if 1
    char *p_work = NULL;
    while( nums ){
        fgets(buf, COMMADN_LEN, stdin);
        if ( strstr(buf, "push") ){ // 入栈规则
            p_work = buf;
            p_work += 5;
            int data = atoi(p_work);
            if(stackMin.empty()){ 
                stackMin.push(data);
            }else if(stackMin.top() >= data){ /*  注意,等于也要压入,不然出栈会发生段错误 */
                stackMin.push(data);
            }
            st.push(data);
        }else if (strstr(buf, "pop")){ // 出栈规则
            if (!st.empty()){
                if (!stackMin.empty() && st.top() == stackMin.top()){
                    stackMin.pop();
                }
                st.pop();
            }
        }else if (strstr(buf, "getMin")){
            if (!stackMin.empty()){
                printf("%d\n", stackMin.top());
            }
        }
        nums--;
    }
#endif
    return EXIT_SUCCESS;
}
发表于 2020-07-21 18:06:32 回复(0)

简介的实现,c++

#include <iostream>
#include <stack>
#include <string>
#include <climits>

using namespace std;

template <typename T>
class Stack{
private:
    stack<T> stackData, stackMin;
public:
    Stack(){
        stackMin.push(INT_MAX);
    }

    void push(T item){
        stackData.push(item);
        stackMin.push(min(stackMin.top(), item));
    }

    void pop(){
        stackMin.pop();
        stackData.pop();
    }

    T getMin(){
        return stackMin.top();
    }
};

int main(){
    Stack<int> s;
    int n;
    cin >> n;
    string operation;
    int item;
    while(n--){
        cin >> operation;
        if(operation == "push"){
            cin >> item;
            s.push(item);
        }else if(operation == "getMin"){
            cout << s.getMin() << endl;
        }else if(operation == "pop"){
            s.pop();
        }
    }
    return 0;
} 
编辑于 2020-05-10 18:03:21 回复(0)
import java.util.Scanner;
import java.util.Stack;


import java.util.Stack;


public class Main {
	private static Stack<Integer> stack = new Stack<Integer>();
	private static Stack<Integer> stackmin = new Stack<Integer>();
	
	public static Integer pop() {
		stackmin.pop();
		return stack.pop();
	}
	
	public static Integer getMin() {
		return stackmin.peek();
	}
	
	public static void push(Integer i) {
		stack.push(i);
		if (!stackmin.isEmpty()) {
			stackmin.push(Math.min(i, stackmin.peek()));
		}
		else {
			stackmin.push(i);
		}
	}
	
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        
        int n = scanner.nextInt();
        
        scanner.nextLine();
        
        for (int opnum = 0; opnum<n; opnum++) {
        	String str = scanner.nextLine();
        	if (str.equals("getMin")) {
        		System.out.println(getMin());
        	} else if (str.equals("pop")) {
				pop();
			}else {
				String[] tmpstr = str.split(" ");
				Integer integer = Integer.parseInt(tmpstr[tmpstr.length-1]);
				push(integer);
			}
        }
        
    }

}


发表于 2020-01-15 22:57:43 回复(0)
使用两个栈,数据栈存放数据,最小栈存放最小值;每次有新数据压入数据栈时,选择新数据和当前最小值中的较小值压入最小栈。

import java.util.Scanner;
import java.util.Stack;
public class Main {
        private static Stack dataStack;
        private static Stack minStack;

        public static void main(String[] args) {
            dataStack = new Stack();
            minStack = new Stack();
            Scanner scanner = new Scanner(System.in);
            int n = Integer.valueOf(scanner.nextLine());
            String string;
            for (int i = 0; i < n; i++) {
                string = scanner.nextLine();
                if (string.equals("pop")) {
                    pop();
                } else if (string.equals("getMin")) {
                    System.out.println(getMin());
                } else {
                    push(Integer.valueOf(string.split(" ")[1]));
                }
            }
        }
        public static void push(int number) {
            dataStack.push(number);
            if(!minStack.empty()) {
                minStack.push(number < getMin() ? number : getMin());
            } else {
                minStack.push(number);
            }
        }
        public static int pop() {
            if (dataStack.empty()) {
                throw new RuntimeException("Your stack is empty!");
            }
            minStack.pop();
            return dataStack.pop();
        }
        public static int getMin() {
            if (minStack.empty()) {
                throw new RuntimeException("Your stack is empty!");
            }
            return minStack.peek();
        }
}

发表于 2019-12-13 11:24:59 回复(0)
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,x;
    string s;
    cin>>n;
    stack<int>s1,s2;
    while(n--)
    {
        cin>>s;
        if(s=="push")
        {
            cin>>x;
            if(s2.empty())
                s2.push(x);
            else if(x<s2.top())
                    s2.push(x);
            else
            {
                x=s2.top();
                s2.push(x);
            }
            s1.push(x);
        }
        else if(s=="pop")
        {
            s1.pop();
            s2.pop();
        }
        else
            cout<<s2.top()<<endl;
    }
    return 0;
}

发表于 2019-08-23 21:25:33 回复(0)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

// 设计一个有getMin功能的栈
public class Main {
    //stackData用于正常栈的功能,stackMin用于同步存储每一步的最小值
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    // public构造方法
    public Main(){
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }

    public void push(int newNum){
        if(this.stackMin.isEmpty()){
            this.stackMin.push(newNum);
        }else if(newNum <= this.top()){
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }

    public int pop(){
        if(this.stackData.isEmpty()){
            throw new RuntimeException("Your stack is empty.");
        }
        int value = this.stackData.pop();
        if(value == this.top()){
            this.stackMin.pop();
        }
        return value;
    }

    public int top() {
        return this.stackMin.peek();
    }

    public void getMin(){
        if (this.stackMin.isEmpty()){
            throw new RuntimeException("Your stack is empty");
        }
        // 这里要输出,不能return,再增加一个top,用于上面push和pop的比较
        System.out.println(this.stackMin.peek());
    }

    public static void main(String[] args) throws IOException {
        // 记得new这个类
        Main m = new Main();

        BufferedReader  scanner = new BufferedReader(new InputStreamReader(System.in));
        // 读进来的String要转成Integer
        int rows = Integer.parseInt(scanner.readLine());
        for (int i = 0;i <rows;i++){
            // 字符串空格隔开后放进数组!一个数组存放一组操作
            String[] inputData = scanner.readLine().split(" ");
            if(inputData[0].equals("push")){
                m.push(Integer.parseInt(inputData[1]));
            }
            if (inputData[0].equals("pop")){
                m.pop();
            }
            if (inputData[0].equals("getMin")){
                m.getMin();
            }
        }
        // 关!
        scanner.close();
    }
}

发表于 2020-03-29 18:27:00 回复(0)
Java用Scanner读输入不能过,报超时。。。服了
发表于 2019-08-07 10:38:22 回复(2)
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Main specialStack = new Main();

        List<Integer> resultList = new ArrayList<>();
        Scanner scanner = new Scanner(System.in);
        //接收键盘输入
        if (scanner.hasNext()) {
            int N = scanner.nextInt();
            Scanner commandScanner = new Scanner(System.in);
            while (N > 0 && commandScanner.hasNextLine()) {
                String s = commandScanner.nextLine();
                if (s.startsWith("push")) {
                    int newNum = Integer.parseInt(s.split(" ")[1]);
                    specialStack.push(newNum);
                } else {
                    if (s.startsWith("pop")) {
                        specialStack.pop();
                    }
                    if (s.equals("getMin")) {
                        resultList.add(specialStack.getMin());
                    }
                }
                N--;
            }
            commandScanner.close();
        }
        scanner.close();
        resultList.forEach(System.out::println);
    }

    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public Main() {
        this.stackData = new Stack<>();
        this.stackMin = new Stack<>();
    }

    public void push(int newNum) {
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        } else if (newNum < this.getMin()) {
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    public int pop() {
        if (stackData.isEmpty()) {
            throw new RuntimeException("栈空,无法弹出元素");
        }

        int value = stackData.pop();
        if (value == this.getMin()) {
            stackMin.pop();
        }
        return value;
    }

    public int getMin() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("栈空,不能获取最小元素");
        }
        return stackMin.peek();
    }

}

发表于 2022-07-14 22:09:39 回复(0)
import java.util.*;
public class Main{
    int arr[];//栈
    int length=0;//最大长度
    int p=-1;//栈帧
    
    Main(int n){
        this.length=n;
        arr=new int[n];
    }
    public boolean isFull(){
        if(length<=0)return true;
        else{
            if(p<length-1)return false;
            else
                return true;
        }
    }
    public boolean isEmpty(){
        if(length<=0)return true;
        else{
            if(p==-1)return true;
            else return false;
        }
    }
    public void push(int i){
        if(!isFull()){
            arr[++p]=i;
        }
    }
    public int pop(){
        if(!isEmpty()){
            int temp=arr[p--];
            //System.out.println(temp+"");
            return temp;
        }
        return -1;
    }
    public void getMin(){
        int min=Integer.MAX_VALUE;
        for(int i=0;i<=p;i++)
            min=Math.min(min,arr[i]);
        System.out.println(min);
    }
    public static void main(String[]args){
        Scanner scanner=new Scanner(System.in);
        Main m=new Main(100);
        int n=scanner.nextInt();
        for(int i=0;i<n;i++){
            String s=scanner.next();
            if(s.equals("getMin")){
                m.getMin();
            }else if(s.equals("push")){
                int i1=scanner.nextInt();
                m.push(i1);
            }else{
                m.pop();
            }
        }
        
    }
}

发表于 2022-06-08 09:22:57 回复(0)
list1 = []
a = int(input())
count = 0
while count < a:
    count += 1
    b = input()
    if 'push' in b:
        list1.append(b.split(' ')[1])
    elif 'pop' in b:
        list1.pop(-1)
    elif 'getMin' in b:
        print(min(map(int,list1)))
发表于 2022-04-28 00:14:46 回复(0)
#include <bits/stdc++.h>

using namespace std;

// 利用 C++ 的pair 保存 <当前元素,当前栈的最小元素>
stack<pair<int, int>> st;


void push_min(int val){
    if(!st.empty()){
        st.push({val, st.top().second < val ? st.top().second : val});
    }
    else
        st.push({val, val});
}

void pop_min(){
    
    st.pop();
}

int getMin(){
    return st.top().second;
}



int main()
{
    int n;
    cin >> n;
    while(n--){
        string s;
        cin >> s;
        if(s == "push"){
            int num;
            cin >> num;
            push_min(num);
        }
        else if(s == "pop"){
            pop_min();
        }
        else {
            cout << getMin() << endl;
        }
    }
    return 0;
}


发表于 2022-04-07 00:07:50 回复(0)
#include <stdio.h>
#include <string.h>
#define  N  1000000
int a[N];
int len=0;
int min=1000000;
int main(){
    int n,num;
    char s[10]={0};
    scanf("%d",&n);
    
    while(n--){
        scanf("%s",s);
        if(!strcmp(s, "push")){
            scanf("%d",&num);
            a[len++]=num;
            if(num<min)        
                min=num;
        }else if(!strcmp(s, "pop")){
            len--;
            int m=1000000;
            for(int i =  0;i<len;i++){
                if(a[i]<m)    
                m=a[i];
            }
            min=m;
        }else if(!strcmp(s, "getMin")){
            printf("%d\n",min);
        }
        memset(s,0,sizeof(s));
    }
    
}

发表于 2022-03-31 18:39:02 回复(0)
这里需要两栈,一个stk_data用来存储数据,作为正常的栈使用,一个stk_min用来存储最小值,做单调栈使用。
有两种方法:
方法1:压入时所有的数据都压入stk_data,如果stk_min为空或者压入的数据小于等于stk_min的栈顶值,则压入stk_min,否则不压入。弹出时,stk_data肯定弹出,弹出值等于stk_min栈顶值,stk_min也弹出。
方法2:压入时所有的数据都压入stk_data,如果stk_min为空或者压入的数据小于等于stk_min的栈顶值,则压入stk_min,否则stk_min再一次压入自身栈顶值。弹出时,stk_data和stk_min栈顶都进行弹出操作。

#include "iostream"
#include "stack"
//#include "cmath"
//#include "limits.h"

using namespace std;
int main()
{
    int num;
    cin>>num;
    stack<int> stk_data;
    stack<int> stk_min;
    
    string str;
    int tmp;
    for(int i=0;i<num;i++)
    {
        cin>>str;
        if(str=="push")
        {
            cin>>tmp;
            stk_data.push(tmp);
            if(stk_min.empty()||tmp<=stk_min.top())
            {
                stk_min.push(tmp);
            }
        }
        else if(str=="pop")
        {
            if(stk_data.top()==stk_min.top()) stk_min.pop();
            stk_data.pop();
        }
        else if(str=="getMin")
        {
            cout<<stk_min.top()<<endl;
        }
    }
    return 0;
}


发表于 2021-12-27 13:11:55 回复(0)
# 分别代表正常栈和最小栈
stack = []
minStack = []


def push(num):
    stack.append(num)
    # 更新最小栈
    if not minStack&nbs***bsp;num <= minStack[-1]:
        minStack.append(num)


def pop():
    if minStack[-1] == stack[-1]:
        minStack.pop()
    stack.pop()


def getMin():
    print(minStack[-1])


if __name__ == '__main__':
    N = int(input())
    for i in range(N):
        l = input().split()
        if len(l) > 1:
            push(int(l[1]))
        elif l[0] == 'pop':
            pop()
        else:
            getMin()

发表于 2021-12-27 11:22:18 回复(0)
跟着书本写的,java版本,改成c++费劲,就先用java来学习先。

方法1

import java.util.*;
class MyStack1{
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public MyStack1(){
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    public void push(int newNum){
        if(this.stackMin.isEmpty()){
            this.stackMin.push(newNum);
        }else if(newNum <= this.getmin()){
            this.stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }
    public int pop(){
        if(this.stackData.isEmpty()){
            throw new RuntimeException("Your stack is empty");
        }
        int value = this.stackData.pop();
        if(value == this.getmin()){
            this.stackMin.pop();
        }
        return value;
    }
    public int getmin(){
        if(this.stackMin.isEmpty()){
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        MyStack1 stack1 = new MyStack1();
        int t = scan.nextInt();
        for(int i=0;i<t;i++){
            String op=scan.next();
            if(op.equals("push")){
                int x= scan.nextInt();
                stack1.push(x);
            }else if(op.equals("getMin")){
                System.out.println(stack1.getmin());
            }else if(op.equals("pop")){
                stack1.pop();
            }
        }
    }
}

方法2

import java.util.*;
class MyStack2{
    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;
    public MyStack2(){
        this.stackData = new Stack<Integer>();
        this.stackMin = new Stack<Integer>();
    }
    public void push(int newNum){
        if(this.stackMin.isEmpty()){
            this.stackMin.push(newNum);
        }else if(newNum < this.getmin()){
            this.stackMin.push(newNum);
        }else{//压入之前的最小值
            int newMin = this.stackMin.peek();
            this.stackMin.push(newMin);
        }
        this.stackData.push(newNum);
    }
    public int pop(){
        if(this.stackData.isEmpty()){
            throw new RuntimeException("Your stack is empty");
        }
        this.stackMin.pop();
        return this.stackData.pop();
    }
    public int getmin(){
        if(this.stackMin.isEmpty()){
            throw new RuntimeException("Your stack is empty.");
        }
        return this.stackMin.peek();
    }
}
public class Main{
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        MyStack2 stack2 = new MyStack2();
        int t = scan.nextInt();
        for(int i=0;i<t;i++){
            String op=scan.next();
            if(op.equals("push")){
                int x= scan.nextInt();
                stack2.push(x);
            }else if(op.equals("getMin")){
                System.out.println(stack2.getmin());
            }else if(op.equals("pop")){
                stack2.pop();
            }
        }
    }
}


编辑于 2021-10-18 10:46:14 回复(0)
#利用两个栈实现
#一个是保存所有数据的栈
#另外一个是保存到现在为止所有数据中最小值的栈
#用python中的list模拟栈
#普通存放数据的栈
normal_stack=[]
#存放最小元素的栈
min_stack=[]
#获取输入
#input()表示从控制台获得一个输入,返回的是字符串形式
#需要转化为int类型
n=int(input())
#模拟,进行栈的操作
#共操作了n次
for i in range(n):
    #获取操作命令和数字(如果有)
    operator=input()
    #判断操作类型
    if operator[:2]=='pu':
        #分割出要保存的数字
        #.split()代表用空格分割字符串
        _,number=operator.split()
        number=int(number)
        normal_stack.append(number)
        #更新最小栈
        #如果当前存放最小值的栈为空
        if len(min_stack)==0:
            #直接压入
            min_stack.append(number)
        #否则的话
        #如果当前元素小于栈顶元素,压入
        else:
            #等于是允许最小值重复出现
            if number<=min_stack[-1]:
                min_stack.append(number)
    if operator[:2]=='ge':
        print(min_stack[-1])
    if operator[:2]=='po':
        #list中的pop方法默认弹出最后一个元素
        pop_num=normal_stack.pop()
        #如果弹出的是最小值,最小值栈也要更新
        if pop_num==min_stack[-1]:
            min_stack.pop()

            

发表于 2021-08-21 16:28:22 回复(0)