C语言队列课件

第三章栈和队列重点难点掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们；熟练掌握栈类型的两种实现方法；熟练掌握循环队列和链队列的基本操作实现算法；理解递归算法执行过程中栈的状态变化过程，便于更好地使用递归算法。

典型例题1.设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

【解】(1)出栈序列为：1324(2)不能得到1423序列。

因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push(3),Push(4),Pop()。

这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。

能得到1432的出栈序列。

具体操作为：Push(1),Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是：1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43122.循环队列的优点是什么? 如何判别它的空和满?【解】循环队列的优点是：它可以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用。

队列是一种特殊的线性表，队列中所有的插入均限定在表的一端进行，而所有的删除则限定在表的另一端进行。

允许插入的一端称为队尾，允许删除的一端称为队头。

队列的特点是先进先出。

下面在VC6环境中用纯C语言编程风格（主函数用int main() ）编写小游戏贪吃蛇；蛇身增长数据用队列数据结构记录。

#include <windows.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#define S_SIZE 16#define S_LEN 300#define MOVET 1#define MOVEB 2#define MOVEL 3#define MOVER 4#define MOVE_L_T 5#define MOVE_L_B 6#define MOVE_R_T 7#define MOVE_R_B 8#define MOVE_TB 9#define MOVE_LR 10#define TABLE_TX 80#define TABLE_TY 80#define TABLE_RX 560#define TABLE_RY 400typedef struct SNAKE{int x;int y;int m_state;int s_g;}m_snake;typedef struct GAMESNAKE{m_snake s_h;m_snake s_bn[S_LEN];m_snake s_bo[S_LEN];m_snake s_t;POINT s_H_h;int front;int rear;}Gamesnake;Gamesnake *tmp;typedef struct FOOD{int fx;int fy;int fs_g;int fk;}Food;Food *ft;//-----------头部数据列表--------//向上数据POINT H_top[11]={4,1,2,3,2,12,3,14,3,16,13,16,13,14,14,12,14,3,12,1,4,1}; POINT H_te1[5]={4,3,4,5,6,5,6,3,4,3};POINT H_te2[5]={10,3,10,5,12,5,12,3,10,3};//向左数据POINT H_left[11]={1,4,1,12,3,14,12,14,14,13,16,13,16,3,14,3,12,2,3,2,1,4}; POINT H_le1[5]={3,4,3,6,5,6,5,4,3,4};POINT H_le2[5]={3,10,3,12,5,12,5,10,3,10};//向右数据POINT H_right[11]={0,3,0,13,2,13,4,14,13,14,15,12,15,4,13,2,4,2,2,3,0,3}; POINT H_re1[5]={11,4,11,6,13,6,13,4,11,4};POINT H_re2[5]={11,10,11,12,13,12,13,10,11,10};//向下数据POINT H_bottom[11]={3,0,3,2,2,4,2,13,4,15,12,15,14,13,14,4,13,2,13,0,3,0}; POINT H_be1[5]={4,11,4,13,6,13,6,11,4,11};POINT H_be2[5]={10,11,10,13,12,13,12,11,10,11};//-------------身体数据列表------------//上下数据POINT B_tb[5]={3,0,3,16,13,16,13,0,3,0};//左右数据POINT B_lr[5]={0,3,0,13,16,13,16,3,0,3};//左上数据POINT B_lt[8]={3,8,3,16,13,16,13,13,16,13,16,3,8,3,3,8};//左下数据POINT B_lb[8]={3,0,3,8,8,13,16,13,16,3,13,3,13,0,3,0};//右上数据POINT B_rt[8]={0,3,0,13,3,13,3,16,13,16,13,8,8,3,0,3};//右下数据POINT B_rb[8]={0,3,0,13,8,13,13,8,13,0,3,0,3,3,0,3};//-------------尾部数据列表---------------//向上数据POINT T_top[9]={3,0,3,16,6,16,6,8,10,8,10,16,13,16,13,0,3,0};//向左数据POINT T_left[9]={0,3,0,13,16,13,16,10,8,10,8,6,16,6,16,3,0,3};//向右数据POINT T_right[9]={0,3,0,6,8,6,8,10,0,10,0,13,16,13,16,3,0,3};//向下数据POINT T_bottom[9]={3,0,3,16,13,16,13,0,10,0,10,8,6,8,6,0,3,0};//-------------食物数据列表----------------//食用果数据POINT F_H[9]={4,6,4,10,6,12,10,12,12,10,12,6,10,4,6,4,4,6};//毒果数据POINT S_H[9]={5,7,5,9,7,12,9,12,11,9,11,7,9,4,7,4,5,7};HWND hwnd;static HFONT mFont=CreateFont(-12,0,0,0,400,0,0,0,GB2312_CHARSET,0,0,0,FF_MODERN,"宋体");LRESULT CALLBACK WndProc(HWND hwnd, UINT message,WPARAM wparam,LPARAM lparam){switch(message){case WM_DESTROY:PostQuitMessage(0);break;}return DefWindowProc(hwnd,message,wparam,lparam);}HWND initgraph(int width,int height){HINSTANCE hist=0;WNDCLASS wc;wc.style=CS_HREDRAW|CS_VREDRAW;wc.lpfnWndProc=(WNDPROC)WndProc;wc.cbClsExtra=0;wc.cbWndExtra=0;wc.hInstance=hist;wc.hIcon=LoadIcon(NULL,IDI_WINLOGO);wc.hCursor=LoadCursor(NULL,IDC_ARROW);wc.hbrBackground=(HBRUSH)(COLOR_WINDOW+2);wc.lpszMenuName=NULL;wc.lpszClassName="tm1";RegisterClass(&wc);hwnd=CreateWindow("tm1","贪吃蛇游戏（C语言数据描述——队列）",WS_OVERLAPPEDWINDOW,0,0,width,height,HWND_DESKTOP,NULL,hist,NULL);ShowWindow(hwnd,1);UpdateWindow(hwnd);return hwnd;}int getkeystate(int vk){if(GetAsyncKeyState(vk)&0x8000)return true;elsereturn false;}void ploy(POINT pt[],int ncount){HPEN hp;hp=CreatePen(PS_SOLID,1,RGB(255,255,255));HDC hdc;hdc=GetDC(hwnd);SelectObject(hdc,hp);Polyline(hdc,pt,ncount);DeleteObject(hp);::DeleteDC(hdc);}void drawploy(int x,int y,POINT p[],int ncount){POINT tmp[11];int i;for(i=0;i<ncount;i++){tmp[i].x=p[i].x+x;tmp[i].y=p[i].y+y;}ploy(tmp,ncount);}void bar(int lx,int ty,int rx,int by){HBRUSH hb;HDC hdc;hdc=GetDC(hwnd);hb=CreateSolidBrush(RGB(0,0,0));SelectObject(hdc,hb);HPEN hp;hp=CreatePen(PS_SOLID,1,RGB(255,255,255));SelectObject(hdc,hp);Rectangle(hdc,lx,ty,rx,by);DeleteObject(hb);DeleteObject(hp);::DeleteDC(hdc);}void setfont(int size,char *style){mFont=CreateFont(size,0,0,0,400,0,0,0,GB2312_CHARSET,0,0,0,FF_MODERN,style); }void outtextxy(int x,int y,char *string){HDC hdc;hdc=GetDC(hwnd);SelectObject(hdc,mFont);SetBkMode(hdc,TRANSPARENT);SetTextColor(hdc,RGB(255,255,255));TextOut(hdc,x,y,string,strlen(string));::DeleteDC(hdc);}void initsnake(Gamesnake *t){int sx,sy;sx=320;sy=240;t->rear=0;t->s_h.m_state=MOVET;t->s_h.x=sx;t->s_h.y=sy;t->s_h.s_g=MOVET;t->s_H_h.x=t->s_h.x;t->s_H_h.y=t->s_h.y;t->s_bn[t->rear].m_state=MOVET;t->s_bn[t->rear].x=sx;t->s_bn[t->rear].y=sy+S_SIZE;t->s_bn[t->rear].s_g=MOVE_TB;t->s_t.m_state=MOVET;t->s_t.s_g=MOVET;t->s_t.x=sx;t->s_t.y=t->s_bn[t->rear].y+S_SIZE;t->s_bo[t->rear].m_state=MOVET;t->s_bo[t->rear].x=sx;t->s_bo[t->rear].y=sy+S_SIZE;t->s_bo[t->rear].s_g=MOVE_TB;}void drawsnake(Gamesnake *t){bar(TABLE_TX-2,TABLE_TY-2,TABLE_RX+2,TABLE_RY+2);switch(t->s_h.s_g){case MOVET:drawploy(t->s_h.x,t->s_h.y,H_top,11);drawploy(t->s_h.x,t->s_h.y,H_te1,5);drawploy(t->s_h.x,t->s_h.y,H_te2,5);break;case MOVEB:drawploy(t->s_h.x,t->s_h.y,H_bottom,11);drawploy(t->s_h.x,t->s_h.y,H_be1,5);drawploy(t->s_h.x,t->s_h.y,H_be2,5);break;case MOVEL:drawploy(t->s_h.x,t->s_h.y,H_left,11);drawploy(t->s_h.x,t->s_h.y,H_le1,5);drawploy(t->s_h.x,t->s_h.y,H_le2,5);break;case MOVER:drawploy(t->s_h.x,t->s_h.y,H_right,11);drawploy(t->s_h.x,t->s_h.y,H_re1,5);drawploy(t->s_h.x,t->s_h.y,H_re2,5);break;}for(t->front=0;t->front<=t->rear;t->front++){switch(t->s_bn[t->front].s_g){case MOVE_L_T:drawploy(t->s_bn[t->front].x,t->s_bn[t->front].y,B_lt,8);break;case MOVE_L_B:drawploy(t->s_bn[t->front].x,t->s_bn[t->front].y,B_lb,8);break;case MOVE_R_T:drawploy(t->s_bn[t->front].x,t->s_bn[t->front].y,B_rt,8);break;case MOVE_R_B:drawploy(t->s_bn[t->front].x,t->s_bn[t->front].y,B_rb,8);break;case MOVE_TB:drawploy(t->s_bn[t->front].x,t->s_bn[t->front].y,B_tb,5);break;case MOVE_LR:drawploy(t->s_bn[t->front].x,t->s_bn[t->front].y,B_lr,5);break;}}switch(t->s_t.s_g){case MOVET:drawploy(t->s_t.x,t->s_t.y,T_top,9);break;case MOVEB:drawploy(t->s_t.x,t->s_t.y,T_bottom,9);break;case MOVEL:drawploy(t->s_t.x,t->s_t.y,T_left,9);break;case MOVER:drawploy(t->s_t.x,t->s_t.y,T_right,9);break;}}void move(int x,int y,int mstate,int s_g,Gamesnake *t){t->s_bn[0].x=x;t->s_bn[0].y=y;t->s_bn[0].m_state=mstate;t->s_bn[0].s_g=s_g;for(t->front=1;t->front<=t->rear;t->front++){t->s_bn[t->front].m_state=t->s_bo[t->front-1].m_state;t->s_bn[t->front].s_g=t->s_bo[t->front-1].s_g;t->s_bn[t->front].x=t->s_bo[t->front-1].x;t->s_bn[t->front].y=t->s_bo[t->front-1].y;}t->s_t.m_state=t->s_bo[t->rear].m_state;t->s_t.x=t->s_bo[t->rear].x;t->s_t.y=t->s_bo[t->rear].y;t->s_t.s_g=t->s_t.m_state;for(t->front=0;t->front<=t->rear;t->front++){t->s_bo[t->front].m_state=t->s_bn[t->front].m_state;t->s_bo[t->front].s_g=t->s_bn[t->front].s_g;t->s_bo[t->front].x=t->s_bn[t->front].x;t->s_bo[t->front].y=t->s_bn[t->front].y;}}void movesnake(Gamesnake *t){switch(t->s_h.m_state){case MOVET:if(t->s_H_h.y>TABLE_TY){move(t->s_h.x,t->s_h.y,MOVET,9,t);t->s_h.y-=S_SIZE;t->s_H_h.y=t->s_h.y;}break;case MOVEB:if(t->s_H_h.y<TABLE_RY){move(t->s_h.x,t->s_h.y,MOVEB,9,t);t->s_h.y+=S_SIZE;t->s_H_h.y+=S_SIZE;}break;case MOVEL:if(t->s_H_h.x>TABLE_TX){move(t->s_h.x,t->s_h.y,MOVEL,10,t);t->s_h.x-=S_SIZE;t->s_H_h.x-=S_SIZE;}break;case MOVER:if(t->s_H_h.x<TABLE_RX){move(t->s_h.x,t->s_h.y,MOVER,10,t);t->s_h.x+=S_SIZE;t->s_H_h.x+=S_SIZE;}break;}drawsnake(t);}void selectmove(Gamesnake *t){if(t->s_h.m_state!=MOVEL&&t->s_h.m_state!=MOVER){if(getkeystate(VK_LEFT)){if(t->s_h.m_state==MOVET)move(t->s_h.x,t->s_h.y,MOVEL,MOVE_R_T,t);if(t->s_h.m_state==MOVEB)move(t->s_h.x,t->s_h.y,MOVEL,MOVE_R_B,t);t->s_h.m_state=MOVEL;t->s_h.s_g=MOVEL;t->s_h.x-=S_SIZE;t->s_H_h.x-=S_SIZE;t->s_H_h.y=t->s_h.y;}if(getkeystate(VK_RIGHT)){if(t->s_h.m_state==MOVET)move(t->s_h.x,t->s_h.y,MOVER,MOVE_L_T,t);if(t->s_h.m_state==MOVEB)move(t->s_h.x,t->s_h.y,MOVER,MOVE_L_B,t);t->s_h.m_state=MOVEL;t->s_h.m_state=MOVER;t->s_h.s_g=MOVER;t->s_h.x+=S_SIZE;t->s_H_h.x=t->s_h.x+S_SIZE;t->s_H_h.y=t->s_h.y;}}if(t->s_h.m_state!=MOVET&&t->s_h.m_state!=MOVEB){if(getkeystate(VK_UP)){if(t->s_h.m_state==MOVEL)move(t->s_h.x,t->s_h.y,MOVET,MOVE_L_B,t);if(t->s_h.m_state==MOVER)move(t->s_h.x,t->s_h.y,MOVET,MOVE_R_B,t);t->s_h.m_state=MOVET;t->s_H_h.y-=S_SIZE;t->s_h.y-=S_SIZE;t->s_H_h.x=t->s_h.x;t->s_h.s_g=MOVET;}if(getkeystate(VK_DOWN)){if(t->s_h.m_state==MOVEL)move(t->s_h.x,t->s_h.y,MOVEB,MOVE_L_T,t);if(t->s_h.m_state==MOVER)move(t->s_h.x,t->s_h.y,MOVEB,MOVE_R_T,t);t->s_h.m_state=MOVEB;t->s_h.y+=S_SIZE;t->s_H_h.x=t->s_h.x;t->s_h.s_g=MOVEB;t->s_H_h.y=t->s_h.y+S_SIZE;}}drawsnake(t);}void setfood(Gamesnake *t,Food *f){int i,j,w,h,pos[20][30];time_t st;st=time(NULL);if(st%10==0){for(i=0;i<20;i++)for(j=0;j<30;j++)pos[i][j]=0;w=(t->s_h.x-TABLE_TX)/S_SIZE;h=(t->s_h.y-TABLE_TY)/S_SIZE;pos[h][w]=1;w=(t->s_t.x-TABLE_TX)/S_SIZE;h=(t->s_t.y-TABLE_TY)/S_SIZE;pos[h][w]=1;for(i=0;i<=t->rear;i++){w=(t->s_bn[i].x-TABLE_TX)/S_SIZE;h=(t->s_bn[i].y-TABLE_TY)/S_SIZE;pos[h][w]=1;}srand(time(NULL));while(1){w=rand()%30;h=rand()%20;if(pos[h][w]==0){f->fk=1;f->fs_g=rand()%2;f->fx=w*S_SIZE+TABLE_TX;f->fy=h*S_SIZE+TABLE_TY;break;}}}if(f->fk){if(f->fs_g)drawploy(f->fx,f->fy,F_H,9);elsedrawploy(f->fx,f->fy,S_H,9);}}void add_s_bn(Gamesnake *t){t->rear++;if(t->rear>S_LEN-1){setfont(-24,"宋体");outtextxy(150,220,"蛇太长！");}else{t->s_bn[t->rear].m_state=t->s_t.m_state;t->s_bn[t->rear].x=t->s_t.x;t->s_bn[t->rear].y=t->s_t.y;if(t->s_t.m_state==MOVET){t->s_bn[t->rear].s_g=MOVE_TB;t->s_t.y+=S_SIZE;}if(t->s_t.m_state==MOVEB){t->s_bn[t->rear].s_g=MOVE_TB;t->s_t.y-=S_SIZE;}if(t->s_t.m_state==MOVEL){t->s_bn[t->rear].s_g=MOVE_LR;t->s_t.x+=S_SIZE;}if(t->s_t.m_state==MOVER){t->s_bn[t->rear].s_g=MOVE_LR;t->s_t.x-=S_SIZE;}t->s_bo[t->rear].m_state=t->s_bn[t->rear].m_state;t->s_bo[t->rear].s_g=t->s_bn[t->rear].s_g;t->s_bo[t->rear].x=t->s_bn[t->rear].x;t->s_bo[t->rear].y=t->s_bn[t->rear].y;}}void OutScore(Gamesnake *t){char s[100];sprintf(s,"%d",t->rear*100);bar(250,30,350,60);setfont(-16,"宋体");outtextxy(260,35,s);}void getfood(Gamesnake *t,Food *f){if(f->fk&&f->fs_g){if(t->s_h.x==f->fx&&t->s_h.y==f->fy){add_s_bn(t);OutScore(t);f->fk=0;}}}void delay(int val){int i,vk=0;while(1){vk++;for(i=0;i<100000;i++);;if(vk>val)break;}}int gameover(Gamesnake *t,Food *f){if(t->s_H_h.x==TABLE_TX||t->s_H_h.x==TABLE_RX)return true;if(t->s_H_h.y==TABLE_TY||t->s_H_h.y==TABLE_RY)return true;for(t->front=0;t->front<=t->rear;t->front++){if(t->s_h.m_state==MOVET){if(t->s_bn[t->front].x==t->s_H_h.x&&t->s_bn[t->front].y+S_SIZE==t->s_H_h.y) return true;if(t->s_t.x==t->s_H_h.x&&t->s_t.y+S_SIZE==t->s_H_h.y)return true;if(f->fk&&f->fs_g==0)if(t->s_H_h.x==f->fx&&t->s_H_h.y==f->fy+S_SIZE)return true;}if(t->s_h.m_state==MOVEL){if(t->s_bn[t->front].x+S_SIZE==t->s_H_h.x&&t->s_bn[t->front].y==t->s_H_h.y) return true;if(t->s_t.x+S_SIZE==t->s_H_h.x&&t->s_t.y==t->s_H_h.y)return true;if(f->fk&&f->fs_g==0)if(t->s_H_h.x==f->fx+S_SIZE&&t->s_H_h.y==f->fy)return true;}if(t->s_h.m_state==MOVEB||t->s_h.m_state==MOVER){if(t->s_bn[t->front].x==t->s_H_h.x&&t->s_bn[t->front].y==t->s_H_h.y)return true;if(t->s_t.x==t->s_H_h.x&&t->s_t.y==t->s_H_h.y)return true;if(f->fk&&f->fs_g==0)if(t->s_H_h.x==f->fx&&t->s_H_h.y==f->fy)return true;}}if(f->fk&&f->fs_g==0)if(t->s_h.x==f->fx&&t->s_h.y==f->fy)return true;return false;}void g_draw(){if(!gameover(tmp,ft)){movesnake(tmp);selectmove(tmp);setfood(tmp,ft);getfood(tmp,ft);delay(2000);}else{setfont(-24,"宋体");outtextxy(270,430,"游戏结束！");}}void DrawFunc(void draw()){MSG msg;BOOL fmsg;PeekMessage(&msg,NULL,0U,0U,PM_NOREMOVE);while(msg.message!=WM_QUIT){fmsg=PeekMessage(&msg,NULL,0U,0U,PM_REMOVE);if(fmsg){TranslateMessage(&msg);DispatchMessage(&msg);}elsedraw();}}int main(){initgraph(640,520);tmp=(Gamesnake *)malloc(sizeof(Gamesnake));ft=(Food *)malloc(sizeof(Food));initsnake(tmp);setfont(-16,"宋体");outtextxy(200,35,"分数：");DrawFunc(g_draw);return 0;}关于贪吃蛇游戏：（1）、蛇的组合：头部、身体和尾巴组成。

