AI 助理
备案控制台
开发者社区 云计算 文章 正文

两个队列模拟实现栈

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

一、实现原理

队列：先进先出


栈：后进先出


根据栈和队列各自的特性就知道，用队列模拟实现栈，这里需要两个队列，一个队列是无法实现的，其实现原理和用栈模拟实现队列差不多，但稍微复杂一点点。


假设用q1模拟入栈，q2模拟出栈，且现在q1内已经入栈了一些数据如图：


image.png


根据栈后进先出的特点，此时若要出栈，拿到的应该是a4，所以需要将a1,a2,a3先依次出队再入队到q2中，才能拿到a4。


那么完成依次出栈操作后，栈内的情况应该是如下：


image.png


如果再进行出栈，操作和之前一样，将队列不为空的前n-1一个元素依次出队再入队到另一个空队列中即可。


若要进行入栈操作，则只需要将元素入队到不为空的队列中即可。


但是获取栈顶元素时，我们不需要在进行如上的出队入队操作，只需直接返回不为空的队列的队尾元素即可。


对于栈的判空和判满操作，只需判断栈内部两个队列的空满情况即可，要注意的是，队列一个为满即栈满，队列两个都为空，栈为空。


操作总结：


1.入栈：将元素入队到不为空的队列当中（若初始两个队列都为空，则只需任意入队到一个队列中即可）


2.出栈：将不为空的队列的前n-1一个元素依次出队再入队到另一个空队列中，最后一个元素只出队不入队即可。（前提：栈不为空）


3.获取栈顶：返回不为空的队列的队尾即可。（前提：栈不为空）


4.栈判空：栈内两个队列都为空即栈为空。


5.栈判满：栈内不为空的队列为满，即栈为满。


6.获取栈内有效元素个数：直接返回不为空的队列内元素个数即可。


7.栈销毁：先销毁掉栈内两个队列，再销毁栈即可。


二、结构体定义

typedef int ElemType;
#define MaxSize 10//栈最大容量
typedef struct {//循环队列
    ElemType* array;
    int front;
    int rear;
    int size;//有效元素个数
}MyQueue;
typedef struct {//队列实现栈
    MyQueue* s1;
    MyQueue* s2;
} MyStack;


三、接口模拟实现

void Test_Stack();//测试函数
bool myStackEmpty(MyStack* obj);//栈判空
MyStack* myStackCreate();//栈初始化
void myStackPush(MyStack* obj, int x);//入栈
int myStackPop(MyStack* obj);//获取栈顶元素并出栈
int myStackTop(MyStack* obj);//获取栈顶元素
int StackSize(MyStack* obj);//获取栈内有效元素个数
void myStackFree(MyStack* obj);//栈销毁


1.栈初始化


MyStack* myStackCreate() {//栈初始化
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (obj == NULL) {//申请失败
        assert(0);
        return NULL;
    }
    obj->s1 = (MyQueue*)malloc(sizeof(MyQueue));
    obj->s2 = (MyQueue*)malloc(sizeof(MyQueue));
    if (obj->s1 == NULL || obj->s2 == NULL) {//申请失败
        assert(0);
        return NULL;
    }
    obj->s1->array = (ElemType*)malloc(sizeof(ElemType) * (MaxSize + 1));//申请MaxSize+1个空间
    obj->s2->array = (ElemType*)malloc(sizeof(ElemType) * (MaxSize + 1));
    if (obj->s1->array == NULL || obj->s2->array == NULL) {//申请失败
        assert(0);
        return NULL;
    }
    obj->s1->front = obj->s1->rear = obj->s1->size = 0;
    obj->s2->front = obj->s2->rear = obj->s2->size = 0;
    return obj;
}


分别堆栈和栈内队列进行初始化申请空间和队头队尾指针以及有效元素个数。


2.入栈


void myStackPush(MyStack* obj, int x) {//入栈
    assert(obj);
    if (obj->s1->size == 0 && obj->s2->size == 0) {//两个队列都为空，入栈到队列s1中
        obj->s1->array[obj->s1->rear] = x;
        obj->s1->rear = (obj->s1->rear + 1) % MaxSize;
        obj->s1->size++;
        return;
    }
    if (obj->s1->size == 0 && obj->s2->size) {//s1为空,s2不为空，则入栈到队列s2中
        if (obj->s2->size == MaxSize) {//栈满（队满）
            return;
        }
        obj->s2->array[obj->s2->rear] = x;
        obj->s2->rear = (obj->s2->rear + 1) % MaxSize;
        obj->s2->size++;
    }
    else {//s2为空,s1不为空，则入栈到队列s1中
        if (obj->s1->size == MaxSize) {//栈满（队满）
            return;
        }
        obj->s1->array[obj->s1->rear] = x;
        obj->s1->rear = (obj->s1->rear + 1) % MaxSize;
        obj->s1->size++;
    }
}


