C数据结构：栈和队列应用场景

计算器实例

main.c

#include <stdlib.h>
#include <stdio.h>
#include "sqstack.h"

void compute(sqstack* snum,datatype* data)
{
    datatype n1,n2,n;
    st_pop(snum,&n2);
    st_pop(snum,&n1);
    switch(*data)
    {
        case '+':
            n = n1 +n2;
            break;
        case '-':
            n = n1 - n2;
            break;
        case '*':
            n = n1 * n2;
            break;
        case '/':
            n = n1 / n2;
            break;
        default:
            exit(1);
            break;
    }
    st_push(snum,&n);


}
int get_pri(int op)
{
    switch(op)
    {
        case '(':
            return 0;
        case '+':
            return 1;
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;

    }
}
void deal_bracket(sqstack*snum ,sqstack* sop)
{
    datatype old_op;
    st_top(sop,&old_op);
    while(old_op != '(')
    {
        st_pop(sop,&old_op);
        compute(snum,&old_op);
        st_top(sop,&old_op);
    }
    st_pop(sop,&old_op); //弹出左括号

}
void deal_op(sqstack*snum,sqstack*sop,int op)
{
    datatype old_op;

    if( (st_isempty(sop)==0) ||op =='('  )  
    {
        st_push(sop,&op);
        return ;
    }
    
    st_top(sop,&old_op);
    if(get_pri(op) > get_pri(old_op))
    {
        st_push(sop,&op);
        return;
    }
    while( get_pri(op) <= get_pri(old_op) )
    {
        st_pop(sop,&old_op);
        compute(snum,&old_op);
        if(st_isempty(sop)== 0)
            break;
        st_top(sop,&old_op);
    }
    st_push(sop,&op);
    
}
int main()
{
    datatype old_op;
    int i=0;
    int value =0;
    int flag = 0;
    char str[] = "(11+3)*2-5"; //23
    sqstack*snum,*sop;
    snum = st_create();
    sop = st_create();


    while(str[i] != '\0')
    {
        // printf("%c  \n",str[i]);
        // num
        if(str[i]> '0' && str[i]< '9' )
        {
            value = value*10 + (str[i]- '0') ;  //求差值,原来内容移位
            flag = 1;
        }
        else // op
        {
            if(flag == 1) //证明取过了数值
            {
                st_push(snum,&value);
                value = 0;
                flag = 0;
            }
            if(str[i]==')')
            {
                deal_bracket(snum,sop);
            }
            else // 可能是  ( + - * / 
            {
                deal_op(snum,sop,str[i]);
            }
        }

        i++;
    }
    
    if(flag) //最后一个元素
    {
        st_push(snum,&value);
    }
    st_travel(snum);
    printf("--------\n"); 
    while(!(st_isempty(sop)==0) )
    {
        st_pop(sop,&old_op);
        compute(snum,&old_op);
        if(st_isempty(sop)==0)
            break;
        st_top(sop,&old_op);
    }
    st_travel(snum);

    st_destroy(snum);
    st_destroy(sop);

    return 0;
}

sqstack.h

#ifndef SQSTACK_H
#define SQSTACK_H

#define MAXSIZE 32

typedef int datatype;

typedef struct node_st
{
    datatype data[MAXSIZE];
    int top;
}sqstack;


sqstack* st_create(void);

int st_isempty(sqstack*);

int st_push(sqstack*,datatype*);

int st_pop(sqstack*,datatype*);

int st_top(sqstack*,datatype*);

void st_travel(sqstack*);

int st_destroy(sqstack*);

#endif

sqstack.c

#include <stdlib.h>
#include <stdio.h>
#include "sqstack.h"

sqstack* st_create(void)
{
    sqstack*st;
    st = malloc(sizeof(*st));
    if(st == NULL)
        return NULL;
        
    st->top = -1;
    return st;
}
int st_isempty(sqstack*st)
{
    if(st->top == -1)
        return 0;
    return 1;
//    return (st->top == -1);
}
int st_push(sqstack*st,datatype* data)
{
    if(st->top == MAXSIZE-1 )
        return -1;
    st->data[++st->top] = *data;
    return 0;
}
int st_pop(sqstack*st,datatype*data)
{
    if(st_isempty(st)==0)
        return -1;
    *data = st->data[st->top--];
    return 0;
}
int st_top(sqstack*st,datatype*data)
{
    if(st_isempty(st )== 0)
        return -1;
    *data = st->data[st->top];
    return 0;
}
void st_travel(sqstack*st)
{
    if(st_isempty(st)== 0)
        return;
    for(int i=0;i<=st->top;i++)
    {
        printf("%d ",st->data[i]);
    }
    printf("\n");
}

int st_destroy(sqstack*st)
{
    free(st);
    st = NULL;
    return 0;
}

球钟算法

代码中包含的sqstack.h/sqstack.c和 queue.h/queue.c参考之前文章：C数据结构栈，C数据结构队列，采用的是顺序存储栈，顺序存储队列，如有疑问，可以给博主留言。

main.c

#include <stdlib.h>
#include <stdio.h>
#include "sqstack.h"
#include "queue.h"

#define BALL_SIZE 27
static int check(queue*qu)
{
    int i = (qu->head+1)%MAXSIZE;

    while(i != qu->tail )
    {
        if(qu->data[i] > qu->data[(i+1)%MAXSIZE ])
            return 0;
        i = (i+1)%MAXSIZE;
    }
    return 1;
}

int main()
{
    int t,time = 0;
    queue* qu;
    int value = 0;
    sqstack*st_min,*st_fivemin,*st_hour;
    qu = qu_create();
    
    st_min = st_create();
    st_fivemin = st_create();
    st_hour = st_create();

    for(int i=1;i<=BALL_SIZE;i++)
    {
        qu_enqueue(qu,&i);
    }
    qu_travel(qu);
    while(1)
    {
        qu_dequeue(qu,&t);
        time++;

        if(st_min->top != 3)
        {
            st_push(st_min,&t);
        }
        else
        {
            while(st_isempty(st_min)!=0)
            {
                st_pop(st_min,&value);
                qu_enqueue(qu,&value);
            }
            if(st_fivemin->top !=10)
            {
                st_push(st_fivemin,&t);
            }
            else
            {
                while(st_isempty(st_fivemin)!=0 )
                {
                    st_pop(st_fivemin,&value);
                    qu_enqueue(qu,&value);
                }
                if(st_hour->top != 10)
                {
                    st_push(st_hour,&t);
                }
                else
                {
                    while(st_isempty(st_hour) !=0 )
                    {
                        st_pop(st_hour,&value);
                        qu_enqueue(qu,&value);
                    }
                    qu_enqueue(qu,&t);
                    if(check(qu))
                        break;
                }


            }
        }
    }

    printf("time = %d \n",time);
    qu_destroy(qu);
    st_destroy(st_min);
    st_destroy(st_fivemin);
    st_destroy(st_hour);

    return 0;
}