线性表

线性表是“所有元素排成一行”的数据结构。除了第一个元素之外，所有元素都有一个“前一个元素”；除了最后一个元素外，所有元素都有“后一个元素”

环状结构也经常转化为线性结构——只需要从某个元素处吧环切断，就变成了链。

---

队列(queue/First In ,First out)例：

【卡片游戏】
桌上有一叠牌，从第一张牌开始从上往下依次编号为1~n，当至少还剩两张牌是进行以下操作：把第一张牌扔掉，然后把新的第一张放到整叠牌的最后。
输入n，输出每次扔掉的牌，以及最后剩下的牌。
样例输入：7
样例输出：1 3 5 7 4 2 6

类似这个卡片游戏的结构我们称之为队列，其特点是，先进的元素先被移出队列，后进的元素后被移出队列。

C++提供一种STL队列，代码如下

#include <cstdio>
#include <queue>
using namespace std;
queue <int> q;  //定义q为一个队列类型，该队列每个元素的类型为int
int main()
{
      int n;
      scanf("%d", &n);
      for (int i=0; i < n; i++)
            q.push(i+1);    //初始化队列，也就是每次循环在q队列的末尾添加一个大小为（i+1）的int元素
      while (!q.empty())  //当队列q为空时返回值true，所以当q为空时退出循环
      {
            printf("%d ", q.front());    //打印首元素
            q.pop();                          //抛弃队首元素
            q.push(q.front());            //吧队首元素加入队尾
            q.pop();                          //抛弃队首元素
       }
      return 0;
}

---

栈(stack/Last In First Out)例：

【铁轨问题】
假设有n节车厢，编号分别为1到n，它们随机排序，并从A驶入station，请问借助station是否可以按照n到1的编号重新排序整个车厢。

车厢可以在station中进行的操作：
1、在A方向未进station的车厢驶入station
2、在station内的车厢向B方向驶出station

因为较早在station内的车厢可能会受后面进station的车厢妨碍，所以需要将后来进的车厢驶出到B，或者返回到A（不如后来的车厢不要先进站了），该较早入station的车厢才能向B方向驶出

车站模型

C++提供这种STL栈，代码如下

#include <cstdio>
#include <stack>
using namespace std;
const int MAXN = 1000 + 10;
int n, target[MAXN];
int main()
{
      while(scanf("%d", &n)  == 1) 
      {
            stack<int> s;
            int A = 1, B = 1;
            for (int i=1; i <= n; i++)
                  scanf("%d", &target[i]);
            int ok=1;
            while (B <= n)
            {
                  if (A == target[B]) {A++; B++;}
                  else if (!s.empty() && s.top() == target[B]) { s.pop(); B++; }
                  else if (A <= n) s.push(A++);
                  else { ok = 0; break;}
            }
            printf("%s\n", ok ? "Yes" : "No");
      }
      return 0;
}

---

链表

链表是一种数据类型，它的特点是，链表中的任何一个元素在记录其本身值的同时，记录该元素的相邻元素的地址（单向，双向）
我们操纵一个线性表的数据时候，链表可以帮助我们快速在任一位置插入或删除一个数(相比将整个列表的数后移一定位数然后插入值)。
但在链表中，按顺序查询一个数的位置（地址/存放位置）通常要花费大量时间，如何优化这一寻找过程便是一个难题

单向链表的倒序操作
以下抽象演示了链表结构与操作

#include <cstdio>
#define LEN 10000
int num[LEN],left[LEN],right[LEN];
//我们将数组第一个元素作为空节点，连接链表的第一个元素 
void link(int x,int y)  //将x,y两个节点连接起来 
{
    right[x]=y;
    right[y]=x;
}
void add(int k,int position)  //这个是在（num中存放的第k个数在链表中的位置）上往后添加一个数 
{
    scanf("%d",&num[position]);
    int r=right[k];
    link(k,position);
    link(position,r);
}
void del(int k) //在链表中删除num存放的第k个数 
{
    link(left[k],right[k]); //直接将该数在链表中的左右节点连接 
}
int find(int k)     //暴力查找链表中的第k个数在num中的位置（没有优化） 
{
    p=0;
    while (k--)
        p=right[p];
    return p;
}