[数据结构]用栈实现队列

思路分析

代码实现：

typedef int STDataType;
typedef struct Stack
{
       int* a;
       int top;//下标
       int capacity;
}ST;
//栈的初始化
void STInit(ST* ps);
//栈的插入
void STPush(ST* ps, STDataType x);
//栈的删除
void STPop(ST* ps);
//
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);
//栈的销毁
void STDestroy(ST* ps);
//访问栈顶元素
STDataType STTop(ST* ps);
//栈的初始化
void STInit(ST* ps)
{
       assert(ps);
       ps->a = malloc(sizeof(STDataType) * 4);
       if (ps->a == NULL)
       {
              perror("malloc fail");
              return;
       }
       ps->capacity = 4;
       ps->top = 0;//代表top表示的是栈顶元素的下一个位置：刚开始top指向的是第一个元素，表示0，当第一个元素插入后top++表示1
}
//栈的插入
void STPush(ST* ps, STDataType x)
{
       assert(ps);
       if (ps->top == ps->capacity)
       {
              STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) *  ps->capacity * 2);//扩容到当前的二倍
              if (tmp == NULL)
              {
                      perror("realloc fail");
                      return;
              }
                      ps->a = tmp;
                      ps->capacity *= 2;
       }
       ps->a[ps->top] = x;
       ps->top++;
}
//栈的删除
void STPop(ST* ps)
{
       assert(ps);
       assert(!STEmpty(ps));
       ps->top--;
       /*在栈操作函数中，栈指针 ps 是操作栈的基础，如果 ps 为 NULL，
              那么后续对 ps 指向的栈结构的任何访问（如 ps->top）都会导致未定义行为，
              通常是程序崩溃。因此，在进行栈操作之前，需要先确保 ps 不是 NULL
              assert(!STEmpty(ps)); 实际上是在检查栈不为空的情况下才继续执行后续操作*/
}
//
int STSize(ST* ps)
{
       assert(ps);
       return ps->top;
}
//判断栈是否为空
bool STEmpty(ST* ps)
{
       assert(ps);
       return ps->top == 0;
}
//栈的销毁
void STDestroy(ST* ps)
{
       assert(ps);
       free(ps->a);
       ps->a = NULL;
       ps->top = 0;
       ps->capacity = 0;
}
//访问栈顶元素
STDataType STTop(ST* ps)
{
       assert(ps);
       assert(!STEmpty(ps));
       return ps->a[ps->top-1];
}


typedef struct {
    ST pushst;
    ST popst;


} MyQueue;




MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}


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


int myQueuePop(MyQueue* obj) {
    //导数据
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));//将栈顶元素导入
            STPop(&obj->pushst);//删除栈顶元素
        }
    }


    int front=STTop(&obj->popst);
    STPop(&obj->popst);
    return front;
}


int myQueuePeek(MyQueue* obj) {
    //导数据
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))
        {
            STPush(&obj->popst,STTop(&obj->pushst));//将栈顶元素导入
            STPop(&obj->pushst);//删除栈顶元素
        }
    }
    int front=STTop(&obj->popst);
    return front;
}


bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}


void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(obj);
}