這篇先寫前三節，下一篇在把這一張剩下的寫完

第2章 棧、隊列、鏈表

• • 第一節 解密QQ號——隊列
  • 第二節 解密回文——棧
  • 第三節 紙牌游戲——小貓釣魚

第一節 解密QQ號——隊列

這一節通過解密一個QQ號來引入隊列，解密這個QQ號的方法是首先將第1個數刪除，緊接著將第2個數放到這串數的末尾，再將第3個數刪除并將第4個數放到這串數的末尾，再將第5個數刪除……知道剩下最后一個數，將最后一個屬也刪除。按照剛才刪除的順序，把這些刪除的數連在一起就是小哈的QQ。

隊列有兩個變量，兩個整型變量head和tail。head記錄隊列的隊首（即第一位），tail用來記錄隊列的隊尾（即最后一位）的下一個位置。
注意：head指向的是第一位，但tail指向的卻不是最后一位，而是最后一位的下一位，因為當隊列只剩下一個元素時，head和tail會重合，會帶來麻煩。
隊首和隊尾重合時，隊列為空。
刪除一個數：head++
增加一個屬：q[tail]=num;tail++;
書中將數組的0號元素賦值為0，即將0號元素去除，從1號開始，方便計數，且將數組定義為102個，這里我將代碼稍稍改動。

#include <stdio.h> int main() { int q[20]={6,3,1,7,5,8,9,2,4},head,tail; int i; //初始化隊列head=0; tail=9; //隊列中已經有9個元素了，tail指向隊尾的后一個位置 while(head<tail) //當隊列不為空的時候執行循環{ //打印隊首并將隊首出隊printf("%d ",q[head]); head++; //先將新隊首的數添加到隊尾q[tail]=q[head]; tail++; //再將隊首出隊head++; } getchar();getchar(); return 0; }

隊列時一種特殊的線性結構，只允許在隊列的首部（head）進行刪除操作，稱為“出隊”；而在隊列的尾部（tail）進行插入操作，稱為“入隊”。當隊列中沒有元素時（head==tail），稱為空隊列。
隊列，先進先出（First In First Out，FIFO）
將隊列的三個基本元素（一個數組，兩個變量）封裝為一個結構體類型，代碼如下：

