• 队列的运行算法

    1.链队：

    插入 删除 打印 取队顶
    1. #include 
    2. #include 
    3.  
    4. typedef struct Qnode{
    5.     int data;
    6.     struct Qnode *next;
    7. }Qnode,*QuenePtr;
    8.  
    9. typedef struct {
    10.     QuenePtr front;
    11.     QuenePtr rear;
    12. }LinkQueue;
    13. //初始化
    14. void InitQueue(LinkQueue *q){
    15.     (*q).front=(QuenePtr)malloc(sizeof (Qnode));
    16.     if(!(*q).front) exit(0);
    17.     (*q).front->next=NULL;
    18.     (*q).rear=(*q).front;
    19. }
    20. //销毁
    21. void DestroyQueue(LinkQueue *q){
    22.     while((*q).front){
    23.         (*q).rear=(*q).front->next;
    24.         free((*q).front);
    25.         (*q).front=(*q).rear;
    26.     }
    27. }
    28. //判空
    29. int IsEmpty(LinkQueue q){
    30.     if(q.rear==q.front) return 1;
    31.     else return 0;
    32. }
    33. //入队
    34. void EnQueue(LinkQueue *q,int e){
    35.     QuenePtr p=(QuenePtr)malloc(sizeof(Qnode));
    36.     if(!p)exit(0);
    37.     p->data=e;
    38.     p->next=NULL;
    39.     (*q).rear->next=p;
    40.     (*q).rear=p;
    41.     
    42. }
    43. //出队
    44. void DeQueue(LinkQueue *q,int *e){
    45.     if((*q).rear==((*q).front)) printf("Empty !");
    46.     QuenePtr p=(*q).front->next;
    47.     *e=p->data;
    48.     (*q).front->next=p->next;
    49.     if((*q).rear ==p) (*q).rear=(*q).front;
    50.     free(p);
    51. }
    52. //打印
    53. void Show(LinkQueue *q){
    54.     for(Qnode *p=q->front->next ;p!=NULL;p=p->next){
    55.         printf("%d ",p->data);
    56.     }
    57.     printf("\n");
    58. }
    59.  
    60. int main(){
    61.     LinkQueue q;
    62.     InitQueue(&q);
    63.     
    64.     for(int i=0;i<5;i++){
    65.         int e; scanf("%d",&e);
    66.         EnQueue(&q,e);
    67.     }
    68.     Show(&q);
    69.     
    70.     if(IsEmpty(q)) printf("empty!");
    71.     else printf("not empty");
    72.     
    73.     int e;DeQueue(&q,&e); printf("出队元素是：%d \n",e);
    74.     Show(&q);
    75.      
    76.     int val;scanf("%d",&val);
    77.     
    78.     
    79.     DestroyQueue(&q);
    80.     return 0;
    81. }

    2.循环队列

    wenti

    1. #include
    2. #include
    3. #define Maxsize 100
    4.  
    5. typedef struct {
    6.     int *base;
    7.     int front ;
    8.     int rear;
    9. }SqQueue;
    10.  
    11. //初始化
    12. void InitQueue (SqQueue *q){
    13.     q->base=(int *)malloc (Maxsize *sizeof (int));
    14.     if(!q->base) exit(0);
    15.     q->front=0;
    16.     q->rear=0;
    17. }
    18. //入队
    19. void EnterQueue(SqQueue *q,int e){
    20.     if((q->rear+1)%Maxsize==q->front) printf("Full!\n");
    21.     q->base[q->rear]=e;
    22.     q->rear=(q->rear +1)%Maxsize;
    23. }
    24. //取队头元素
    25. void getElem(SqQueue q,int *e){
    26.     if(q.front!=q.rear){
    27.         *e=q.base[q.front];
    28.     }
    29.     else {
    30.         printf("Empty! \n");
    31.     }
    32. }
    33. //求队长
    34. int Getlength(SqQueue q){
    35.     int e;
    36.     e=(q.rear-q.front+Maxsize)%Maxsize;
    37.     return e;
    38. }
    39. //出队
    40. void PopQueue(SqQueue *q,int *e){
    41.     if(q->front==q->rear) printf("Empty! \n");
    42.     *e=q->base[q->front];
    43.     q->front=(q->front+1)%Maxsize;
    44. }
    45. //打印
    46. void Print(SqQueue q){
    47.     for (int i=q.front;i!=q.rear;){
    48.         printf("%d ",q.base[i]);
    49.         i=(i+1)%Maxsize;
    50.     }
    51.     printf("\n");
    52. }
    53.  
    54. int main(){
    55.     SqQueue q;
    56.     int e;
    57.     for(int i=0;i<5;i++){
    58.         scanf("%d",&e);
    59.         EnterQueue(&q,e);
    60.     }
    61.     Print(q);
    62.     getElem(q,&e);
    63.     printf("队顶元素是 %d \n",e);
    64.     
    65.     int length=Getlength(q);
    66.     printf("队长是%d \n",length);
    67.      
    68.     PopQueue(&q,&e);
    69.     printf("出队元素是%d \n",e);
    70.     Print(q);
    71.     return 0;
    72. }
    73.  
    1. #include
    2. #include
    3. #include
    4. #define Maxsize 50
    5.  
    6. typedef struct {
    7.     int *base;
    8.     int front;
    9.     int rear;
    10. }SqQueue;
    11.  
    12. void InitQueue(SqQueue *Q){
    13.     (*Q).base=(int )malloc(Maxsize*sizeof(int));
    14.     if(!(*Q).base)exit(0);
    15.     (*Q).front=0;
    16.     (*Q).rear=0;
    17. }
    18.  
    19. void EnterQueue(SqQueue *q,int e){
    20.     if(((*q).base+1) %Maxsize==q->front){
    21.         printf("Full");
    22.     }
    23.     q->base[q->rear]=e;
    24.     q->rear=(q->rear+1)%Maxsize;
    25. }
    26.  
    27. void PopQueue(SqQueue *q,int *e){
    28.     if(q->front==q->rear){
    29.         printf("empty!\n");
    30.     }
    31.     e=q->base[q->front];
    32.     q->front=(q->front+1)%Maxsize;
    33. }
    34.  
    35. int Emp(SqQueue q){
    36.     if(q.front==q.rear) return 0;
    37.     else return 1;
    38. }
    39.  
    40. int main(){
    41.     int n,m;
    42.     scanf("%d %d",&n,&m);
    43.     int a[n];
    44.     SqQueue Q;
    45.     InitQueue(&Q);
    46.     for(int i=0;i
    47.         scanf("%d ",&a[i]);
    48.         EnterQueue(&Q,a[i]);
    49.     }
    50.     int e;
    51.     for(int i=0;i
    52.         PopQueue(&Q,&e);
    53.         printf("%d ",e);
    54.     }
    55.     
    56.     if(Emp(Q)==1) printf("\n1");
    57.     else printf("\n0");
    58.     return 0;
    59. }
    1.  
    2. #include 
    3. #include 
    4.  
    5. #define TOTAL_SPACE 5
    6.  
    7. /**
    8.  * Circle int queue.
    9.  */
    10. typedef struct CircleIntQueue
    11. {
    12.     int data[TOTAL_SPACE];
    13.  
    14.     int head;
    15.  
    16.     int tail;
    17. }*CircleIntQueuePtr;
    18.  
    19. /**
    20.  * Initialize the queue.
    21.  */
    22. CircleIntQueuePtr initQueue()
    23. {
    24.     CircleIntQueuePtr resultPtr = (CircleIntQueuePtr)malloc(sizeof(struct CircleIntQueue));
    25.     resultPtr->head = 0;
    26.     resultPtr->tail = 0;
    27.  
    28.     return resultPtr;
    29. }// Of the first constructor
    30.  
    31. /**
    32.  * Enqueue.
    33.  *
    34.  * @param paraValue The value of the new node.
    35.  */
    36. void enqueue(CircleIntQueuePtr paraPtr, int paraValue)
    37. {
    38.     if ((paraPtr->tail + 1) % TOTAL_SPACE == paraPtr->head) {
    39.         printf("Queue full.\r\n");
    40.         return;
    41.     } // Of if
    42.  
    43.     paraPtr->data[paraPtr->tail % TOTAL_SPACE] = paraValue;
    44.     paraPtr->tail++;
    45. }// Of enqueue
    46.  
    47. /**
    48.  * Dequeue.
    49.  *
    50.  * @return The value at the head.
    51.  */
    52. int dequeue(CircleIntQueuePtr paraPtr)
    53. {
    54.     int resultValue;
    55.     if (paraPtr->head == paraPtr->tail) {
    56.         printf("No element in the queue.\r\n");
    57.         return -1;
    58.     } // Of if
    59.  
    60.     resultValue = paraPtr->data[paraPtr->head % TOTAL_SPACE];
    61.     paraPtr->head++;
    62.  
    63.     return resultValue;
    64. }// Of dequeue
    65.  
    66. /**
    67.  * Output the queue.
    68.  */
    69. void outputLinkQueue(CircleIntQueuePtr paraPtr)
    70. {
    71.     int i;
    72.     if (paraPtr->head == paraPtr->tail)
    73.     {
    74.         printf("Empty queue.");
    75.         return;
    76.     } // Of if
    77.  
    78.     printf("Elements in the queue: ");
    79.     for (i = paraPtr->head; i < paraPtr->tail; i++)
    80.     {
    81.         printf("%d, ", paraPtr->data[i % TOTAL_SPACE]);
    82.     } // Of for i
    83.  
    84.     printf("\r\n");
    85. }//Of outputLinkQueue
    86.  
    87. /**
    88.  * Unit test.
    89.  */
    90. void testLinkQueue()
    91. {
    92.     int i = 10;
    93.     CircleIntQueuePtr tempPtr = initQueue();
    94.     for (; i < 16; i ++)
    95.     {
    96.         enqueue(tempPtr, i);
    97.     }//Of for i
    98.  
    99.     outputLinkQueue(tempPtr);
    100.  
    101.     for (i = 0; i < 6; i ++)
    102.     {
    103.         printf("dequeue gets %d\r\n", dequeue(tempPtr));
    104.     }//Of for i
    105.  
    106.     enqueue(tempPtr, 8);
    107.     outputLinkQueue(tempPtr);
    108. }//Of testLinkQueue
    109.  
    110. /**
    111.  * The entrance.
    112.  */
    113. int main()
    114. {
    115.     testLinkQueue();
    116.     return 1;
    117.     
    118. }

    3.问题 A: 【DS3-6】基于顺序存储的循环队列的基本操作

    [命题人 : admin_ly]
    时间限制 : 1.000 sec  内存限制 : 128 MB
     
    题目描述

    用顺序存储结构实现队列的入队、出队和判断队列是否为空操作。

    输入

    第一行输入两个整数n和m，n表示入队序列A的长度（n个数依次连续入队，中间没有出队的情况），m表示出队序列B的元素数量（m个数依次连续出队，中间没有入队的情况）。第二行为序列A（空格分隔的n个整数），整数之间用空格分隔。

    输出

    第一行输出m个整数，代表出队序列B的各个整数，整数之间用空格分隔。

    第二行输出一个整数表示队列是否为空，队列为空输出0，不为空输出1。

    样例输入 Copy
    1. 5 3
    2. 1 3 5 3 6
    样例输出 Copy
    1. 1 3 5
    2. 1
    1.  
    2.  
    3. #include
    4. #include
    5.  
    6. //数据类型
    7. #define ElemType int
    8. //队列的最大空间
    9. #define MAXSIZE 8
    10. //队列的管理结构
    11. typedef struct Queue
    12. {
    13.     ElemType *base; //指向队列空间的基址
    14.     int       front; //头指针
    15.     int       rear; //尾指针
    16. }Queue;
    17. //队列初始化
    18. void InitQueue(Queue *Q)
    19. {
    20.     //为队列分配存储空间
    21.     Q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);
    22.     if(Q->base == NULL) exit(0);
    23.     //初始时队列为空，头指针和尾指针都指向0位置
    24.     Q->front = 0;
    25.     Q->rear = 0;
    26. }
    27.  
    28. //入队操作
    29. void EnQueue(Queue *Q, ElemType x)
    30. {
    31.     //判断循环队列是否已满
    32.     if(((Q->rear+1)%MAXSIZE) == Q->front)
    33.         printf("Full\n");
    34.     //队列未满，将数据入队
    35.     Q->base[Q->rear] = x;
    36.     //更改尾指针的指向
    37.     Q->rear = (Q->rear+1)%MAXSIZE;
    38. }
    39.  
    40. //打印循环队列中的数据
    41. void ShowQueue(Queue *Q)
    42. {
    43.     //遍历循环队列中的元素，并将数据打印
    44.     for(int i=Q->front; i!=Q->rear;)
    45.     {
    46.         printf("%d ",Q->base[i]);
    47.         //此操作是为了实现循环遍历
    48.         i = (i+1)%MAXSIZE;
    49.     }
    50.     printf("\n");
    51. }
    52.  
    53. //出队操作
    54. int DeQueue(Queue *Q)
    55. {
    56.     //判断循环队列是否为空
    57.     if(Q->front == Q->rear)
    58.         printf("empty\n");
    59.     //如果非空，实现可循环出队
    60.     int e=Q->base[Q->front];
    61.     Q->front = (Q->front+1)%MAXSIZE;
    62.     return e;
    63. }
    64.  
    65. int main()
    66. {
    67.     Queue Q;
    68.     InitQueue(&Q);
    69.     int m,n;
    70.     scanf("%d %d",&n,&m);
    71.     int a[n];
    72.     for(int i=1; i<=n; ++i)
    73.     {
    74.         scanf("%d",&a[i]);
    75.         EnQueue(&Q, a[i]);
    76.     }
    77.     for(int i=0;i
    78.         int e=DeQueue(&Q);
    79.         printf("%d ",e);
    80.     }
    81.     if(Q.front==Q.rear) printf("\n0");
    82.     else printf("\n1");
    83.     return 0;
    84. }
    85.

     

    2.问题 B: 【DS3-7】基于循环链表的队列的基本操作

    [命题人 : admin_ly]
    时间限制 : 1.000 sec  内存限制 : 128 MB
     
    题目描述

    用带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针）。实现该队列的入队、出队和判断队列是否为空操作。

    输入

    第一行输入两个整数n和m，n表示入队序列A的长度（n个数依次连续入队，中间没有出队的情况），m表示出队序列B的元素数量（m个数依次连续出队，中间没有入队的情况）。第二行为序列A（空格分隔的n个整数），整数之间用空格分隔。 

    输出

    第一行输出m个整数，代表出队序列B的各个整数，整数之间用空格分隔。
    第二行输出一个整数表示队列是否为空，队列为空输出0，不为空输出1

    样例输入 Copy
    1. 5 3
    2. 1 3 5 3 6
    样例输出 Copy
    1. 1 3 5
    2. 1
    1. #include
    2. #include
    3.  
    4. /**
    5.  * 链式循环队列结点结构体定义
    6.  */
    7. typedef struct QNode {
    8.     
    9.     int data;
    10.     
    11.     struct QNode *next;
    12.     struct QNode *rear;
    13. } QNode;
    14. void init(QNode **queue) {
    15.     *queue = (QNode *) malloc(sizeof(QNode));
    16.     // 将链式队列头结点的 next 和 rear 指针都指向自身，因为是循环的，并且是空队列
    17.     (*queue)->next = *queue;
    18.     (*queue)->rear = *queue;
    19. }
    20.  
    21.  
    22. void enQueue(QNode **rear, int ele) {
    23.     QNode *newNode = (QNode *) malloc(sizeof(QNode));
    24.     newNode->data = ele;
    25.     newNode->next = NULL;
    26.     newNode->next = (*rear)->next;
    27.     (*rear)->next = newNode;
    28.     (*rear) = newNode;
    29. }
    30.  
    31.  
    32. int deQueue(QNode **rear) {
    33.     if ((*rear)->next == *rear) {
    34.         return 0;
    35.     }
    36.  
    37.     QNode *headNode = (*rear)->next;
    38.      QNode *startNode = headNode->next;
    39.     int ele;
    40.     ele = startNode->data;
    41.      headNode->next = startNode->next;
    42.    
    43.     if (startNode==*rear){
    44.         *rear=(*rear)->next;
    45.     }
    46.     free(startNode);
    47.     return ele;
    48. }
    49.  
    50.  
    51. int Is_empty(QNode **rear){
    52.     if ((*rear)->next == *rear) {
    53.         return 0;
    54.     }
    55.     else return 1;
    56. }
    57.  
    58. int main() {
    59.     QNode *queue;
    60.     init(&queue);
    61.     int n,m;
    62.     scanf("%d %d",&n,&m);
    63.     int a[n];
    64.     for(int i=0;i
    65.         scanf("%d",&a[i]);
    66.         enQueue(&(queue->rear), a[i]);
    67.     }
    68.    
    69.     for(int i=0;i
    70.         int p= deQueue(&(queue->rear));
    71.         printf("%d ",p);
    72.     }
    73.     printf("\n");
    74.     if(Is_empty(&(queue->rear))==1){
    75.         printf("1");
    76.     }
    77.        else printf("0");
    78.     return 0;
    79.  
    80.    
    81.     
    82.    
    83.  
    84. }
    85.

    AHNU-DS

    3。问题 C: 【DS3-08】使用队列判断整数是否为回文数

    [命题人 : 2022069]

    时间限制 : 1.000 sec  内存限制 : 128 MB
     

    题目描述

    给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

    回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

    例如，121 是回文，而 123 不是。

    输入

    一个整数x

    输出

    如果 x 是一个回文整数，返回 true ；否则，返回 false 。

    样例输入 Copy
    121
    样例输出 Copy
    true
    1. #include 
    2. #include 
    3.  
    4. #define MAX_SIZE 100
    5.  
    6. typedef struct {
    7.     int data[MAX_SIZE];
    8.     int front;
    9.     int rear;
    10. } Queue;
    11.  
    12. void initQueue(Queue *q) {
    13.     q->front = 0;
    14.     q->rear = -1;
    15. }
    16.  
    17. bool isQueueEmpty(Queue *q) {
    18.     return q->rear < q->front;
    19. }
    20.  
    21. bool isQueueFull(Queue *q) {
    22.     return q->rear - q->front + 1 == MAX_SIZE;
    23. }
    24.  
    25. void enqueue(Queue *q, int value) {
    26.     if (isQueueFull(q)) {
    27.         printf("Queue is full");
    28.         return;
    29.     }
    30.     q->data[++q->rear] = value;
    31. }
    32.  
    33. int dequeue(Queue *q) {
    34.     if (isQueueEmpty(q)) {
    35.         return -1;
    36.     }
    37.     return q->data[q->front++];
    38. }
    39. int dequeue1(Queue *q) {
    40.     if (isQueueEmpty(q)) {
    41.         return -1;
    42.     }
    43.     return q->data[q->rear--];
    44. }
    45. bool isPalindrome(int x) {
    46.     if (x < 0) {  // 负数不是回文数
    47.         return false;
    48.     }
    49.     Queue q;
    50.     initQueue(&q);
    51.     int temp = x;
    52.     while (temp!= 0) {  // 将整数的每一位入队
    53.     enqueue(&q,temp%10);temp=temp/10;
    54.     }
    55.     while (!isQueueEmpty(&q)) {  // 从队列头和队列尾分别取出数字比较
    56.      if(dequeue(&q)!=dequeue1(&q)||dequeue(&q)&&dequeue1(&q)!=-1)
    57.      return false;
    58.     }    
    59.     return true;
    60. }
    61.  
    62. int main() {
    63.     int num;
    64.     scanf("%d", &num);
    65.     if (isPalindrome(num)) {
    66.         printf("true");
    67.     } else {
    68.         printf("false");
    69.     }
    70.     return 0;
    71. }

  • 相关阅读:
    TCP详解之滑动窗口
    HPC、AI与云计算：当智能时代三叉戟在亚马逊云科技完美融合
    正确选择数据库安全运维平台的几个原则
    京东健康、平安健康To B各有倚仗
    【MyBatis】五、MyBatis的缓存机制与逆向工程
    1.1.C++项目：仿muduo库实现并发服务器之any类的设计
    UltraEdit\UEStudio 的 SSHTelnet 功能教程
    [docker]笔记-网络故障处理
    Windows系统使用MinGW编译二维码库Zbar
    什么是动态规划？
  • 原文地址：https://blog.csdn.net/m0_74161592/article/details/133867952