用栈模拟实现队列(c语言版)

2023-06-27 98

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 用栈模拟实现队列(c语言版)

前言

用"栈实现队列",力扣中一道oj题,可以帮助刚接触"栈"和"队列"的新手更好的理解栈和队列这两种结构.

题目来源于力扣:

题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/

难度:简单

一、队列的各接口:

1.1 类型的声明(MyQueue):

//模拟队列类型的声明
typedef struct {
    ST stackpush;   //用于模拟队列的 入队操作
    ST stackpop;    //用于模拟队列的 出队操作
} MyQueue;

这里是借助两个栈用于模拟队列.

①:stackpush 模拟队列的入队

②:stackpop 模拟队列的出队

1.2 初始化(myQueueCreate):

该队列是由两个栈实现的,所以重点关注两个栈的初始化即可.

步骤:

申请两个栈大小的空间.

申请失败时判断一下.

对队列中的两个栈,一次调用他们的初始化函数.(这个千万别漏掉了,牛牛漏掉之后找了好久的问题)

//队列的初始化
MyQueue* myQueueCreate() {
  //给队列开辟空间
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("obj malloc fail");
    }
    //一定要记得这里要初始化(别漏掉了哦)
    InitST(&obj->stackpush);
    InitST(&obj->stackpop);
    return obj;
}

1.3 入队列(myQueuePush)

对于入队列的模拟实现很简单,只需要将数据压入栈(模拟入队列:stackpush)即可.

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

1.4 出队列(myQueuePop)

函数要求:

将队首元素出队,并且返回刚刚出队的队首元素.

模拟出队相对复杂一些.

初始状态下或者stackpop(模拟出队的栈)数据出队列到空时,里面是没有数据的,所以先判断stackpop是否有数据.

有数据:则直接获取stackpop的栈顶元素作为队首元素.

无数据:将数据从模拟入队列栈全部倒过来.(倒数据)

获取stackpop的栈顶元素作为队首元素,使用top变量记录下来.(因为后面要执行出栈操作).

出栈(模拟出队列),并返回top变量.

int myQueuePop(MyQueue* obj) {
     assert(obj);
     if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列的栈)为空,则向栈(stackpush模拟入队列的栈)要数据
     {
        //下面循环结束的条件是不为空
          while(!STEmpty(&obj->stackpush))//将数据从模拟入队列栈全部倒过来
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
     }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    STPop(&obj->stackpop);
    return top;
}

1.5 队列的判空(myQueueEmpty)

当两个栈中都没有元素时,则队列为空.

//写法1

bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈
    {
        return true;
    }
    else 
    return false;
}

//写法2.

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->stackpush) &&  STEmpty(&obj->stackpop);
}

1.6 返回队首元素(myQueuePeek):

stackpop不为空时,则队首元素就是stackpop的栈顶元素.

stackpop为空时,则队首元素就是stackpush的栈底元素.

所以这里也需要倒数据.

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列)为空,则向栈(stackpush模拟入队列)要数据
     {
        while(!STEmpty(&obj->stackpush))
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出队列)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
    }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    return top;
}

与myQueuePop(出队列)函数比较,此函数只是将队首元素返回,并没有指向pop出队操作.

所以我们在实现myQueuePop函数时可以复用一下myQueuePeek函数.

int myQueuePop(MyQueue* obj) {
    int top=myQueuePeek(obj);
    STPop(&obj->stackpop);
    return top;
}

1.7 队列的销毁(myQueueFree):

释放两个栈初始化开辟的空间

释放队列申请的空间.

void myQueueFree(MyQueue* obj) {
    STDestory(&obj->stackpush);
    STDestory(&obj->stackpop);
    free(obj);
}

二、总代码:

前面的代码是栈的实现,由于c语言不能像c++那样直接调用库.

typedef  int stacktype;
typedef struct stack//定义栈的类型
{
  stacktype* data;
  int top;
  int capacaity;
}ST;
void InitST(ST* ps);//初始化栈
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁
void InitST(ST* ps)//初始化栈
{
  assert(ps);
  ps->top = -1;
  ps->capacaity = 4;
  ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));
}
void STPush(ST* ps, stacktype x)//压栈
{
  assert(ps);
  if (ps->top+1 == ps->capacaity)
  {
    ps->capacaity *= 2;
    ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
    if(tmp == NULL)
    {
      printf("增容失败\n");
    }
    ps->data = tmp;
  }
  ps->top++;
  ps->data[ps->top] = x;
}
void STPop(ST* ps)//出栈
{
  assert(ps);
  assert(!STEmpty(ps));
  ps->top--;
}
bool STEmpty(ST* ps)//判断是否为空栈,是空返回真
{
  assert(ps);
  if (ps->top == -1)
  {
    return true;
  }
  return false;
}
stacktype STTop(ST* ps)//返回栈顶元素
{
  assert(ps);
  return ps->data[ps->top];
}
void STDestory(ST* ps)//销毁栈
{
  assert(ps);
  free(ps->data);
  ps->data = NULL;
  ps->top = -1;
  ps->capacaity = 0;
}
//模拟队列类型的声明
typedef struct {
    ST stackpush;
    ST stackpop;
} MyQueue;
//队列的初始化
MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("obj malloc fail");
    }
    //一定要记得这里要初始化
    InitST(&obj->stackpush);
    InitST(&obj->stackpop);
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    STPush(&obj->stackpush,x);
}
int myQueuePop(MyQueue* obj) {
     assert(obj);
     if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据
     {
          while(!STEmpty(&obj->stackpush))
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
     }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    STPop(&obj->stackpop);
    return top;
}
bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈
    {
        return true;
    }
    else 
    return false;
    //return STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop);
}
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据
     {
        while(!STEmpty(&obj->stackpush))
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
    }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    return top;
    //return STTop(&obj->stackpop);
}
void myQueueFree(MyQueue* obj) {
    STDestory(&obj->stackpush);
    STDestory(&obj->stackpop);
    free(obj);
}

运行结果: