文档建议反馈控制台
首页
学习
活动
专区
圈层
工具
MCP广场
文章/答案/技术大牛
发布
社区首页 >专栏 >C语言编程实战：每日一题：用栈实现队列

C语言编程实战：每日一题：用栈实现队列

作者头像
say-fall
发布于 2026-01-15 15:10:51
发布于 2026-01-15 15:10:51
20
举报
欢迎来到say-fall的文章
在这里插入图片描述
在这里插入图片描述

🌈 say-fall：个人主页 🚀 专栏：《手把手教你学会C++》 | 《C语言从零开始到精通》 | 《数据结构与算法》 | 《小游戏与项目》 💪 格言：做好你自己，才能吸引更多人，与他们共赢，这才是最好的成长方式。

题目：用栈实现队列

1. 思路解析（初）：

最初我采用了一种相对复杂的实现方式。核心思路是：利用栈结构实现队列功能时，将新元素存入主栈后，通过转移操作保持元素顺序。

具体操作流程：

  1. 首次存入元素：
首次操作示意图
首次操作示意图

将元素从主栈转移到辅助栈：

转移过程示意图
转移过程示意图

使用时直接从辅助栈取出，确保主栈始终保持为空

  1. 后续存入元素： 先将新元素存入主栈：
存入新元素示意图
存入新元素示意图

再将所有元素转移到辅助栈：

二次转移示意图
二次转移示意图

这样每次执行删除或获取操作时，直接从辅助栈处理即可

2. 代码(初)：

初始写法

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int STDatatype;
typedef struct Stack
{
    STDatatype* ptr;
    int top;
    int capacity;
}Stack;

//初始化与销毁
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);

//入栈与出栈
void StackPush(Stack* ps, STDatatype x);
void StackPop(Stack* ps);

//查看顶端元素
STDatatype StackTop(Stack* ps);

//判空
bool StackEmpty(Stack* ps);

//有效元素个数
int StackSize(Stack* ps);

//初始化与销毁
void StackInit(Stack* ps)
{
    assert(ps);

    ps->ptr = NULL;
    ps->capacity = 0;
    //指向栈顶的下一个位置
    ps->top = 0;
}
void StackDestroy(Stack* ps)
{
    assert(ps);

    free(ps->ptr);
    ps->ptr = NULL;
    ps->capacity = ps->top = 0;
}

//入栈与出栈
void StackPush(Stack* ps, STDatatype x)
{
    assert(ps);

    if (ps->top == ps->capacity)
    {
        int newcapacity = ps->capacity == 0 ? 4 : (2 * ps->capacity);
        STDatatype* tmp = (STDatatype*)realloc(ps->ptr, newcapacity * sizeof(STDatatype));
        if (tmp == NULL)
        {
            perror("realloc");
            return;
        }
        ps->ptr = tmp;
        ps->capacity = newcapacity;
    }
    ps->ptr[ps->top] = x;
    ps->top++;
}
void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);

    ps->top--;
}


//查看顶端元素
STDatatype StackTop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);

    return ps->ptr[ps->top - 1];
}

//判空
bool StackEmpty(Stack* ps)
{
    assert(ps);

    return ps->top == 0;
}

//有效元素个数
int StackSize(Stack* ps)
{
    assert(ps);

    return ps->top;
}



typedef struct {
    Stack st1;
    Stack st2;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));

    StackInit(&(obj->st1));
    StackInit(&(obj->st2));
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
     //如果都没有元素，随便插入
     if(StackEmpty(&obj->st1) && StackEmpty(&obj->st2))
     {
         StackPush(&obj->st1,x);
     }
    //如果有元素，先把元素挪到另一个栈中；
    else
    {
        Stack* empty = &obj->st1;
    	Stack* nonempty = &obj->st2;
    	if (!StackEmpty(empty))
    	{
        	empty = &obj->st2;
        	nonempty = &obj->st1;
    	}

    while (!StackEmpty(nonempty))
    {
        StackPush(empty, StackTop(nonempty));
        StackPop(nonempty);
    }
    StackPush(empty, x);
    while (!StackEmpty(empty))
    {
        StackPush(nonempty, StackTop(empty));
        StackPop(empty);
    }
    }
}

