O (1) 시간 및 O (1) 추가 공간에서 getMin ()을 지원하는 스택을 설계합니다. 따라서 특별 스택 데이터 구조는 다음과 같은 스택의 모든 작업을 지원해야합니다.
- 무효 push ()
- int pop ()
- bool isFull ()
- bool isEmpty ()
일정한 시간에. 추가 연산 getMin ()을 추가하여 일정한 시간과 O (1) 추가 공간에서 특수 스택의 최소값을 반환합니다.
차례
예
push(30) push(20) push(10) getMin() pop() getMin()
Minimum element : 10 Popped element : 10 Minimum element : 20
push(500) push(50) push(5) getMin() pop() getMin()
Minimum element : 5 Popped element : 5 Minimum element : 50
minStack을 구현하기위한 수학적 / 관찰 된 방법
이 접근 방식에서는 최소 요소를 다음과 같이 업데이트합니다.
push () 함수에서 푸시 할 정수가 최소 요소보다 작 으면 해당 정수의 두 배에서 최소 요소를 뺀 스택에 삽입합니다.이 요소는 항상 주어진 정수보다 작습니다.
- 주어진 정수 <주어진 정수를 의미하는 최소 요소 – 최소 요소 <0
- // 양쪽에 주어진 정수 추가
- 주어진 정수 – 최소 요소 + 주어진 정수 <0 + 주어진 정수
- 2 * 주어진 정수 – 최소 요소 <주어진 정수
- 2 * 주어진 정수 – 최소 요소 <새로운 최소 요소
따라서이 요소를 튀어 나오는 동안 최소 요소보다 작으므로 최소 요소를 업데이트합니다.
마찬가지로 pop () 함수에서 현재 요소가 최소 요소보다 작 으면 업데이트합니다.
암호알고리즘
- 구조 초기화 뉴스택 함수를 만듭니다. 푸시() 정수를 매개 변수로 받아들이는 그 안에.
- 스택이 비어 있는지 확인하고 정수 min 변수에서 스택에 정수를 삽입하고 반환합니다.
- 정수가 min보다 작 으면 2 * x – min을 스택에 삽입하고 min을 x로 업데이트합니다.
- 그렇지 않으면 스택의 정수를 푸시하십시오.
- pop () 함수를 만듭니다. 스택이 비어 있는지 확인하고“스택이 비어 있음”을 인쇄하고 반환합니다.
- 그렇지 않으면 변수 t의 스택 맨 위에 요소를 저장하고 스택에서 맨 위 요소를 팝 / 제거합니다.
- t가 min print min보다 작은 지 확인하고 min을 2 * min – t로 업데이트하십시오.
- 그렇지 않으면 t.
- getMin () 함수를 생성하고 스택이 비어 있는지 확인하십시오. "Stack is empty"를 인쇄하십시오.
- Else는 최소 요소를 반환합니다.
암호
minStack 용 C ++ 프로그램
#include <bits/stdc++.h>
using namespace std;
struct newStack{
stack<int> s;
int min;
void getMin(){
if(s.empty()){
cout<<"Stack is empty\n";
}
else{
cout<<"Minimum element : "<<min<<"\n";
}
}
void pop(){
if(s.empty()){
cout<<"Stack is empty\n";
return;
}
cout<<"Popped element : ";
int t = s.top();
s.pop();
if(t<min){
cout<<min<< "\n";
min = 2*min - t;
}
else{
cout<<t<< "\n";
}
}
void push(int x){
if(s.empty()){
min = x;
s.push(x);
return;
}
if(x < min){
s.push(2*x - min);
min = x;
}
else{
s.push(x);
}
}
};
int main(){
newStack s;
s.push(30);
s.push(20);
s.push(10);
s.getMin();
s.pop();
s.getMin();
return 0;
}
Minimum element : 10 Popped element : 10 Minimum element : 20
minStack 용 Java 프로그램
import java.util.*;
class newStack{
Stack<Integer> s;
Integer min;
newStack(){
s = new Stack<Integer>();
}
void getMin(){
if(s.isEmpty())
System.out.println("Stack is empty");
else{
System.out.println("Minimum element : " + min);
}
}
void pop(){
if (s.isEmpty()){
System.out.println("Stack is empty");
return;
}
System.out.print("Popped element : ");
Integer t = s.pop();
if(t<min){
System.out.println(min);
min = 2*min - t;
}
else{
System.out.println(t);
}
}
void push(Integer x){
if(s.isEmpty()){
min = x;
s.push(x);
return;
}
if(x<min){
s.push(2*x - min);
min = x;
}
else{
s.push(x);
}
}
};
public class Main{
public static void main(String[] args){
newStack s = new newStack();
s.push(30);
s.push(20);
s.push(10);
s.getMin();
s.pop();
s.getMin();
}
}
Minimum element : 10 Popped element : 10 Minimum element : 20
복잡성 분석
시간 복잡성
O (1) 모든 작업이 일정한 시간에 수행되므로 각 작업에 대해.
공간 복잡성
O (1) 일정한 보조 공간을 사용하고 있기 때문입니다. 입력을 저장하는 데 필요한 공간은 알고리즘의 공간 복잡성에 포함되지 않습니다.
