一.队列1.队列的顺序存储1.队列的定义队列(Qucue)简称队也是一种操作受限的线性表只允许在表的一端进行插入而在表的另一端进行删除。向队列中插入元素称为入队或进队;删除元素称为出队或离队。这和我们日常生活中的排队是一致的最早排队的也是最早离队的其操作的特性是先进先出(FirstInFirst Out,FIFO),如图所示。队头(Front):允许删除的一端也称队首。队尾(Rear):允许插入的一端。空队列:不含任何元素的空表。顺序队列的两种定义1.typedef int Data_t; typedef struct node { Data_t data; struct node *pnext; }Node_t; typedef struct lqueue { Node_t *phead; Node_t *ptail; int clen; }LQue_t;2.typedef struct{ Data_t data[MaxSize]; //用数组存放队列元素 int front,rear; //队首指针和队尾指针 }SqQueue;以第一种定义为例以下为相关CRUD功能实现LQue_t * create_link_queue() { LQue_t *pque malloc(sizeof(LQue_t)); if (NULL pque) { printf(malloc error\n); return NULL; } pque-phead NULL; pque-ptail NULL; pque-clen 0; return pque; } int is_empty(LQue_t *plink) { return NULL plink-phead; } int insert_link_queue(LQue_t* pque,int data) { Node_t *p malloc(sizeof(Node_t)); p-data data; p-pnext NULL; if(p NULL) { printf(malloc error\n); return -1; } if(pque-phead NULL) { pque-phead p; pque-ptail p; } else { pque-ptail-pnext p; pque-ptail p; } pque-clen; return 0; } void show_link_queue(LQue_t* pque) { if(is_empty(pque)) { return; } Node_t *ptmp pque-phead; while(ptmp) { printf(%d ,ptmp-data); ptmp ptmp-pnext; } printf(\n); } int pop_link_queue(LQue_t* pque,Data_t *pdata) { if(is_empty(pque)) { return -1; } Node_t *pnode pque-phead; pque-phead pnode-pnext; *pdata pnode-data; free(pnode); pque-clen--; if(pque-clen 0) { pque-ptail NULL; } return 0; } int get_link_queue_head(LQue_t *pque,Data_t *pdata) { if(is_empty(pque)) { return -1; } *pdata pque-phead-data;; return 0; } void destory_link_queue(LQue_t *pque) { // if(is_empty(pque)) // { // return ; // } // while(pque-phead) // { // Node_t *pfree pque-phead; // pque-phead pfree-pnext; // free(pfree); // pque-clen--; // } // pque-clen 0; // free(pque); while (!is_empty_link_queue(pque)) { pop_link_queue(pque, NULL); } free(pque); }2.链式队列3.循环队列由于上述顺序队列存在“假溢出”的问题这里引出循环队列的概念。将顺序队列臆造为一个环状的空间即把存储队列元素的表从逻辑上视为一个环称为循环队列。当队首指针Q.frontMaxSize-1后再前进一个位置就自动到0这可以利用除法取模运算(%)来实现。为了区分是队空还是队满的情况有三种处理方式:1)牺牲一个单元来区分队空和队满入队时少用一个队列单元这是一种较为普遍的做法约定以“队首指针在队尾指针的下一位置作为队满的标志”如图3.7(d2)所示。队满条件:(Q.rear1)%MaxSizeQ.front。队空条件:Q.frontQ.rear。队列中元素的个数:(Q.rear-Q.frontMaxSize)%MaxSize。2)类型中增设size数据成员表示元素个数。若删除成功则size减1若插入成功则 size 加 1,队空时 Q.size0;队满时 Q.sizeMaxSize两种情况都有Q.frontQ.rear.3)类型中增设tag数据成员以区分是队满还是队空。删除成功置tag0若导致Q.frontQ.rear,则为队空;插入成功置tag1,若导致Q.frontQ.rear则为队满。循环链表定义typedef struct seq_que { Data_t* base; int head; int tail; }SQue_t;基本功能SQue_t* create_seq_queue() { SQue_t* psq malloc(sizeof(SQue_t)); if (NULL psq) { printf(malloc error\n); return NULL; } psq-base malloc(sizeof(Data_t)*SEQ_MAX_LEN); if (NULL psq) { printf(malloc error\n); return NULL; } psq-head 0; psq-tail 0; return psq; } int push_seq_queue(SQue_t *psq,Data_t data) { if(is_full_seq_queue(psq)) { return -1; } psq-base[psq-tail] data; psq-tail (psq-tail1)%SEQ_MAX_LEN; return 0; } int is_full_seq_queue(SQue_t* psq) { return (psq-tail1)%SEQ_MAX_LEN psq-head; } int is_empty_seq_queue(SQue_t *psq) { return psq-tail psq-head; } void show_seq_queue(SQue_t*psq) { if(is_empty_seq_queue(psq)) { return ; } int tmp psq-head; while(tmppsq-tail) { printf(%d ,psq-base[tmp]); tmp; } printf(\n); } int pop_seq_queue(SQue_t *psq,Data_t *pdata) { if(is_empty_seq_queue(psq)) { return -1; } if(pdata NULL) { return -1; } *pdata psq-base[psq-head]; psq-head (psq-head1)%SEQ_MAX_LEN; return 0; } void destory(SQue_t *psq) { free(psq-base); psq-base NULL; free(psq); }4.队列的应用1.队列在层次遍历中的应用2.队列在计算机系统中的应用二.栈1.链式栈栈结构:只允许从一端进行插入和删除数据的线性存储结构成为栈结构。数据插入和删除的这端成为栈顶另一端成为栈底;数据的插入称为入栈/压栈数据的删除称为出栈/弹栈。顺序栈:满增栈、空增栈、满减栈、空减栈满栈、空栈:根据所在位置是否存有元素确定栈顶所在位置一直存有元素称为满栈。栈顶所在位置一直没有元素称为空栈。增栈、减栈:根据栈的生长方向确定。入栈数据时栈顶向内存高地址移动称为增栈入栈数据时栈顶向内存低地址移动称为减栈。链式栈的结构定义typedef int Data_t; typedef struct node { Data_t data; struct node *pnext; }Node_t; typedef struct stack { Node_t *ptop; int clen; }Stack_t;基本功能实现#includestdio.h #includestack.h #includestdlib.h Stack_t *create_stack() { Stack_t *pstack malloc(sizeof(Stack_t)); if(NULL pstack) { printf(malloc error\n); return NULL; } pstack-clen 0; pstack-ptop NULL; return pstack; } int push_stack(Stack_t *pstack, Data_t data) { Node_t *pnode malloc(sizeof(Node_t)); if(NULL pnode) { printf(malloc error\n); return -1; } pnode-data data; pnode-pnext pstack-ptop; pstack-ptop pnode; pstack-clen; return 0; } int pop_stack(Stack_t *pstack, Data_t *pdata) { if(is_empty_stack(pstack)) { return -1; } Node_t *pfree pstack-ptop; if(pdata) *pdata pfree-data; pstack-ptop pfree-pnext; free(pfree); pstack-clen--; return 0; } int is_empty_stack(Stack_t *pstack) { return pstack-clen 0; } void clear_stack(Stack_t *pstack) { while(!is_empty_stack(pstack)) { pop_stack(pstack,NULL); } } void show_stack(Stack_t *pstack) { Node_t *ptmp pstack-ptop; while(ptmp) { printf(%d ,ptmp-data); ptmp ptmp-pnext; } printf(\n); } int get_stack_top(Stack_t *pstack,Data_t *pdata) { if(is_empty_stack(pstack)) { return -1; } *pdata pstack-ptop-data; return 0; } void destroy_stack(Stack_t *pstack) { clear_stack(pstack); free(pstack); }2.栈的应用解决回溯问题撤销功能、网页撤销功能缓存判断回文字符串判断成对出现的符号有没有丢失栈在括号匹配中的应用栈在递归中的应用