程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 棧學習筆記，wifi協議棧學習

棧學習筆記，wifi協議棧學習

編輯：C++入門知識

棧學習筆記，wifi協議棧學習

棧

棧是特殊的鏈表，只能在表尾進行插入(push)和刪除(pop),具有後進先出的特點(LIFO)
鏈表分為動態鏈表和表態鏈表。動態鏈表是根據需要給棧元素分配存儲空間，而靜態鏈表則是固定存儲空間的。
C++ STL(Standard Template Library, 即標准模板庫) 定義了棧的基本操作, 需要包含<stack>頭文件。示例代碼如圖1-1所示。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
    stack<int>s; //聲明棧s的元素類似是int
    s.empty()    //棧空，返回true, 否則返回false
    s.push(1);   //1進棧
    s.top();     //取棧頂元素
    s.pop();     //棧頂元素出棧
    return 0;                        
}

圖1-1 標准模板庫stack的使用示例

規模確定的情況下，可以使用數組來存儲棧。示例代碼如圖1-2所示。

#include <iostream>
#include <stack>
using namespace std;
int main()
{
    int stk[1000], top=0;
　　 top = 0;          //棧空
    stk[++top] = 1;   //1進棧
    stk[-- top];      //取棧頂元素
    top--;            //出棧
    return 0;                        
}

圖1-2 用數組實現簡單的棧

與棧相關的編程練習，TOJ 1196 Web Navigation 和 TOJ 1036 Rails。其中前者是模擬上網訪問(visit)網頁的前進(FORWARD)和後退(BACK)，後者是模擬火車進入“死胡同”後出站的順序。前者可以用兩個棧，一個保存前進的網頁URL，一個保存後退的URL。火車車廂進“死胡同”，後進的車廂先出。這兩道題是比較古老但經典的與棧相關的題目。這兩道題的相應代碼分別如圖1-3、圖1-4所示。

#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
    string cmd, visit = "http://www.acm.org/";
    stack<string>Forward, Back;
    while(cin>>cmd && cmd != "QUIT")
    {
        if(cmd == "VISIT")
        {
            Back.push(visit);
            while(!Forward.empty())
                Forward.pop();
            cin>>visit;
        }
        else if(cmd == "FORWARD")
        {
            if(Forward.empty())
            {
                cout<<"Ignored"<<endl;
                continue;
            }
            else
            {
                Back.push(visit);
                visit = Forward.top();
                Forward.pop();
            }
        }
        else if(cmd == "BACK")
        {
            if(Back.empty())
            {
                cout<<"Ignored"<<endl;
                continue;
            }
            else
            {
                Forward.push(visit);
                visit = Back.top();
                Back.pop();
            }
        }
        else
            printf("Invalid input!\n");
        cout<<visit<<endl;
    }
    return 0;
}

圖1-3 TOJ1196 Web Navigation的參考代碼

#include <stdio.h>
#include <stdlib.h>
#include <stack>
using namespace std;
int main()
{
    stack<int>s;
    int n, i, j;
    while(scanf("%d", &n) && n)
    {
        //init block
        int a[n];
      while(scanf("%d", &a[0]) && a[0])
     {
        for(i=1; i<n; i++)
        {
            scanf("%d", &a[i]);
        }
        //judge
        j = 1, i=0;
        while(!s.empty())
            s.pop();
        while(i < n)
        {
            //push j  when j<=a[i]
            while(j <= a[i])
            {
                s.push(j);
                j++;
            }
            //pop s.top if s.top() == a[i]
            while(!s.empty() && s.top() == a[i])
            {
                s.pop();
                i++;
            }
            //根據LIFO, s.top()永遠應該<=a[i]
            if(!s.empty() && s.top()>a[i])
                break;
        }
        if(s.empty())
            printf("Yes\n");
        else
            printf("No\n");
      }
      printf("\n");
    }
    return 0;
}

圖1-4 TOJ 1036 Rails 的參考代碼