C语⾔基础——队列详细讲解！队列（Queue）⼀般的顺序队列：由于这种结构会有假溢出的情况，所以⼀般不选择这种队列，⽽更多的使⽤循环队列。

循环队列：判断队列满的情况：1、count来计数；通常使⽤countCount等于队列的MAXSIZE2、Flag标志 int⼊队列 flag=1 出队列flag=0Front=rear&&flag==03、把⼀个存储单元空出来，不存放数据Rear 1==front注意事项：（不要）顺序结构，SeqQueue myQueue；链式：malloc（C语⾔C 交流学习群560655063）初始化：//（1）初始化void SeqQueueInit(SeqQueue *Q){Q->front = 0;Q->rear = 0;Q->count = 0;}//（2）⼊队int SeqQueueIn(SeqQueue *Q, intdata){if (Q->count > 0 && Q->rear == Q->front){printf('队列满！\n');return 0;}else{Q->data[Q->rear] = data; //把数据赋给队尾元素Q->rear = (Q->rear 1) % MAXSIZE; //让对位移动⼀个位置 1Q->count ; //计数器 1return 1;}}//（3）出队列int SeqQueueOut(SeqQueue *Q,int *data){if (Q->count == 0){printf('队列空\n');return 0;}else{*data = Q->data[Q->front];Q->front = (Q->front 1) % MAXSIZE;Q->count--;}}//释放：不要，数组是连续的存储空间，队列的⼤⼩10，队列⾥⾯有没有内容，都是10个⼤⼩。