[数据结构与算法]C语言用栈实现队列(数据结构)

1.首先需要两个栈来模拟队列的出队和入队

2.假设入队1 2 3 4 ,如果要出队则不能直接出栈.需要进行数据的搬移:

先把s1的数据全部放入s2中,然后再在s2出栈->整个队列出队:

3.如果再要入队则将入队元素放入s1,若要出队则出栈s2元素,若s2为空则继续搬移s1的元素到s2即可.

4.总结:入队:s1? ? 出队:s2

5.代码如下:

typedef int Datatype;
typedef struct stack {
    Datatype* arr;
    int top;
    int capacity;
}stack;
//1.检测栈是否为空，如果为空返回非零结果，如果不为空返回0
int StackEmpty(stack* ps) {
    assert(ps);
    return ps->top == 0;
}
//2.检测栈满扩容
void Cheakstack(stack* ps) {
    if (ps->capacity == ps->top) {
        int newcapacity = (ps->capacity) * 2;
        Datatype* newstack = (Datatype*)malloc(sizeof(stack) * newcapacity);
        for (int i = 0; i < ps->top; i++) {
            newstack[i] = ps->arr[i];
        }
        free(ps->arr);
        ps->arr = newstack;
        ps->capacity = newcapacity;
    }
}
// 3..初始化栈 
void StackInit(stack* ps) {
    assert(ps);
    int N = 5;
    ps->arr = (Datatype*)malloc(sizeof(Datatype) * N);
    ps->capacity = N;
    ps->top = 0;
}
//4.入栈 
void StackPush(stack* ps, Datatype data) {
    assert(ps);
    Cheakstack(ps);
    ps->arr[ps->top] = data;
    ps->top++;
}
//5.出栈
void StackPop(stack* ps) {
    assert(ps);
    if (StackEmpty(ps)) {
        return;
    }
    ps->top--;
}
//6.获取栈顶元素
Datatype* StackTop(stack* ps) {
    assert(ps);
    if (StackEmpty(ps)) {
        return NULL;
    }
    return ps->arr[ps->top - 1];
}
//7. 获取栈中有效元素个数 
int StackSize(stack* ps) {
    assert(ps);
    return ps->top;
}
// 8.销毁栈 
void StackDestroy(stack* ps) {
    assert(ps);
    if (ps->arr) {
        free(ps->arr);
        ps->capacity = 0;
        ps->top =0;
    }
}

typedef struct {
    //俩个栈
    stack s1;
    stack s2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* mq=(MyQueue*)malloc(sizeof(MyQueue));//申请空间
    if(NULL==mq){//检测参数
        return NULL;
    }
    //初始化栈
    StackInit(&mq->s1);
    StackInit(&mq->s2);
    return mq;
}

void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1,x);
}

int myQueuePop(MyQueue* obj) {
    //出队列:把非空 的栈里的元素搬移到空的
    if(StackEmpty(&obj->s2)){
        while(!StackEmpty(&obj->s1)){//所有元素搬移到s2
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }
    int ret=StackTop(&obj->s2);//保存出队元素
    StackPop(&obj->s2);//出队
    return ret;
}

int myQueuePeek(MyQueue* obj) {
     if(StackEmpty(&obj->s2)){
        while(!StackEmpty(&obj->s1)){//所有元素搬移到s2
            StackPush(&obj->s2,StackTop(&obj->s1));
            StackPop(&obj->s1);
        }
    }
    return StackTop(&obj->s2);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);

}

void myQueueFree(MyQueue* obj) {
    if(obj!=NULL){//先销毁栈
        StackDestroy(&obj->s1);
        StackDestroy(&obj->s2);
        free(obj);
    }
}

?

?