参考：
总结
本系列为C++数据结构系列，会介绍 线性结构，简单树，特殊树，简单图等。本文为线性结构部分。
大纲要求
- 线性结构
【 3 】链表：单链表、双向链表、循环链表
【 3 】栈
【 3 】队列
线性结构-栈
栈是Stack一个后进先出Last In First Out,LIFO的线性表，他要求只在表尾对数据执行删除和插入等操作。
栈就是一个线性表，可以是数组、也可以是链表。但它的操作有别于一般的线性表。栈的元素必须先进后出，也就是先进入栈的元素必须后出栈。而不能像一般的链表或数组那样从任意位置读取元素。
栈的操作只能在线性表的表尾进行，这个标为被称为栈的栈顶top，相应的表头被称为栈的栈底bottom
栈的数据必须从栈顶进入，也必须从栈顶取出，先入栈的数据在后入栈的数据下面。
栈中不含有任何数据时的状态叫作空栈，此时栈顶top等于栈底bottom。
回文匹配
#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; //l求字符串的中点 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--; } if(top==0) printf("yes"); else printf("no"); getchar(); getchar(); return 0; }
小猫钓鱼的故事
#include <stdio.h> struct queue { int data[100];//100 int head; int tail; }; struct stack { int data[10]; int top; }; int main ( ) { struct queue q1,q2; struct stack s; int book[10]= {0}; int i,t; //初始化队列 q1.head=1; q1.tail=1; q2.head=1; q2.tail=1; // 初始化栈 s.top=0; //int q1_data[7]= {0,2,4,1,2,5,6}; //初始化标记数组，标记哪些牌在桌上 for(i=1; i<=6; i++) { scanf("%d",&q1.data[q1.tail]); //q1.data[q1.tail]=q1_data[i]; q1.tail++; } //int q2_data[7]= {0,3,1,3,5,6,4}; //初始化标记数组，标记哪些牌在桌上 for(i=1; i<=6; i++) { scanf("%d",&q2.data[q2.tail]); //q2.data[q1.tail]=q2_data[i]; q2.tail++; } //当队列不为空时执行循环 while(q1.head<q1.tail && q2.head<q2.tail) { t=q1.data[q1.head];//q1取出一张牌 printf("q1---> t %d , book[t] %d \n",&t,&book[t]); // 判断q1当前打出的牌能否赢牌 if(book[t]==0)//表明桌面上没有牌面为t的牌 { // q1次轮没有赢牌 q1.head++;//把q1打出的牌出列 s.top++; s.data[s.top]=t;//把打出的牌t放在桌上，入栈 book[t]=1;//标记桌上有牌面为t的牌 } else { //q1可以赢牌 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--; //栈中少了一张牌，栈顶减一 } } //q2出一张牌 t=q2.data[q2.head]; printf("q2---> t %d , book[t] %d \n",&t,&book[t]); // 判断q2当前打出的牌能否赢牌 if(book[t]==0)//表明桌面上没有牌面为t的牌 { // q2次轮没有赢牌 q2.head++;//把q1打出的牌出列 s.top++; s.data[s.top]=t;//把打出的牌t放在桌上，入栈 book[t]=1;//标记桌上有牌面为t的牌 } else { //q2可以赢牌 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("q1赢win\n"); printf("q1当前手中的牌是："); 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("q2赢win\n"); printf("q2当前手中的牌是："); 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; }
