최소 스택

최소 스택 문제에서 우리는 스택 다음 기능을 효율적으로 구현하기 위해
푸시 (x) –> 요소 x를 스택으로 푸시
팝() –> 스택 맨 위에있는 항목을 제거합니다.
상단() –> 스택 맨 위에있는 요소를 반환합니다.
getMin () –> 스택에있는 최소 요소를 반환합니다.

예

입력:
푸시 -2
푸시 0
최소 가져 오기
푸시 -3
팝
상의
최소 가져 오기
출력:
-2
0
-2

최소 스택에 대한 알고리즘

push, pop 및 top 메서드는 일반 스택과 유사하지만 스택에있는 최소 요소를 가져 오기 위해 모든 요소까지 최소값을 저장하는 스택을 하나 더 사용합니다.

첫 번째 스택을 st, 두 번째 스택을 minSt로 설정 한 다음

푸시 (x)

1. x를 스택 st에 밀어 넣습니다.
2. minSt가 비어 있거나 minSt의 상단이 x보다 크면 x를 minSt로 누릅니다.
3. 그렇지 않으면 minSt의 상단을 minSt로 다시 밉니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

팝()

스택 st 및 스택 minSt에서 요소를 팝합니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

상단()

스택의 맨 위를 반환합니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

getMin ()

스택 minSt의 맨 위를 반환합니다.

시간 복잡성 =O (1) 
공간 복잡성 =O (1)

전반적인 공간 복잡성 = O (n) 
여기서 n은 한 번에 스택으로 푸시되는 최대 요소 수입니다.

최소 스택에 대한 설명

위의 예를 고려하십시오.
두 스택 st 및 minSt를 초기화합니다.
st = null 및 minSt = null

1. 푸시 (-2)
   st = (-2) 및 minSt = (-2)
2. 푸시 0
   st = 0-> (-2) 및 minSt = (-2)-> (-2)
3. getMin
   minSt의 맨 위 = (-2), 반환(-2)
4. 푸시 (-3)
   st = (-3)-> 0-> (-2) 및 minSt = (-3)-> (-2)-> (-2)
5. 팝
   st = 0-> (-2) 및 minSt = (-2)-> (-2)
6. 상의
   스택의 맨 위 st는 0이고 0을 반환합니다.
7. getMin
   스택의 최상위 minSt는 (-2)이고 (-2)를 반환합니다.

자세한 내용은 아래 이미지를 참조하십시오.

핀

최소 스택 용 JAVA 코드

import java.util.Stack;

public class MinStack {
    private static Stack<Integer> st;
    private static Stack<Integer> minSt;

    private static void push(int x) {
        // Push x to stack st
        st.push(x);
        // If minSt is empty or if top of minSt is greater than x push x to minSt.
        if (minSt.isEmpty() || minSt.peek() > x) {
            minSt.push(x);
        } else {
            // Else push top of minSt to minSt again.
            minSt.push(minSt.peek());
        }
    }

    private static void pop() {
        // Pop element from st and minSt
        st.pop();
        minSt.pop();
    }
    
    private static int top() {
        // Return top of st
        return st.peek();
    }
    
    private static int getMin() {
        // Return top of minSt
        return minSt.peek();
    }

    public static void main(String[] args) {
        // Initialise st and minSt
        st = new Stack<>();
        minSt = new Stack<>();

        // Example
        push(-2);
        push(0);
        System.out.println(getMin());
        push(-3);
        pop();
        System.out.println(top());
        System.out.println(getMin());
    }
}

-2
0
-2

최소 스택 용 C ++ 코드

#include<bits/stdc++.h> 
using namespace std;

stack<int> st;
stack<int> minSt;

void push(int x) {
    // Push x to stack st
    st.push(x);
    // If minSt is empty or if top of minSt is greater than x push x to minSt.
    if (minSt.empty() || minSt.top() > x) {
        minSt.push(x);
    } else {
        // Else push top of minSt to minSt again.
        minSt.push(minSt.top());
    }
}

void pop() {
    // Pop element from st and minSt
    st.pop();
    minSt.pop();
}

int top() {
    // Return top of st
    return st.top();
}

int getMin() {
    // Return top of minSt
    return minSt.top();
}

int main() {
    // Example
    push(-2);
    push(0);
    cout<<getMin()<<endl;
    push(-3);
    pop();
    cout<<top()<<endl;
    cout<<getMin()<<endl;
    
    return 0;
}

-2
0
-2

참조