POJ 1028 Web Navigation：雙棧模擬瀏覽器前進後退

題目大意

模擬瀏覽器導航：初始頁面 https://www.acm.org/。支持命令：

• VISIT URL：訪問新頁面，當前頁入後退棧，清空前進棧
• BACK：當前頁入前進棧，從後退棧彈出頁面為當前頁 (空則忽略)
• FORWARD：當前頁入後退棧，從前進棧彈出頁面為當前頁 (空則忽略)
• QUIT：結束

每條命令 (除 QUIT) 輸出當前頁 URL 或 Ignored。

數據結構：兩個堆疊

• backStack：可後退的頁面 (棧頂為最近)
• forwardStack：可前進的頁面 (棧頂為最近)
• current：當前頁面

操作邏輯

// VISIT url
backStack.push(current);
current = url;
forwardStack = stack(); // 清空

// BACK
if (!backStack.empty()) {
    forwardStack.push(current);
    current = backStack.top(); backStack.pop();
    output current;
} else output "Ignored";

// FORWARD
if (!forwardStack.empty()) {
    backStack.push(current);
    current = forwardStack.top(); forwardStack.pop();
    output current;
} else output "Ignored";

完整代碼

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string current = "https://www.acm.org/";
    stack backStack, forwardStack;
    string cmd;

    while (cin >> cmd) {
        if (cmd == "QUIT") break;
        if (cmd == "VISIT") {
            string url; cin >> url;
            backStack.push(current);
            current = url;
            while (!forwardStack.empty()) forwardStack.pop();
            cout << current << '\n';
        } else if (cmd == "BACK") {
            if (backStack.empty()) {
                cout << "Ignored\n";
            } else {
                forwardStack.push(current);
                current = backStack.top(); backStack.pop();
                cout << current << '\n';
            }
        } else if (cmd == "FORWARD") {
            if (forwardStack.empty()) {
                cout << "Ignored\n";
            } else {
                backStack.push(current);
                current = forwardStack.top(); forwardStack.pop();
                cout << current << '\n';
            }
        }
    }
    return 0;
}

樣例追蹤

輸入：
VISIT https://acm.ashland.edu/
VISIT https://acm.baylor.edu/acmicpc/
BACK
BACK
BACK
FORWARD
VISIT https://www.ibm.com/
BACK
BACK
FORWARD
FORWARD
FORWARD
QUIT

輸出：
https://acm.ashland.edu/
https://acm.baylor.edu/acmicpc/
https://acm.ashland.edu/
https://www.acm.org/
Ignored
https://acm.ashland.edu/
https://www.ibm.com/
https://acm.ashland.edu/
https://www.acm.org/
https://acm.ashland.edu/
https://www.ibm.com/
Ignored

複雜度分析

• 每條命令 O(1) (棧操作)
• 空間：O(歷史記錄長度)，題目保證 ≤ 100

擴展：支持完整瀏覽器歷史

真實瀏覽器使用雙向鏈表或數組 + 指針實現歷史，支持：

• 任意跳轉 (不只相鄰)
• 歷史搜索、分組、同步
• 會話恢復 (序列化到磁盤)

但本題僅需模擬基本前進後退，雙棧是最簡潔、正確的模型。

總結

POJ 1028 是棧應用的經典入門題：後退棧 + 前進棧 + 當前頁 完美建模瀏覽器導航邏輯。關鍵點在於 VISIT 清空前進棧、BACK/FORWARD 互為逆操作、空棧保護輸出 Ignored。代碼簡短、邏輯清晰，是數據結構教學的優秀案例。