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

【数据结构】第七站：栈和队列力扣题

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


一、用队列实现栈

题目链接：力扣

对于这道题，我们想要使用两个队列去实现栈

队列的性质是先进先出，而栈的性质是先进后出

为了实现性质转换，我们需要有一个队列时刻保持空状态，当我们想要入栈的时候，我们在不是空的队列进行插入即可

而想要实现出栈，假设又n+1个数据，先将前n个数据给倒入另一个空队列，最后出最后一个数据即可

有了思路，但是这道题最难的地方就是栈的结构了。也就是创建栈的函数，根据题目的要求，我们是需要创建一个栈并且返回这个栈的指针的。所以这个创建栈的函数就类似于带头双向循环链表的创建。如下图所示，是我们这个栈的结构

所以我们很容易就写出来了第一个函数

MyStack* myStackCreate() {
    MyStack* st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(st->q1));
    QueueInit(&(st->q2));
    return st;
}

我们将栈的结构给构建出来以后，这个题目就变得十分简单了。事实上，栈和队列的本身实现并不难，难的是结构的构造

最终代码为

typedef int QDateType;
typedef struct QNode
{
  QDateType data;
  struct QNode* next;
}QNode;
typedef  struct Queue
{
  QNode* head;
  QNode* tail;
  int size;
}Queue;
//初始化队列
void QueueInit(Queue* q);
//队尾入队列
void QueuePush(Queue* q, QDateType x);
//队头出队列
void QueuePop(Queue* q);
//获取队列头部元素
QDateType QueueFront(Queue* q);
//获取队列尾部元素
QDateType QueueBack(Queue* q);
//获取队列中的有效元素个数
int QueueSize(Queue* q);
//检测队列是否为空
bool QueueEmpty(Queue* q);
//销毁队列
void QueueDestroy(Queue* q);
//初始化队列
void QueueInit(Queue* q)
{
  assert(q);
  q->head = NULL;
  q->tail = NULL;
  q->size = 0;
}
//申请一个结点
QNode* BuyQNode(QDateType x)
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return NULL;
  }
  newnode->next = NULL;
  newnode->data = x;
  return newnode;
}
//队尾入队列
void QueuePush(Queue* q, QDateType x)
{
  assert(q);
  QNode* newnode = BuyQNode(x);
  if (q->tail == NULL)
  {
    q->head = q->tail = newnode;
  }
  else
  {
    q->tail->next = newnode;
    q->tail = q->tail->next;
  }
  q->size++;
}
//队头出队列
void QueuePop(Queue* q)
{
  assert(q);
  assert(q->head);
  QNode* first = q->head->next;
  free(q->head);
  q->head = first;
  q->size--;
  if (q->head == NULL)
  {
    q->tail = NULL;
  }
}
//获取队列头部元素
QDateType QueueFront(Queue* q)
{
  assert(q);
  assert(q->head);
  return q->head->data;
}
//获取队列尾部元素
QDateType QueueBack(Queue* q)
{
  assert(q);
  assert(q->head);
  return q->tail->data;
}
//获取队列中的有效元素个数
int QueueSize(Queue* q)
{
  assert(q);
  return q->size;
}
//检测队列是否为空
bool QueueEmpty(Queue* q)
{
  assert(q);
  return q->head == NULL;
}
//销毁队列
void QueueDestroy(Queue* q)
{
  assert(q);
  QNode* cur = q->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  q->head = q->tail = NULL;
  q->size = 0;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* st=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&(st->q1));
    QueueInit(&(st->q2));
    return st;
}
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&(obj->q1))&&QueueEmpty(&(obj->q2));
}
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    Queue* emptyq=&(obj->q1);
    Queue* noemptyq=&(obj->q2);
    if(!QueueEmpty(emptyq))
    {
        noemptyq=&(obj->q1);
        emptyq=&(obj->q2);
    }
    QueuePush(noemptyq,x);
}
int myStackPop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    Queue* emptyq=&(obj->q1);
    Queue* noemptyq=&(obj->q2);
    if(!QueueEmpty(emptyq))
    {
        noemptyq=&(obj->q1);
        emptyq=&(obj->q2);
    }
    while(QueueSize(noemptyq)>1)
    {
        QDateType x=QueueFront(noemptyq);
        QueuePop(noemptyq);
        QueuePush(emptyq,x);
    }
    QDateType x=QueueFront(noemptyq);
    QueuePop(noemptyq);
    return x;
}
int myStackTop(MyStack* obj) {
    assert(obj);
    assert(!myStackEmpty(obj));
    Queue* emptyq=&(obj->q1);
    Queue* noemptyq=&(obj->q2);
    if(!QueueEmpty(emptyq))
    {
        noemptyq=&(obj->q1);
        emptyq=&(obj->q2);
    }
    while(QueueSize(noemptyq)>1)
    {
        QDateType x=QueueFront(noemptyq);
        QueuePop(noemptyq);
        QueuePush(emptyq,x);
    }
    QDateType x=QueueFront(noemptyq);
    QueuePush(emptyq,x);
    QueuePop(noemptyq);
    //QDateType x=QueueBack(noemptyq);
    return x;
}
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);
*/

二、用栈实现队列

题目链接：力扣

对于这道题，与上面的题目十分类似，我们使用两各栈去模拟一个队列。那么我们可以这样做，一个栈专门用来入数据，一个栈专门用来出数据，当出数据的栈为空的时候，将入数据的栈的数据全部导入出数据的栈中。这样我们就可以模拟出一个队列

同样的，这个题的难点，仍然是结构。

