This is the 29th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021.”

Implement stacks with queues

The title

image-20211101211340400


The stack structure

typedef struct {
    Queue q1;
    Queue q2;// Two queues
} MyStack;
Copy the code

Stack initialization

MyStack* myStackCreate(a) {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}
Copy the code

Into the “stack”


void myStackPush(MyStack* obj, int x) {
    if(! QueueErase(&obj->q1)) { QueuePush(&obj->q1,x); }else// Push to Q2 when both are empty{ QueuePush(&obj->q2,x); }}Copy the code

Unstack and fetch the top element of the stack


int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;// Assume q2 is empty and Q1 is not empty
    // We can't just swap places
    if(! QueueErase(emptyQ)) { nonemptyQ = &obj->q1; emptyQ = &obj->q2; }// The non-air team leader moves the data into the air team for more than a moment
    while(QueueSize(nonemptyQ)>1)
    {
        // Push the non-empty pairs to the empty pairs
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        // Then pop off the non-empty pairs
        QueuePop(nonemptyQ);
    }
    // We want to return the data at the top of the stack
    int tmp = QueueFront(nonemptyQ);
    // There is only one data left in the queue
    QueuePop(nonemptyQ);
    return tmp;
}
Copy the code

Take the top element of the stack

int myStackTop(MyStack* obj) {
    // Whoever is not empty goes to the end of the queue data
    if(! QueueErase(&obj->q1)) {return QueueBack(&obj->q1);
    }
    else
    {
        returnQueueBack(&obj->q2); }}Copy the code

Determine the stack is empty

bool myStackEmpty(MyStack* obj) {
    return QueueErase(&obj->q1)&&QueueErase(&obj->q2);
}
Copy the code

Stack is destroyed

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
Copy the code
image-20211102002834360


Stack code (interface code to my above article)The algorithm opens a small code non queue


typedef struct {
    Queue q1;
    Queue q2;// Two queues
} MyStack;


MyStack* myStackCreate(a) {
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}

void myStackPush(MyStack* obj, int x) {
    if(! QueueErase(&obj->q1)) { QueuePush(&obj->q1,x); }else// Push to Q2 when both are empty{ QueuePush(&obj->q2,x); }}int myStackPop(MyStack* obj) {
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;// Assume q2 is empty and Q1 is not empty
    // We can't just swap places
    if(! QueueErase(emptyQ)) { nonemptyQ = &obj->q1; emptyQ = &obj->q2; }// The non-air team leader moves the data into the air team for more than a moment
    while(QueueSize(nonemptyQ)>1)
    {
        // Push the non-empty pairs to the empty pairs
        QueuePush(emptyQ,QueueFront(nonemptyQ));
        // Then pop off the non-empty pairs
        QueuePop(nonemptyQ);
    }
    // We want to return the data at the top of the stack
    int tmp = QueueFront(nonemptyQ);
    // There is only one data left in the queue
    QueuePop(nonemptyQ);
    return tmp;
}

int myStackTop(MyStack* obj) {
    // Whoever is not empty goes to the end of the queue data
    if(! QueueErase(&obj->q1)) {return QueueBack(&obj->q1);
    }
    else
    {
        returnQueueBack(&obj->q2); }}bool myStackEmpty(MyStack* obj) {
    return QueueErase(&obj->q1)&&QueueErase(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
Copy the code