栈学习笔记

栈

栈是特殊的链表，只能在表尾进行插入(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!
");
        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
");
        else
            printf("No
");
      }
      printf("
");
    }
    return 0;
}

图1-4 TOJ 1036 Rails 的参考代码