線性表是“所有元素排成一行”的數(shù)據(jù)結(jié)構(gòu)滑进。除了第一個(gè)元素之外，所有元素都有一個(gè)“前一個(gè)元素”拴曲；除了最后一個(gè)元素外窗骑，所有元素都有“后一個(gè)元素”

環(huán)狀結(jié)構(gòu)也經(jīng)常轉(zhuǎn)化為線性結(jié)構(gòu)——只需要從某個(gè)元素處吧環(huán)切斷，就變成了鏈耳鸯。

隊(duì)列(queue/First In ,First out)例：

【卡片游戲】
桌上有一疊牌湿蛔，從第一張牌開始從上往下依次編號為1~n，當(dāng)至少還剩兩張牌是進(jìn)行以下操作：把第一張牌扔掉片拍，然后把新的第一張放到整疊牌的最后煌集。
輸入n妓肢，輸出每次扔掉的牌捌省，以及最后剩下的牌。
樣例輸入：7
樣例輸出：1 3 5 7 4 2 6

類似這個(gè)卡片游戲的結(jié)構(gòu)我們稱之為隊(duì)列碉钠，其特點(diǎn)是纲缓，先進(jìn)的元素先被移出隊(duì)列，后進(jìn)的元素后被移出隊(duì)列喊废。

C++提供一種STL隊(duì)列祝高，代碼如下

#include <cstdio>
#include <queue>
using namespace std;
queue <int> q;  //定義q為一個(gè)隊(duì)列類型，該隊(duì)列每個(gè)元素的類型為int
int main()
{
      int n;
      scanf("%d", &n);
      for (int i=0; i < n; i++)
            q.push(i+1);    //初始化隊(duì)列污筷，也就是每次循環(huán)在q隊(duì)列的末尾添加一個(gè)大小為（i+1）的int元素
      while (!q.empty())  //當(dāng)隊(duì)列q為空時(shí)返回值true工闺，所以當(dāng)q為空時(shí)退出循環(huán)
      {
            printf("%d ", q.front());    //打印首元素
            q.pop();                          //拋棄隊(duì)首元素
            q.push(q.front());            //吧隊(duì)首元素加入隊(duì)尾
            q.pop();                          //拋棄隊(duì)首元素
       }
      return 0;
}

棧(stack/Last In First Out)例：

【鐵軌問題】
假設(shè)有n節(jié)車廂，編號分別為1到n，它們隨機(jī)排序陆蟆，并從A駛?cè)雜tation雷厂，請問借助station是否可以按照n到1的編號重新排序整個(gè)車廂。

車廂可以在station中進(jìn)行的操作：
1叠殷、在A方向未進(jìn)station的車廂駛?cè)雜tation
2改鲫、在station內(nèi)的車廂向B方向駛出station

因?yàn)檩^早在station內(nèi)的車廂可能會(huì)受后面進(jìn)station的車廂妨礙，所以需要將后來進(jìn)的車廂駛出到B林束，或者返回到A（不如后來的車廂不要先進(jìn)站了）像棘，該較早入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;
}

鏈表

鏈表是一種數(shù)據(jù)類型壶冒，它的特點(diǎn)是缕题，鏈表中的任何一個(gè)元素在記錄其本身值的同時(shí)，記錄該元素的相鄰元素的地址（單向胖腾，雙向）
我們操縱一個(gè)線性表的數(shù)據(jù)時(shí)候避除，鏈表可以幫助我們快速在任一位置插入或刪除一個(gè)數(shù)(相比將整個(gè)列表的數(shù)后移一定位數(shù)然后插入值)。
但在鏈表中胸嘁，按順序查詢一個(gè)數(shù)的位置（地址/存放位置）通常要花費(fèi)大量時(shí)間瓶摆，如何優(yōu)化這一尋找過程便是一個(gè)難題

單向鏈表的倒序操作

#include <cstdio>
#define LEN 10000
int num[LEN],left[LEN],right[LEN];
//我們將數(shù)組第一個(gè)元素作為空節(jié)點(diǎn)，連接鏈表的第一個(gè)元素 
void link(int x,int y)  //將x,y兩個(gè)節(jié)點(diǎn)連接起來 
{
    right[x]=y;
    right[y]=x;
}
void add(int k,int position)  //這個(gè)是在（num中存放的第k個(gè)數(shù)在鏈表中的位置）上往后添加一個(gè)數(shù) 
{
    scanf("%d",&num[position]);
    int r=right[k];
    link(k,position);
    link(position,r);
}
void del(int k) //在鏈表中刪除num存放的第k個(gè)數(shù) 
{
    link(left[k],right[k]); //直接將該數(shù)在鏈表中的左右節(jié)點(diǎn)連接 
}
int find(int k)     //暴力查找鏈表中的第k個(gè)數(shù)在num中的位置（沒有優(yōu)化） 
{
    p=0;
    while (k--)
        p=right[p];
    return p;
}