struct queue { int data[100];//隊列的主體，用來存儲內容int head;//隊首int tail;//隊尾 }; //定義結構體類型，通常將其放在main函數的外面 //注意結構體的定義末尾有個； //

定義結構體變量：

struct queue q; //struct queque 是一個整體，不能直接寫queque q; //使用成員運算符（點號運算符）來訪問結構體變量的成員

下面是完整的使用結構體來實現的隊列操作。

#include <stdio.h> struct queue { int data[100];//隊列的主體，用來存儲內容int head;//隊首int tail;//隊尾 }; int main() { struct queue q; int i; //初始化隊列q.head=0; q.tail=0; for(i=1;i<=9;i++) { //依次向隊列插入9個數scanf("%d",&q.data[q.tail]); q.tail++; } while(q.head<q.tail) //當隊列不為空的時候執行循環{ //打印隊首并將隊首出隊printf("%d ",q.data[q.head]); q.head++; //先將新隊首的數添加到隊尾q.data[q.tail]=q.data[q.head]; q.tail++; //再將隊首出隊q.head++; } getchar();getchar(); return 0; }

第二節 解密回文——棧

本節通過判斷是否是回文來引入棧的概念，判斷回文的方法，先將要判斷的字符前一半如棧，然后當前棧的字符依次出棧，看能否與后一半字符依次匹配，匹配即回文。

棧：后進后出，只能在一端進行插入和刪除操作。
棧只需要一個一維數組和一個指向頂棧的變量top，通過top來對棧進行插入和刪除操作。
因為top指向的是當前棧頂的變量，所以進棧的代碼是：

s[++top]=a[i]; //先將top指向下一個位置，然后賦值

下面是書中判斷是否回文的代碼：

#include <stdio.h> #include <string.h> int main() { char a[101],s[101]; int i,len,mid,next,top; gets(a); //讀入一行字符串len=strlen(a); //求字符串的長度mid=len/2-1; //求字符串的中點top=0;//棧的初始化//將mid前的字符依次入棧for(i=0;i<=mid;i++) s[++top]=a[i]; //判斷字符串的長度是奇數還是偶數，并找出需要進行字符匹配的起始下標 if(len%2==0) next=mid+1; else next=mid+2; //開始匹配for(i=next;i<=len-1;i++) { if(a[i]!=s[top]) break; top--; } //如果top的值為0，則說明棧內所有的字符都被一一匹配了if(top==0) printf("YES"); else printf("NO"); getchar();getchar(); return 0; }

堆棧最早由 Alan M. Turing（艾倫·圖靈）于 1946 年提出，當時是為了解決子程序的調用和返回。艾倫·圖靈這個大帥哥可是個大牛人，圖靈獎就是以他的名字命名的。如果你對他感興趣不妨去讀一讀《艾倫·圖靈傳：如謎的解謎者》和《圖靈的秘密》。

第三節 紙牌游戲——小貓釣魚

本節是由我們小時候玩的游戲，小貓釣魚引入，這個游戲大概就是兩個人一人一摞紙牌，按照一定順序，往上放牌，如果與之前放過的牌一致，就可以把這兩張牌之間的牌拿走（包括這兩張牌本身）放到自己手中牌的后面，最后手里沒有牌的一方為輸。

這個游戲相信大家小時候都玩過，但是用代碼來模擬這個游戲怎么實現呢，讓我們來看一下吧：

#include <stdio.h> struct queue { int data[1000]; int head; int tail; }; struct stack { int data[10]; int top; }; int main() { struct queue q1,q2; struct stack s; int book[10]; int i,t; //初始化隊列q1.head=1; q1.tail=1; q2.head=1; q2.tail=1; //初始化棧s.top=0; //初始化用來標記的數組，用來標記哪些牌已經在桌上for(i=1;i<=9;i++) book[i]=0; //依次向隊列插入6個數//小哼手上的6張牌for(i=1;i<=6;i++) { scanf("%d",&q1.data[q1.tail]); q1.tail++; } //小哈手上的6張牌for(i=1;i<=6;i++) { scanf("%d",&q2.data[q2.tail]); q2.tail++; } while(q1.head<q1.tail && q2.head<q2.tail ) //當隊列不為空的時候執行循環{ t=q1.data[q1.head];//小哼出一張牌//判斷小哼當前打出的牌是否能贏牌if(book[t]==0) //表明桌上沒有牌面為t的牌{ //小哼此輪沒有贏牌q1.head++; //小哼已經打出一張牌，所以要把打出的牌出隊s.top++; s.data[s.top]=t; //再把打出的牌放到桌上，即入棧book[t]=1; //標記桌上現在已經有牌面為t的牌} else { //小哼此輪可以贏牌q1.head++;//小哼已經打出一張牌，所以要把打出的牌出隊q1.data[q1.tail]=t;//緊接著把打出的牌放到手中牌的末尾q1.tail++; while(s.data[s.top]!=t) //把桌上可以贏得的牌依次放到手中牌的末尾{ book[s.data[s.top]]=0;//取消標記q1.data[q1.tail]=s.data[s.top];//依次放入隊尾q1.tail++; s.top--; //棧中少了一張牌，所以棧頂要減1 } } t=q2.data[q2.head]; //小哈出一張牌//判斷小哈當前打出的牌是否能贏牌if(book[t]==0) //表明桌上沒有牌面為t的牌{ //小哈此輪沒有贏牌q2.head++; //小哈已經打出一張牌，所以要把打出的牌出隊s.top++; s.data[s.top]=t; //再把打出的牌放到桌上，即入棧book[t]=1; //標記桌上現在已經有牌面為t的牌 } else { //小哈此輪可以贏牌q2.head++;//小哈已經打出一張牌，所以要把打出的牌出隊q2.data[q2.tail]=t;//緊接著把打出的牌放到手中牌的末尾q2.tail++; while(s.data[s.top]!=t) //把桌上可以贏得的牌依次放到手中牌的末尾{ book[s.data[s.top]]=0;//取消標記q2.data[q2.tail]=s.data[s.top];//依次放入隊尾q2.tail++; s.top--; } } } if(q2.head==q2.tail) { printf("小哼win\n"); printf("小哼當前手中的牌是"); for(i=q1.head;i<=q1.tail-1;i++) printf(" %d",q1.data[i]); if(s.top>0) //如果桌上有牌則依次輸出桌上的牌{ printf("\n桌上的牌是"); for(i=1;i<=s.top;i++) printf(" %d",s.data[i]); } else printf("\n桌上已經沒有牌了"); } else { printf("小哈win\n"); printf("小哈當前手中的牌是"); for(i=q2.head;i<=q2.tail-1;i++) printf(" %d",q2.data[i]); if(s.top>0) //如果桌上有牌則依次輸出桌上的牌{ printf("\n桌上的牌是"); for(i=1;i<=s.top;i++) printf(" %d",s.data[i]); } else printf("\n桌上已經沒有牌了"); } getchar();getchar(); return 0; }

最后來個個人小總結吧：
1.隊列：先進先出（后進后出），需要三個變量，一個數組（用來存放數據），一個head變量（記錄隊列的隊首），一個tail變量（記錄隊列的隊尾的下一個位置）
2.棧：后進先出（先進后出），需要兩個變量，一個數組（用來存放數據），一個top變量（指向棧頂）

謝謝你的堅持閱讀ovo喲，讓我們一起加油吖

總結

以上是生活随笔為你收集整理的《啊哈！算法》笔记_Day02的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。