图片.png图片.png

    1. /*
    2. *栈先加后减 S->[++top],S->[top--]
    3. */

    图片.png
    简单理解就是:先出栈的在最右侧图片.png
    符号最高时出栈

    1. /*
    2. *队列:FIFO,先进先出,头删尾进(正常的队列规则)
    3. *一般队列->引出front,rear:n>m(m是入队列的元素个数),n是队列的容量,插入操作0(1)[末尾插入]
    4. *删除某个元素,按线性表的逻辑(前驱后继关系),大量的数据移动(n/2)(O(n)),引入队头,队尾指针,不用移动
    5. *接着有“假溢出的问题”(公交车有座问题),满空条件碰撞,引入循环队列
    6. *设置flag|| 牺牲掉一个队列元素来实现,rear指向最后一个元素下标+1,front指向头元素的下标
    7. *判满(rear+1)%QSIZE #正常的话就+1,但是会假溢出,所以就对QSIZE取模,有点空间复用
    8. *所以就rear=(rear+1+QSIZE)%QSIZE //空间复用的实现,解决假溢出
    9. *判满 ,(rear+1)%QSIZE==front,解决条件碰撞的问题
    10. *循环队列->判空,判满
    11. *假溢出指的是下标溢出,真溢出指的是空间溢出(QSIZE<要插入的元素个数),数据的覆盖
    12. *队列长度=|rear-front|=(rear-front+QSIZE)%QSIZE
    13. *链队->空间问题不需要考虑
    14. */
    15. //循环队列的顺序存储结构:队列的基本操作
    16. #include"stdio.h"
    17. #define MAXSIZE 10
    18. typedef int Elemtype;
    19. typedef struct
    20. {
    21. Elemtype r[MAXSIZE];
    22. int front;//队头指针
    23. int rear;//指空(尾元素的下一个),front,rear递增式移动
    24. }SqQueue;
    25. void InitSqQueue(SqQueue *Q);//初始化空队列
    26. void GetLength(SqQueue *Q,int length);//获取长度
    27. void InsertElem(SqQueue *Q,int e);//涉及rear的变化Q->rear=(Q->rear+1+QSIZE)%QSIZE;
    28. void DeleteElem(SqQueue *Q,int *e);//Q->front=(Q->front+1+QSIZE)%QSIZE;

    图片.png

    1. //队列的链式存储结构,尾进头出,链队列,链队的特征是front指向头结点,rear指向尾节点
    2. //空时均指向头结点
    3. typedef int Elemtype;
    4. typedef struct QNode
    5. {
    6. Elemtype data;
    7. struct QNode * next;//链队元素的介绍
    8. }QNode ,*QnodePtr;
    9. typedef struct
    10. {
    11. QnodePtr front,rear;//链队的属性
    12. }QLinkList;

    图片.png

    1. //队列的链式存储结构,尾进头出,链队列,链队的特征是front指向头结点,rear指向尾节点
    2. //空时均指向头结点
    3. #include"stdio.h"
    4. #include"malloc.h"
    5. #define MAXSIZE 10
    6. typedef int Elemtype;
    7. typedef struct QNode
    8. {
    9. Elemtype data;
    10. struct QNode * next;//链队元素的介绍
    11. }QNode ,*QnodePtr;
    12. typedef struct
    13. {
    14. QnodePtr front,rear;//链队的属性
    15. }QLinkList;
    16. int main();
    17. void QueuePrint(QLinkList *Q);
    18. void QueueInit(QLinkList *Q,Elemtype *a);
    19. void InQueue(QLinkList *Q,Elemtype e);//队尾入队
    20. int main()
    21. {
    22. QLinkList Q;
    23. Elemtype a[MAXSIZE]={1,2,3,4,5,6,7,8,9,0};
    24. QueueInit(&Q,a);
    25. QueuePrint(&Q);
    26. printf("\n");
    27. InQueue(&Q,3);
    28. QueuePrint(&Q);
    29. }
    30. void QueueInit(QLinkList *Q,Elemtype *a)
    31. {
    32. //设置头结点,这里没有传递二级指针的原因是修改的是Q的front,一级指针即可
    33. Q->front=(QNode*)malloc(sizeof(QNode));
    34. Q->front->next=NULL;
    35. Q->rear=Q->front;
    36. //各节点初始化
    37. QnodePtr p;
    38. int i;
    39. p=Q->front;
    40. for(i=1;i<=MAXSIZE;i++)
    41. {
    42. p->next=(QNode*)malloc(sizeof(QNode));
    43. p=p->next;
    44. p->data=a[i-1];
    45. Q->rear=p;
    46. }
    47. //printf("%d ",p->data);
    48. //QueuePrint(Q);
    49. p->next=NULL;
    50. //QueuePrint(Q);
    51. }
    52. void InQueue(QLinkList *Q,Elemtype e)//队尾插入元素
    53. {
    54. Q->rear->next=(QNode *)malloc(sizeof(QNode));//添加尾节点
    55. Q->rear=Q->rear->next;//尾指针更新
    56. Q->rear->data=e;//尾数据更新
    57. Q->rear->next=NULL;//尾节点的指针域更新
    58. //这里易需要自己验证
    59. }
    60. void QueuePrint(QLinkList *Q)
    61. {
    62. int j;
    63. QNode *p;
    64. //已起始和终结节点为分割距离
    65. p=Q->front->next;
    66. while(p)
    67. {
    68. printf("%d " ,p->data);
    69. p=p->next;
    70. }
    71. }

    图片.png
    图片.png