设计getMin功能的栈

#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;
}

#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;
}

#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;
}

简介的实现，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;
} 

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);
			}
        }
        
    }

}

#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;
}

#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;
}

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();
    }
}

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();
    }

}

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();
            }
        }
        
    }
}

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)))

#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;
}

# 分别代表正常栈和最小栈
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()

#利用两个栈实现
#一个是保存所有数据的栈
#另外一个是保存到现在为止所有数据中最小值的栈
#用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()