資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++程式：構建具有指定操作的最大棧
假設我們想建立一個最大棧，它支援以下操作：
MaxStk()：構造一個新的最大棧例項。
push(val)：將val插入到棧中。
top()：獲取棧頂元素。
max()：獲取棧中最大元素。
pop()：移除並返回棧頂元素。
popmax()：移除並返回棧中最大元素。
現在，透過呼叫MasStk()構造最大棧，然後壓入三個值：5、15、10，接著分別呼叫top()、max()、popmax()、max()、pop()、top()函式。初始棧狀態為[5, 15, 10]，相應函式的輸出為：10、15、15、10、10、5。
為了解決這個問題，我們將遵循以下步驟：
pos_index := 0
定義一個集合stk和另一個集合aux。
定義建構函式，它不執行任何特殊任務。
定義一個函式push()，它將接收val，
將pos_index、val插入到stk中。
將val、pos_index插入到aux中。
(pos_index加1)
定義一個函式top()。
如果stk為空，則：
返回-1。
返回stk的第一個元素的第二個值。
定義一個函式max()。
如果aux為空，則：
返回-1。
返回aux的第一個元素的第一個值。
定義一個函式pop()。
如果stk為空，則：
返回-1。
id := stk第一個元素的第一個值，ret := stk第一個元素的第二個值。
從stk中刪除第一個元素。
從aux中刪除(ret, id)對。
返回ret。
定義一個函式popmax()。
如果aux為空，則：
返回-1。
ret := aux第一個元素的第一個值，id := aux第一個元素的第二個值。
從aux中刪除第一個元素。
從stk中刪除(id, ret)對。
返回ret。
讓我們來看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class MaxStk {
int pos_index = 0;
set<pair<int, int>, greater<>> stk, aux;
public:
MaxStk() {}
void push(int val) {
stk.emplace(pos_index, val);
aux.emplace(val, pos_index);
pos_index++;
}
int top() {
if (stk.empty())
return −1;
return stk.begin()−>second;
}
int max() {
if (aux.empty())
return −1;
return aux.begin()−>first;
}
int pop() {
if (stk.empty())
return −1;
int id = stk.begin()−>first, ret = stk.begin()−>second;
stk.erase(stk.begin());
aux.erase({ret, id});
return ret;
}
int popmax() {
if (aux.empty())
return −1;
int ret = aux.begin()−>first, id = aux.begin()−>second;
aux.erase(aux.begin());
stk.erase({id, ret});
return ret;
}
};
int main(){
MaxStk max_stk;
max_stk.push(5);
max_stk.push(15);
max_stk.push(10);
cout << max_stk.top() << endl;
cout << max_stk.max() << endl;
cout << max_stk.popmax() << endl;
cout << max_stk.max() << endl;
cout << max_stk.pop() << endl;
cout << max_stk.top() << endl;
}輸入
max_stk.push(5) max_stk.push(15) max_stk.push(10) max_stk.top() max_stk.max() max_stk.popmax() max_stk.max() max_stk.pop() max_stk.top()
輸出
10 15 15 10 10 5
更新於：2020年12月26日
瀏覽量：295
廣告