备案控制台
开发者社区 人工智能 文章 正文

数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）二

2024-06-06 15
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）二

数据结构和算法学习记录——栈和队列习题-用队列实现栈、用栈实现队列（核心思路、解题过程、完整题解）一：https://developer.aliyun.com/article/1530537


销毁栈函数

销毁栈不能只free掉栈结构体的空间，栈结构里面还有两个队列结构，而队列里面有指针指向链式结构。只free掉栈结构体时，会发生内存泄漏，即队列里面指向链式结构的指针没得到释放。所以我们应该由内到外，先把两个队列free掉，最后再free掉栈。

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

完整题解（C语言）

typedef int QDataType;
 
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QueueNode;
 
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
}Queue;
void QueueInit(Queue* pq)
{
  assert(pq);
 
  pq->head = NULL;
  pq->tail = NULL;
}
 
void QueueDestroy(Queue* pq)
{
  assert(pq);
 
  QueueNode* cur = pq->head;
  while (cur != NULL)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
 
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  newnode->data = x;
  newnode->next = NULL;
 
  if (pq->head == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
 
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
 
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  QueueNode* next = pq->head->next;
  free(pq->head);
  pq->head = next;
  if (pq->head == NULL)
  {
    pq->tail = NULL;
  }
}
 
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->head->data;
}
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
 
  return pq->tail->data;
}
 
int QueueSize(Queue* pq)
{
  assert(pq);
 
  int n = 0;
  QueueNode* cur = pq->head;
  while (cur)
  {
    n++;
    cur = cur->next;
  }
  return n;
}
typedef struct
{
    Queue q1;
    Queue q2;
} MyStack;
 
 
MyStack* myStackCreate() 
{
    MyStack* st = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&st->q1);
    QueueInit(&st->q2);
    return st;
}
 
void myStackPush(MyStack* obj, int x) 
{
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);        
    }
    else
    {
        QueuePush(&obj->q2,x);
    }
}
 
int myStackPop(MyStack* obj) 
{
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
 
    while(QueueSize(nonemptyQ) > 1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ)); 
        QueuePop(nonemptyQ);       
    }
    int top = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);
 
    return top;
}
 
int myStackTop(MyStack* obj)
{
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}
 
bool myStackEmpty(MyStack* obj) 
{
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
 
void myStackFree(MyStack* obj)
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}
 
/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

用栈实现队列

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。

你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

题目示例

输入：

["MyQueue", "push", "push", "peek", "pop", "empty"]

[[], [1], [2], [], [], []]

输出：

[null, null, null, 1, 1, false]


解释：

MyQueue myQueue = new MyQueue();

myQueue.push(1); // queue is: [1]

myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)

myQueue.peek(); // return 1

myQueue.pop(); // return 1, queue is [2]

myQueue.empty(); // return false

核心思路

与上一道题本质上是没有区别的，所以就只写一下核心思路


要用两个栈来实现队列： 入数据时，入到其中的一个栈中。（设此栈为PushStack） 出数据时，将有数据的栈转移到另一个栈，这样就把数据倒过来了，这时直接出这个栈的数据就实现了先进先出了（设此栈为PopStack）


完整题解（C语言）

typedef int STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps)
{
  assert(ps);
 
  ps->a = NULL;
  ps->top = 0; //或者ps->top = -1;
  ps->capacity = 0;
}
 
 
void StackPrint(ST* ps)
{
  assert(ps);
 
  for (int i = 0; i < ps->top; i++)
  {
    printf("%d\t", ps->a[i]);
  }
  printf("\n");
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
 
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;//top为0返回真，否则返回假
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
 
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
 
  ps->a[ps->top] = x;
  ps->top++;
}
 
void StackPop(ST* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
 
  ps->top--;
}
 
STDataType StackTop(ST* ps)//取出栈顶元素
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
 
int StackSize(ST* ps)//计算栈中有多少个元素
{
  assert(ps);
  return ps->top;
}
 
typedef struct
{
    ST pushST;
    ST popST;
} MyQueue;
 
 
MyQueue* myQueueCreate()
{
    MyQueue* q = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&q->pushST);
    StackInit(&q->popST);
 
    return q;
}
 
