265
劍指Offer之包含min函數的棧
- 題目描述：
-
定義棧的數據結構，請在該類型中實現一個能夠得到棧最小元素的min函數。
- 輸入：
-
輸入可能包含多個測試樣例，輸入以EOF結束。
對於每個測試案例，輸入的第一行為一個整數n(1<=n<=1000000)， n代表將要輸入的操作的步驟數。
接下來有n行，每行開始有一個字母Ci。
Ci=’s’時，接下有一個數字k，代表將k壓入棧。
Ci=’o’時，彈出棧頂元素。
- 輸出：
-
對應每個測試案例中的每個操作，
若棧不為空，輸出相應的棧中最小元素。否則，輸出NULL。
- 樣例輸入：
-
7 s 3 s 4 s 2 s 1 o o s 0
- 樣例輸出：
-
3 3 2 1 2 3 0
/*********************************
* 日期：2013-11-19
* 作者：SJF0115
* 題號: 題目1522：包含min函數的棧
* 來源：https://ac.jobdu.com/problem.php?pid=1522
* 結果：AC
* 來源：劍指Offer
* 總結：
**********************************/
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <stack>
using namespace std;
int MinOfStack(int n){
int i,num;
char operate;
stack<int> numStack;
stack<int> minStack;
for(i = 0;i < n;i++){
scanf(" %c",&operate);
//進棧
if(operate == 's'){
scanf("%d",&num);
numStack.push(num);
//輔助棧不空
if(!minStack.empty()){
int minNum = minStack.top();
//當前值和最小值比較，小的放入minStack
if(num < minNum){
minStack.push(num);
}
else{
minStack.push(minNum);
}
}
//輔助棧空
else{
minStack.push(num);
}
printf("%d\n",minStack.top());
}
//出棧
else if(operate == 'o'){
if(!minStack.empty()){
minStack.pop();
numStack.pop();
}
if(!minStack.empty()){
printf("%d\n",minStack.top());
}
else{
printf("NULL\n");
}
}
//非法
else{
return 0;
}
}
return 1;
}
int main()
{
int i,n;
while(scanf("%d",&n) != EOF){
int result = MinOfStack(n);
if(result == 0){
break;
}
}
return 0;
}
#include <stdio.h>
#define MAXN 1000010
int stackA[MAXN],stackB[MAXN];
int top=-1,min;
void push(int num)
{
if(top==-1){
min=num;
stackA[++top]=num;
}
else{
if(min>=num){
stackA[++top]=num;
stackB[top]=min;
min=num;
}
else
stackA[++top]=num;
}
printf("%d\n",min);
}
void pop()
{
int tmp=stackA[top--];
if(top==-1){
printf("NULL\n");
return ;
}
if(tmp==min)
min=stackB[top+1];
printf("%d\n",min);
return ;
}
int main()
{
int n,num;
char c;
while(scanf("%d",&n)!=EOF){
top=-1;
while(n--){
scanf(" %c",&c);
if(c=='s'){
scanf("%d",&num);
push(num);
}
else if(c=='o')
pop();
}
}
return 0;
}
最後更新：2017-04-03 14:54:25