先判断是否栈为空（两个队列都为空），为空则入队到任意一个队列内即可，不为空则判断并入队到不为空的队列中即可。（入队前需先对队列进行判满操作）


3.获取栈顶元素并出栈


int myStackPop(MyStack* obj) {//获取栈顶元素并出栈
    assert(obj);
    if (myStackEmpty(obj)) {//栈判空
        return -1;
    }
    ElemType temp = 0;
    //将不为空的哪个队列的前size-1个元素入队到空队列中，第size个元素即为栈顶
    if (obj->s1->size && obj->s2->size == 0) {//s1不为空
        int flag = obj->s1->size - 1;
        for (int i = 0; i < flag; i++) {
            obj->s2->array[obj->s2->rear] = obj->s1->array[obj->s1->front];
            obj->s2->rear = (obj->s2->rear + 1) % MaxSize;
            obj->s2->size++;
            obj->s1->front = (obj->s1->front + 1) % MaxSize;
            obj->s1->size--;
        }
        temp = obj->s1->array[obj->s1->front];//保存栈顶元素（队尾元素）
        obj->s1->front = (obj->s1->front + 1) % MaxSize;//出栈
        obj->s1->size--;
    }
    else {//s2不为空
        int flag = obj->s2->size - 1;
        for (int i = 0; i < flag; i++) {
            obj->s1->array[obj->s1->rear] = obj->s2->array[obj->s2->front];
            obj->s1->rear = (obj->s1->rear + 1) % MaxSize;
            obj->s1->size++;
            obj->s2->front = (obj->s2->front + 1) % MaxSize;
            obj->s2->size--;
        }
        temp = obj->s2->array[obj->s2->front];//保存栈顶元素（队尾元素）
        obj->s2->front = (obj->s2->front + 1) % MaxSize;//出栈
        obj->s2->size--;
    }
    return temp;//返回栈顶元素
}


用队列模拟栈的操作中，相对比较复杂的就是出栈操作了。但其原理其实也是比较简单的，先判断是否是空栈（即两个队列都为空），为空则无需操作，不为空则只需将不为空的队列内的前n-1个元素依次出队再入队到另一个空队列中即可，最后第n个元素即为栈顶元素，对其1只出队不入队即出栈成功。


4.获取栈顶元素


int myStackTop(MyStack* obj) {//获取栈顶元素
    assert(obj);
    if (myStackEmpty(obj)) {//栈判空
        return -1;
    }
    if (obj->s1->size && obj->s2->size == 0) {//s1不为空，s2为空
        return obj->s1->array[(obj->s1->rear - 1 + MaxSize) % MaxSize];//直接返回队尾元素即栈顶元素
    }
    else {
        return obj->s2->array[(obj->s2->rear - 1 + MaxSize) % MaxSize];
    }
}


栈不为空则直接返回不为空的队列的队尾元素即可。需注意的是，队尾元素为rear-1号下标的元素，而且为了避免队列的假溢出问题，我采用的是循环队列，为了防止数组越界，每次对队头队尾直接操作时，都需要对最大容量进行取余。


5.栈判空


bool myStackEmpty(MyStack* obj) {//栈判空
    if (obj->s1->size == 0 && obj->s2->size == 0) {//两个队列都为空，即栈为空
        return true;
    }
    return false;
}


栈内两个队列都为空即栈为空。


6.获取栈内有效元素个数


int StackSize(MyStack* obj) {//获取栈内有效元素个数
    assert(obj);
    return obj->s1->size > obj->s2->size ? obj->s1->size : obj->s2->size;
}


7.栈销毁


void myStackFree(MyStack* obj) {//栈销毁
    assert(obj);
    if (obj) {
        free(obj->s1->array);
        free(obj->s1);
        free(obj->s2->array);
        free(obj->s2);
        free(obj);
    }
}


四、接口测试

1.测试函数


void Test_Stack() {
    MyStack* s = myStackCreate();//初始化
    myStackPush(s, 1);//入栈
    myStackPush(s, 2);
    myStackPush(s, 3);
    myStackPush(s, 4);
    printf("top=%d\n", myStackPop(s));//获取栈顶元素4并出栈
    printf("bool=%d\n", myStackEmpty(s));//判空 bool=0
    printf("size=%d\n", StackSize(s));//获取有效元素个数3
    printf("top=%d\n", myStackPop(s));//获取栈顶元素3并出栈
    printf("top=%d\n", myStackTop(s));//获取栈顶元素2
    printf("top=%d\n", myStackPop(s));//获取栈顶元素2并出栈
    printf("top=%d\n", myStackPop(s));//获取栈顶元素1并出栈
    printf("size=%d\n", StackSize(s));//获取有效元素个数0
    printf("bool=%d\n", myStackEmpty(s));//判空 bool=1
    myStackFree(s);//栈销毁
}