如上所示，是我们的结构示意图

typedef struct {
    Stack push;
    Stack pop;
} MyQueue;

一旦我们将结构给理清楚了，那么这道题就易如反掌了

typedef int  STDateType;
typedef struct Stack
{
  STDateType* a;
  int top;
  int capacity;
}Stack;
//栈的初始化
void StackInit(Stack* ps);
//栈的销毁
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps, STDateType x);
//出栈
void StackPop(Stack* ps);
//栈的个数
int StackSize(Stack* ps);
//栈是否为空
bool StackEmpty(Stack* ps);
//取出栈顶的数据
STDateType StackTop(Stack* ps);
//栈的初始化
void StackInit(Stack* ps)
{
  assert(ps);
  ps->a = (STDateType*)malloc(sizeof(STDateType) * 4);
  if (ps->a == NULL)
  {
    perror("malloc fail");
    return;
  }
  ps->top = 0;
  ps->capacity = 4;
}
//栈的销毁
void StackDestroy(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
//入栈
void StackPush(Stack* ps, STDateType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    STDateType* tmp = (STDateType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDateType));
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    ps->a = tmp;
    ps->capacity *= 2;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
//栈的个数
int StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
//取出栈顶的数据
STDateType StackTop(Stack* ps)
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->a[ps->top - 1];
}
typedef struct {
    Stack push;
    Stack pop;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* q=(MyQueue*)malloc(sizeof(MyQueue));
    if(q==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    StackInit(&(q->push));
    StackInit(&(q->pop));
    return q;
}
bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return StackEmpty(&(obj->push))&&StackEmpty(&(obj->pop));
}
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    StackPush(&(obj->push),x);
}
int myQueuePop(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&(obj->pop)))
    {
        while(!StackEmpty(&(obj->push)))
        {
            STDateType x=StackTop(&(obj->push));
            StackPop(&(obj->push));
            StackPush(&(obj->pop),x);
        }
    }
    STDateType x=StackTop(&(obj->pop));
    StackPop(&(obj->pop));
    return x;
}
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&(obj->pop)))
    {
        while(!StackEmpty(&(obj->push)))
        {
            STDateType x=StackTop(&(obj->push));
            StackPop(&(obj->push));
            StackPush(&(obj->pop),x);
        }
    }
    STDateType x=StackTop(&(obj->pop));
    return x;
}
void myQueueFree(MyQueue* obj) {
    assert(obj);
    StackDestroy(&(obj->push));
    StackDestroy(&(obj->pop));
    free(obj);
    obj=NULL;
}
/**
 * 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);
*/

三、设计循环队列

题目链接：力扣

对于这道题，设计循环队列，我们最容易想到的方法就是使用链表。不难想到，对于单链表只需要将头尾给链接起来，似乎就能变成循环队列了

我们假设k为4，

我们一开始让front和rear都指向第一个元素，当需要入队列的时候，rear指向下一个元素

当想要出队列的时候，让front往后走一步即可

我们继续入队列，当数据入满的时候，如下图所示，我们发现一个问题，队列满和队列空都始front和rear相等，无法辨别。

为了解决这个问题，我们有两种解决方案：

1.使用一个变量size来记住队列有几个元素

2.多开辟一个结点，这样当队列满的时候，rear->next==front这就是判断队列满的标志了，得以区分

这样了以后，其实还是有一点问题的，如果我们需要取出尾数据的话，十分难受，我们必须得去遍历链表。

当然我们可以多定义一个指针有进行处理，但是这样代码可读性变差了

由上述分析得知，循环队列并不适合使用链表来实现，反而适合数组。

想要使用数组来实现，那么我们得先分析基本的思路

如果使用数组来模拟的话，首先我们假设k为4，为了区分满与空，我们需要开辟5个空间

当我们入队的时候，rear++

当我们出队的时候，front++

当数据一直插入直到满的时候，数组为下面的情景

此时rear+1==front，代表队列已满

有了上述的分析，那么这道题就很简单了，代码如下所示：

typedef struct {
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    assert(obj);
    return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    assert(obj);
    return obj->front==(obj->rear+1)%(obj->k+1);
}
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a=(int*)malloc(sizeof(int)*(k+1));
    q->front=0;
    q->rear=0;
    q->k=k;
    return q;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    assert(obj);
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear %= obj->k+1;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    obj->front++;
    obj->front %= obj->k+1;
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    return obj->a[(obj->rear-1+obj->k+1)%(obj->k+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    assert(obj);
    free(obj->a);
    obj->a=NULL;
    obj->front=0;
    obj->rear=0;
    obj->k=0;
    free(obj);
    obj=NULL;
}   
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 * bool param_2 = myCircularQueueDeQueue(obj);
 * int param_3 = myCircularQueueFront(obj);
 * int param_4 = myCircularQueueRear(obj);
 * bool param_5 = myCircularQueueIsEmpty(obj);
 * bool param_6 = myCircularQueueIsFull(obj);
 * myCircularQueueFree(obj);
*/

本期内容到此为止

如果对你有帮助的话，不要忘记点赞加收藏哦！！！

关键词：
数据结构队列
数据结构栈队列
数据结构栈
LeetCode数据结构
数据结构栈和队列
青色忘川
目录
相关文章
那年春天
|
26天前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
24 1
龙大吉
|
14天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
33 5
德国都芳最好
|
29天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
78 21
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
31 2
XIAZHI
|
21天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
39 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
141 9
dufadayang
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
51 4
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
40 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
21 1
禁默
|
2月前
初步认识栈和队列
初步认识栈和队列
禁默
61 10