int myQueuePop(MyQueue* obj) {
    Stack* empty = &obj->st1;
    Stack* nonempty = &obj->st2;
    if (!StackEmpty(empty))
    {
        empty = &obj->st2;
        nonempty = &obj->st1;
    }
    int top = StackTop(nonempty);
    StackPop(nonempty);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    Stack* empty = &obj->st1;
    Stack* nonempty = &obj->st2;
    if (!StackEmpty(empty))
    {
        empty = &obj->st2;
        nonempty = &obj->st1;
    }
    return StackTop(nonempty);
}

bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->st1) && StackEmpty(&obj->st2);
}

void myQueueFree(MyQueue* obj) {
	StackDestroy(&obj->st1); 
	StackDestroy(&obj->st2);
    free(obj);
    obj = NULL;
}

3. 思路解析（优化）

通过设计输入栈和输出栈的双栈结构实现队列功能：

  • 所有入队操作直接压入输入栈
  • 出队操作从输出栈弹出元素
  • 当输出栈为空时，将输入栈所有元素依次弹出并压入输出栈

这种方法使入队和出队操作的时间复杂度均为O(1)，相比原来的实现更高效。

双栈实现队列示意图
双栈实现队列示意图

4. 代码（优化）

代码语言：javascript
复制
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef int STDatatype;
typedef struct Stack {
    STDatatype* ptr;
    int top;
    int capacity;
} Stack;

// 栈基本操作
void StackInit(Stack* ps);
void StackDestroy(Stack* ps);
void StackPush(Stack* ps, STDatatype x);
void StackPop(Stack* ps);
STDatatype StackTop(Stack* ps);
bool StackEmpty(Stack* ps);
int StackSize(Stack* ps);

void StackInit(Stack* ps) {
    assert(ps);
    ps->ptr = NULL;
    ps->capacity = 0;
    ps->top = 0;  // 指向栈顶的下一个位置
}

void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->ptr);
    ps->ptr = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps, STDatatype x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : (2 * ps->capacity);
        STDatatype* tmp = (STDatatype*)realloc(ps->ptr, newcapacity * sizeof(STDatatype));
        if (tmp == NULL) {
            perror("realloc");
            return;
        }
        ps->ptr = tmp;
        ps->capacity = newcapacity;
    }
    ps->ptr[ps->top++] = x;
}

void StackPop(Stack* ps) {
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

STDatatype StackTop(Stack* ps) {
    assert(ps);
    assert(ps->top > 0);
    return ps->ptr[ps->top - 1];
}

bool StackEmpty(Stack* ps) {
    assert(ps);
    return ps->top == 0;
}

int StackSize(Stack* ps) {
    assert(ps);
    return ps->top;
}

// 队列实现
typedef struct {
    Stack InStack;  // 输入栈
    Stack OutStack; // 输出栈
} MyQueue;

// 当输出栈为空时，将输入栈元素转移到输出栈
void transferElements(MyQueue* obj) {
    assert(obj);
    if (StackEmpty(&obj->OutStack)) {
        while (!StackEmpty(&obj->InStack)) {
            StackPush(&obj->OutStack, StackTop(&obj->InStack));
            StackPop(&obj->InStack);
        }
    }
}

MyQueue* myQueueCreate() {
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&(obj->InStack));
    StackInit(&(obj->OutStack));
    return obj;
}

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

int myQueuePop(MyQueue* obj) {
    assert(obj);
    transferElements(obj);
    int top = StackTop(&obj->OutStack);
    StackPop(&obj->OutStack);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    transferElements(obj);
    return StackTop(&obj->OutStack);
}

bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&obj->InStack) && StackEmpty(&obj->OutStack);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->InStack);
    StackDestroy(&obj->OutStack);
    free(obj);
    obj = NULL;
}
  • 本节完…
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2026-01-13，如有侵权请联系 cloudcommunity@tencent.com 删除
编程
队列
assert
ps
stack

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

编程
队列
assert
ps
stack
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
目录
  • 题目：用栈实现队列
    • 1. 思路解析（初）：
    • 2. 代码(初)：
    • 3. 思路解析（优化）
    • 4. 代码（优化）
领券

腾讯云开发者

扫码关注腾讯云开发者

扫码关注腾讯云开发者

领取腾讯云代金券

热门产品

热门推荐

更多推荐

Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 粤公网安备44030502008569号

腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号

问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

Copyright © 2013 - 2026 Tencent Cloud.

All Rights Reserved. 腾讯云 版权所有

登录 后参与评论