C语言数据结构之栈与队列的相互实现

//栈的结构是由两个队列构成
typedef struct Nystack{
   Quetail q1;
   Quetail q2;
} MyStack;
 
//栈的初始化
MyStack* myStackCreate() {
   MyStack* Newstack = (MyStack*)malloc(sizeof(MyStack));
   Que_Init(&Newstack->q1);
   Que_Init(&Newstack->q2);
   return Newstack;
}

//插入数据
void myStackPush(MyStack* obj, int x) {
     //if((&obj->q1)->head == NULL) //法一：直接判断是否为空
     if(Que_Empty(&obj->q1))        //法二：后续函数的复用
     Que_push(&obj->q2,x);
     else
     Que_push(&obj->q1,x);
}

int myStackPop(MyStack* obj) {
    int temp = 0;
    //假设原队列和空队列
    Quetail* existque = &obj->q1,*nullque = &obj->q2;
    if((&obj->q1)->head == NULL)      //判断与实际是否相符
    {
        existque = nullque;
        nullque = &obj->q1;
    } 
    for(;existque->head->Next;)       //保留最后一个数据
    {
        Que_push(nullque,existque->head->data);  //向空队列导入数据  
        Que_pop(existque);                       //删除原队列数据
    }
    temp = existque->head->data;      
    Que_pop(existque);                //导出最后进的数据
    return temp;
}

int myStackTop(MyStack* obj) {
    if((&obj->q1)->head == NULL)
    {
        return (&obj->q2)->tail->data;
    }
    return (&obj->q1)->tail->data;
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    //法一：直接判断
    //if((&obj->q1)->head == NULL&& (&obj->q2)->head == NULL)
    //法二：复用队列判空函数
    if(Que_Empty(&(obj->q1))&&Que_Empty(&(obj->q2)))
    return true;
    return false;
}

void myStackFree(MyStack* obj) {
     Que_Destory(&obj->q1);
     Que_Destory(&obj->q2);
     free(obj);
}

typedef struct {
    Stack T1;
    Stack T2;
} MyQueue;
 
 
MyQueue* myQueueCreate() {
      MyQueue *Q1;
      Q1 = (MyQueue*)malloc(sizeof(MyQueue));
      Stack_init(&(Q1->T1));      // T1 做入口栈
      Stack_init(&(Q1->T2));      // T2 做出口栈
      return Q1;
}

void myQueuePush(MyQueue* obj, int x) {
     Stack_push(&obj->T1,x);          //这里将栈 T1 作为入口栈
}

int myQueuePop(MyQueue* obj) {
    if(Stack_Empty(&obj->T2))          //判断是否为空
    {
        int k = 0;
        for(;!Stack_Empty(&obj->T1);)  
        {
            k = Stack_Top(&obj->T1);   //记录入口站数据
            Stack_pop(&obj->T1);       //删除入口栈数据
            Stack_push(&obj->T2,k);    //导入出口栈
        }
    }
    int temp = 0;
    temp = Stack_Top(&obj->T2);        
    Stack_pop(&obj->T2);               //从出口栈导出数据
    return temp;                       //题干要求返回导出的值
}

int myQueuePeek(MyQueue* obj) {
    if(Stack_Empty(&obj->T2))         //判断出口栈中是否有数据
    {
        int k = 0;
        for(;!Stack_Empty(&obj->T1);) //向出口栈导入数据
        {
            k = Stack_Top(&obj->T1);
            Stack_pop(&obj->T1);
            Stack_push(&obj->T2,k);
        }
    }
    return Stack_Top(&obj->T2);       //返回出口栈栈顶数据
}

//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
     //判断两个栈是否均为空
     return Stack_Empty(&obj->T1)&&Stack_Empty(&obj->T2);
}
 
//销毁释放队列
void myQueueFree(MyQueue* obj) {
     Stack_pop(&obj->T1);
     Stack_pop(&obj->T2);
     free(obj);
}