2.测试结果


1.png


五、完整代码

#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
#include<malloc.h>
typedef int ElemType;
#define MaxSize 10//栈最大容量
typedef struct {//循环队列
    ElemType* array;
    int front;
    int rear;
    int size;//有效元素个数
}MyQueue;
typedef struct {//队列实现栈
    MyQueue* s1;
    MyQueue* s2;
} MyStack;
void Test_Stack();//测试函数
bool myStackEmpty(MyStack* obj);//栈判空
MyStack* myStackCreate();//栈初始化
void myStackPush(MyStack* obj, int x);//入栈
int myStackPop(MyStack* obj);//获取栈顶元素并出栈
int myStackTop(MyStack* obj);//获取栈顶元素
int StackSize(MyStack* obj);//获取栈内有效元素个数
void myStackFree(MyStack* obj);//栈销毁
int main() {
    Test_Stack();
    return 0;
}
void Test_Stack() {
    MyStack* s = myStackCreate();//初始化
    myStackPush(s, 1);//入栈
    myStackPush(s, 2);
    myStackPush(s, 3);
    myStackPush(s, 4);
    printf("top=%d\n", myStackPop(s));//获取栈顶元素4并出栈
    printf("bool=%d\n", myStackEmpty(s));//判空 bool=0
    printf("size=%d\n", StackSize(s));//获取有效元素个数3
    printf("top=%d\n", myStackPop(s));//获取栈顶元素3并出栈
    printf("top=%d\n", myStackTop(s));//获取栈顶元素2
    printf("top=%d\n", myStackPop(s));//获取栈顶元素2并出栈
    printf("top=%d\n", myStackPop(s));//获取栈顶元素1并出栈
    printf("size=%d\n", StackSize(s));//获取有效元素个数0
    printf("bool=%d\n", myStackEmpty(s));//判空 bool=1
    myStackFree(s);//栈销毁
}
MyStack* myStackCreate() {//栈初始化
    MyStack* obj = (MyStack*)malloc(sizeof(MyStack));
    if (obj == NULL) {//申请失败
        assert(0);
        return NULL;
    }
    obj->s1 = (MyQueue*)malloc(sizeof(MyQueue));
    obj->s2 = (MyQueue*)malloc(sizeof(MyQueue));
    if (obj->s1 == NULL || obj->s2 == NULL) {//申请失败
        assert(0);
        return NULL;
    }
    obj->s1->array = (ElemType*)malloc(sizeof(ElemType) * (MaxSize + 1));//申请MaxSize+1个空间
    obj->s2->array = (ElemType*)malloc(sizeof(ElemType) * (MaxSize + 1));
    if (obj->s1->array == NULL || obj->s2->array == NULL) {//申请失败
        assert(0);
        return NULL;
    }
    obj->s1->front = obj->s1->rear = obj->s1->size = 0;
    obj->s2->front = obj->s2->rear = obj->s2->size = 0;
    return obj;
}
void myStackPush(MyStack* obj, int x) {//入栈
    assert(obj);
    if (obj->s1->size == 0 && obj->s2->size == 0) {//两个队列都为空，入栈到队列s1中
        obj->s1->array[obj->s1->rear] = x;
        obj->s1->rear = (obj->s1->rear + 1) % MaxSize;
        obj->s1->size++;
        return;
    }
    if (obj->s1->size == 0 && obj->s2->size) {//s1为空,s2不为空，则入栈到队列s2中
        if (obj->s2->size == MaxSize) {//栈满（队满）
            return;
        }
        obj->s2->array[obj->s2->rear] = x;
        obj->s2->rear = (obj->s2->rear + 1) % MaxSize;
        obj->s2->size++;
    }
    else {//s2为空,s1不为空，则入栈到队列s1中
        if (obj->s1->size == MaxSize) {//栈满（队满）
            return;
        }
        obj->s1->array[obj->s1->rear] = x;
        obj->s1->rear = (obj->s1->rear + 1) % MaxSize;
        obj->s1->size++;
    }
}
int myStackPop(MyStack* obj) {//获取栈顶元素并出栈
    assert(obj);
    if (myStackEmpty(obj)) {//栈判空
        return -1;
    }
    ElemType temp = 0;
    //将不为空的哪个队列的前size-1个元素入队到空队列中，第size个元素即为栈顶
    if (obj->s1->size && obj->s2->size == 0) {//s1不为空
        int flag = obj->s1->size - 1;
        for (int i = 0; i < flag; i++) {
            obj->s2->array[obj->s2->rear] = obj->s1->array[obj->s1->front];
            obj->s2->rear = (obj->s2->rear + 1) % MaxSize;
            obj->s2->size++;
            obj->s1->front = (obj->s1->front + 1) % MaxSize;
            obj->s1->size--;
        }
        temp = obj->s1->array[obj->s1->front];//保存栈顶元素（队尾元素）
        obj->s1->front = (obj->s1->front + 1) % MaxSize;//出栈
        obj->s1->size--;
    }
    else {//s2不为空
        int flag = obj->s2->size - 1;
        for (int i = 0; i < flag; i++) {
            obj->s1->array[obj->s1->rear] = obj->s2->array[obj->s2->front];
            obj->s1->rear = (obj->s1->rear + 1) % MaxSize;
            obj->s1->size++;
            obj->s2->front = (obj->s2->front + 1) % MaxSize;
            obj->s2->size--;
        }
        temp = obj->s2->array[obj->s2->front];//保存栈顶元素（队尾元素）
        obj->s2->front = (obj->s2->front + 1) % MaxSize;//出栈
        obj->s2->size--;
    }
    return temp;//返回栈顶元素
}
int myStackTop(MyStack* obj) {//获取栈顶元素
    assert(obj);
    if (myStackEmpty(obj)) {//栈判空
        return -1;
    }
    if (obj->s1->size && obj->s2->size == 0) {//s1不为空，s2为空
        return obj->s1->array[(obj->s1->rear - 1 + MaxSize) % MaxSize];//直接返回队尾元素即栈顶元素
    }
    else {
        return obj->s2->array[(obj->s2->rear - 1 + MaxSize) % MaxSize];
    }
}
bool myStackEmpty(MyStack* obj) {//栈判空
    if (obj->s1->size == 0 && obj->s2->size == 0) {//两个队列都为空，即栈为空
        return true;
    }
    return false;
}
int StackSize(MyStack* obj) {//获取栈内有效元素个数
    assert(obj);
    return obj->s1->size > obj->s2->size ? obj->s1->size : obj->s2->size;
}
void myStackFree(MyStack* obj) {//栈销毁
    assert(obj);
    if (obj) {
        free(obj->s1->array);
        free(obj->s1);
        free(obj->s2->array);
        free(obj->s2);
        free(obj);
    }
}