void myQueuePush(MyQueue* obj, int x)
{
    StackPush(&obj->pushST,x);
}
 
int myQueuePop(MyQueue* obj)
{
    //如果popST中没有数据，将pushST的数据传递过去
    //popST中的数据就可以符合先进先出的顺序了
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }        
    }
    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return front;
}
 
int myQueuePeek(MyQueue* obj)
{
    //如果popST中没有数据，将pushST的数据传递过去
    //popST中的数据就符合先进先出的顺序
    if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST,StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    return StackTop(&obj->popST);
}
 
bool myQueueEmpty(MyQueue* obj)
{
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
 
}
 
void myQueueFree(MyQueue* obj)
{
    StackDestroy(&obj->pushST);
    StackDestroy(&obj->popST);
    free(obj);
}
 
/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/
文章标签：
算法
C语言
关键词：
算法学习
数据结构算法
数据结构队列
数据结构栈队列
数据结构栈
sky_qiyi
目录
相关文章
西瓜味的敌敌畏
|
21小时前
|
存储 缓存 算法
队列和栈
队列和栈
西瓜味的敌敌畏
13 0
空白诗
|
1天前
|
算法 搜索推荐 JavaScript
算法学习：快速排序
算法学习：快速排序
空白诗
7 1
空白诗
|
1天前
|
机器学习/深度学习 存储 算法
算法学习：递归
算法学习：递归
空白诗
7 0
空白诗
|
1天前
|
存储 算法 Go
算法学习：数组 vs 链表
算法学习：数组 vs 链表
空白诗
6 0
空白诗
|
1天前
|
算法 JavaScript 前端开发
算法学习：二分查找
算法学习：二分查找
空白诗
5 0
Eternity._
|
4天前
数据结构——栈和队列
数据结构——栈和队列
Eternity._
7 1
誓则盟约
|
7天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
誓则盟约
12 3
加油，旭杏
|
15天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现（两个方式实现）
【数据结构】栈和队列的模拟实现（两个方式实现）
加油，旭杏
13 1
邢仕冲的一亩三分地
|
1天前
顺序栈实现出栈入栈
顺序栈实现出栈入栈
邢仕冲的一亩三分地
5 0
一只大鸽子
|
3天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
一只大鸽子
8 1

热门文章

最新文章

  • 1
    什么是优化技术？给算法小白同学的快速讲解和上手文
  • 2
    椭圆曲线密码算法（ECC）：数学之美与安全之钥
  • 3
    【视频】支持向量机算法原理和Python用户流失数据挖掘SVM实例（下）
  • 4
    【视频】支持向量机算法原理和Python用户流失数据挖掘SVM实例（上）
  • 5
    基于DCT和扩频的音频水印嵌入提取算法matlab仿真
  • 6
    智能解决装箱问题：使用优化算法实现高效包装
  • 7
    分布式(计算机算法)
  • 8
    揭秘深度学习中的优化算法
  • 9
    Rust代码编写高性能屏幕监控软件的核心算法
  • 10
    【Python机器学习专栏】关联规则学习：Apriori算法详解
  • 1
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
    99
  • 2
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（一）
    60
  • 3
    【软件设计师备考 专题 】数据结构深度解析：从数组到图
    63
  • 4
    揭秘数组：数据结构的基石与代码实践解析
    11
  • 5
    Java 学习路线：基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
    113
  • 6
    Golang 数据结构：图
    48
  • 7
    C/C++ 数据结构设计与应用（三）：运算符重载的策略与实践 (Operator Overloading Strategies and Practices)
    27
  • 8
    C/C++ 数据结构设计与应用（二）：自定义数据结构的设计 (Design of Custom Data Structures)
    69
  • 9
    C/C++ 数据结构设计与应用（一）： 数据结构的选择与应用 (Data Structure Selection and Application)
    46
  • 10
    【手撕数据结构】二分查找(好多细节)
    19

    • 相关课程

    更多
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • TLS1.3的后量子算法集成
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考