关键词：
栈数据结构
队列数据结构
队列栈数据结构
rxzbqcijxqaoi
目录
相关文章
ephemerals__
|
15天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
90 9
那年春天
|
6天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
15 1
德国都芳最好
|
9天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
48 21
html的七十二变
|
12天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
26 2
dufadayang
|
14天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
42 4
肾透侧视攻城狮
|
18天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
17 1
星霜旅人
|
1月前
数据结构（栈与列队）
数据结构（栈与列队）
星霜旅人
17 1
神明木佑
|
1月前
|
存储 JavaScript 前端开发
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
为什么基础数据类型存放在栈中，而引用数据类型存放在堆中？
神明木佑
68 1
白子寰
|
1月前
【数据结构】-- 栈和队列
【数据结构】-- 栈和队列
白子寰
16 0
java冯坚持
|
1月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
30 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器

热门文章

最新文章

  • 1
    我花了一夜用数据结构给女朋友写个H5走迷宫游戏
  • 2
    数据结构学习笔记【持续更新】
  • 3
    【数据结构与算法】一篇文章彻底搞懂二分查找（思路图解+代码优化）两种实现方式，递归与非递归
  • 4
    基于OHCI的USB主机 —— OHCI（自定义数据结构）
  • 5
    学数据结构，只需要基本的编程体验
  • 6
    数据结构（2）：栈的原理和实现
  • 7
    【数据结构7】查找
  • 8
    算法导论第十四章 数据结构的扩张
  • 9
    R语言学习笔记（一）数据结构
  • 10
    基于OHCI的USB主机 —— UFI数据结构2
  • 1
    数据结构~缓存淘汰算法--LRU算法（Java的俩种实现方式，万字解析
    97
  • 2
    数据结构（五）----特殊矩阵的压缩存储
    243
  • 3
    数据结构（九）---并查集
    70
  • 4
    【数据结构与算法 11，高并发系统基础篇
    41
  • 5
    JavaScript 中实现常见数据结构：栈、队列与树
    78
  • 6
    数据结构链表详解(不仅顺序表可以，我链表也可以)
    41
  • 7
    顺序表的实现（迈入数据结构的大门）（2）
    39
  • 8
    顺序表的实现（迈入数据结构的大门）（1）
    32
  • 9
    每个程序员都必须掌握的8种数据结构，retrofit教程
    35
  • 10
    scala中常见数据结构的用法
    45

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云OSS设置跨域访问