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

【数据结构】3道经典面试题带你玩转栈与队列

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

一.有效的括号

题目链接

https://leetcode.cn/problems/valid-parentheses/

题目描述

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

题目详情

解题思路

本题解题思路为:

  • 创建一个栈
  • 遍历字符串s,遇到左括号则将其入栈
  • 遇到右括号则取栈顶元素和它匹配
  • 匹配成功则将栈顶元素出栈继续遍历,失败则返回false
  • 直到遍历完字符串s,栈中元素也都恰好匹配完毕则返回true

细节问题:动态开辟的内存需要换给系统,在程序设置好几个return点的情况下特别要保证每个return前都应有Destroy的操作.

解题代码

综上,本题解题代码如下:

typedef char STDataType;
 
typedef struct Stack
{
  STDataType*arr;
  int top;
  int capacity;
}ST;
 
bool STEmpty(ST* ps)//判空,为空则真
{
  assert(ps);
  return ps->top==0;
}
 
void STInit(ST* ps)
{
  assert(ps);
 
  ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->arr == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
  ps->capacity = 4;
  ps->top = 0;   //top表示栈顶元素的下一个
                 //top指向栈顶元素的话,top给-1
}
 
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->arr);
  ps->arr = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
 
void STPush(ST* ps, STDataType x)
{
  assert(ps);
 
  if (ps->top == ps->capacity)//扩容
  {
    STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail::\n");
      return;
    }
    ps->arr = tmp;
    ps->capacity *= 2;
  }
  ps->arr[ps->top] = x;
  ps->top++;
}
 
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
  ps->top--;
}
 
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
  return ps->arr[ps->top - 1];
}
 
bool isValid(char* s) 
{
    ST st;
    STInit(&st);
    char*cur=s;
   
    while(*cur!='\0')
    {
         //如果是左括号,入栈
        if(*cur=='{'||*cur=='['||*cur=='(')
        {
            STPush(&st,*cur);
        }
        //如果是右括号,和栈顶元素匹配,相同就出栈,不同就false
        else
        {
            if(STEmpty(&st))
            {
                STDestroy(&st);
                return false;
            }
            if(*cur==')'&&STTop(&st)=='(')
            {
                STPop(&st);
            }
            else if(*cur==']'&&STTop(&st)=='[')
            {
                STPop(&st);
            }
            else if(*cur=='}'&&STTop(&st)=='{')
            {
                STPop(&st);
            }
            else
            {
                STDestroy(&st);
                return false;
            }
        }
        cur++;
    }
    if(STEmpty(&st))
    {
         STDestroy(&st);
         return true;
    } 
    else
    {
         STDestroy(&st);
        return false;
    }
        
}

提交运行:

二.用栈实现队列

题目链接

https://leetcode.cn/problems/implement-queue-using-stacks/

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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栈和pop栈)
  • MyQueue入队入push栈即可.
  • MyQueue出队出pop栈顶的元素,如果pop栈为空,则先将push栈中的所有元素依次入pop栈后再出pop栈顶元素,图示如下:
  • MyQueue初始化,取队头元素,查空,销毁函数逻辑较简单,思路见下方解题代码注释.

解题代码

综上,本题解题代码如下:

//先创建两个栈及栈的相关操作,然后组合实现队列的效果
//定义栈:
typedef int STDataType;
typedef struct Stack
{
  STDataType*arr;
  int top;
  int capacity;
}ST;
 
void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);//判空,为空则真
STDataType STTop(ST* ps);
//实现栈:
void STInit(ST* ps)
{
  assert(ps);
  ps->arr = (STDataType*)malloc(sizeof(STDataType) * 4);
  if (ps->arr == NULL)
  {
    perror("malloc fail::\n");
    return;
  }
  ps->capacity = 4;
  ps->top = 0;   //top表示栈顶元素的下一个
                 //top指向栈顶元素的话,top给-1
}
 
void STDestroy(ST* ps)
{
  assert(ps);
  free(ps->arr);
  ps->arr = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
 
void STPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)//扩容
  {
    STDataType* tmp = (STDataType*)realloc(ps->arr, sizeof(STDataType) * ps->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc fail::\n");
      return;
    }
    ps->arr = tmp;
    ps->capacity *= 2;
  }
  ps->arr[ps->top] = x;
  ps->top++;
}
 
void STPop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
  ps->top--;
}
 
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
 
bool STEmpty(ST* ps)//判空,为空则真
{
  assert(ps);
  return ps->top==0;
}
 
STDataType STTop(ST* ps)
{
  assert(ps);
  assert(!STEmpty(ps));
  return ps->arr[ps->top - 1];
}
 
//实现队列
 
 
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;
 
 
MyQueue* myQueueCreate() //MyQueue结构体初始化,将两个栈分别初始化即可
{
    MyQueue *obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("malloc fail::\n");
        return NULL;
    }
    STInit(&obj->pushst);
    STInit(&obj->popst);
    return obj;
}
 
void myQueuePush(MyQueue* obj, int x) //MyQueue进栈,进栈元素进pushst栈即可
{
    STPush(&obj->pushst , x);
}
 
int myQueuePop(MyQueue* obj)//MyQueue出栈
{
    //如果pop栈不为空就出pop栈顶的元素
    if(!STEmpty(&obj->popst))
    {
        int x=STTop(&obj->popst);
        STPop(&obj->popst);
        return x; 
    }
    else//如果pop栈为空,就先倒Push栈的元素过来,再出pop栈顶的元素
    {
        while(!STEmpty(&obj->pushst))//倒push栈必须将现有的元素全部倒过来
        {
            int x=STTop(&obj->pushst);
            STPush(&obj->popst , x);
            STPop(&obj->pushst);
        }
        //倒完出pop栈顶元素
        int x=STTop(&obj->popst);
        STPop(&obj->popst);
        return x;
    }
}
 
int myQueuePeek(MyQueue* obj)//MyQueue取栈顶元素(逻辑比出栈少一个出) 
{
    if(!STEmpty(&obj->popst))
    {
        return STTop(&obj->popst);
    }
    else//如果pop栈为空,就先倒Push的过来,再pop
    {
        while(!STEmpty(&obj->pushst))
        {
            int x=STTop(&obj->pushst);
            STPush(&obj->popst , x);
            STPop(&obj->pushst);
        }
        return STTop(&obj->popst);
    }
}
 
bool myQueueEmpty(MyQueue* obj)//MyQueue查空,push和pop栈都为空则MyQueue为空
 {
    return (STEmpty(&obj->pushst)&&STEmpty(&obj->popst));
}
 
void myQueueFree(MyQueue* obj) //MyQueue销毁,分别将push栈和pop栈销毁后把obj销毁即可
{
    STDestroy(&obj->pushst);
    STDestroy(&obj->popst);
    free(obj);
}

提交运行:

三.用队列实现栈

题目链接

https://leetcode.cn/problems/implement-stack-using-queues/

题目描述

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

题目详情

解题思路

本题解题思路为:

  • 先定义队列的结构并完成其相关操作函数(即定义队列,实现队列)
  • 创建MyStack结构体,其中包含两个队列(q1队列和q2队列),结构图示如下:
  • 我们需要一直保持q1和q2中有一个空队列,以便可以模拟出栈.
  • MyStack入栈时入q1和q2中的非空栈,图示如下:
  • MyStack出栈时将q1和q2中的非空队的前n-1个元素全部入队到空队列中,然后将剩下的那个元素出栈,图示如下:
  • MyStack取栈顶元素相当于取非空队的队尾元素.
  • MyStack初始化,判空,销毁逻辑较为简单,思路见下方解题代码注释.

解题代码

//先自己创建两个队列,然后调用这两个队列完成栈的操作.
 
//定义队列
typedef int QDatatype;
typedef struct QueueNode//一个是结点结构
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
typedef struct Queue//一个是队列整体结构
{
  QNode* head;
  QNode* tail;
  int size ;
}Que;
void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que* pq,QDatatype x);
void QueuePop(Que* pq);
int QueueSize(Que* pq);
bool QueueEmpty(Que* pq);
QDatatype QueueFront(Que* pq);
QDatatype QueueBack(Que* pq);
 
//实现队列操作
void QueueInit(Que* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueueDestroy(Que* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
 
void QueuePush(Que* pq, QDatatype x) //入队是尾插
{
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->head == NULL)//头插
  {
    assert(pq->tail == NULL);
    pq->head = pq->tail = newnode;
  }
  else//尾插
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
  pq->size++;
}
 
void QueuePop(Que* pq)//出队是头删
{
  assert(pq);
  assert(!QueueEmpty(pq));//assert为假会终止程序
  QNode* cur = pq;
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
  pq->size--;
}
 
int QueueSize(Que* pq)
{
  assert(pq);
  return pq->size;
}
 
bool QueueEmpty(Que* pq)//判空!为空返回真!
{
  assert(pq);
  return pq->size==0;
}
 
QDatatype QueueFront(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
 
QDatatype QueueBack(Que* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
 
//实现栈
typedef struct 
{
    Que q1;
    Que q2;
} MyStack;
 
MyStack* myStackCreate() 
{
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
    {
        perror("malloc fail::\n");
        return NULL;
    }
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
 
void myStackPush(MyStack* obj, int x) //入栈入非空队
{
    if(QueueEmpty(&obj->q1))//如果q1为空,入q2
    {
        QueuePush(&obj->q2,x);
    }
    else
    {
        QueuePush(&obj->q1,x);
    }
 
    //都为空走else,也可以
}
 
//出栈把非空队前n-1个元素全部插入空队,然后出非空队
int myStackPop(MyStack* obj) 
{
    if(QueueEmpty(&obj->q1))//如果q1为空,出q2的n-1元素到q1
    {
        int n=QueueSize(&obj->q2)-1;
        while(n--)//先出q2再入q1
        {
            int x=QueueFront(&obj->q2);
            QueuePush(&obj->q1,x);
            QueuePop(&obj->q2);
        }
        //q2的最后一个元素出函数
        int top=QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        return top;
    }
    else//如果q2为空,出q1的n-1元素到q2
    {
        int n=QueueSize(&obj->q1)-1;
        while(n--)//先出q2再入q1
        {
            int x=QueueFront(&obj->q1);
            QueuePush(&obj->q2,x);
            QueuePop(&obj->q1);
        }
        //q2的最后一个元素出函数
        int top=QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        return top;
    }
}
 
int myStackTop(MyStack* obj)//栈顶=队尾
{
    if(QueueEmpty(&obj->q1))//如果q1为空,返回q2队尾
    {
        return QueueBack(&obj->q2);
    }
    else
    {
        return QueueBack(&obj->q1);
    }
}
 
bool myStackEmpty(MyStack* obj) //q1&&q2为空才为空
{
    return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));
}
 
void myStackFree(MyStack* obj) //释放q1,q2,obj
{
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

提交运行:

结语

希望通过上面的题目能使大家对栈和队列这两个经典的数据结构的理解以及运用能够更上一层楼,欢迎大佬们留言或私信与我交流.学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!


关键词：
数据结构队列
数据结构栈
数据结构栈队列
数据结构面试
数据结构面试栈
修修修也
目录
相关文章
球球不吃虾
|
1天前
|
前端开发 JavaScript 算法
JavaScript 中实现常见数据结构：栈、队列与树
JavaScript 中实现常见数据结构：栈、队列与树
球球不吃虾
6 0
热爱嵌入式的小佳同学
|
2天前
|
存储 编译器 C语言
数据结构——顺序队列与链式队列的实现-2
数据结构——顺序队列与链式队列的实现
热爱嵌入式的小佳同学
22 2
数据结构——顺序队列与链式队列的实现-2
热爱嵌入式的小佳同学
|
2天前
|
存储 C语言
数据结构——顺序队列与链式队列的实现-1
数据结构——顺序队列与链式队列的实现
热爱嵌入式的小佳同学
22 1
数据结构——顺序队列与链式队列的实现-1
热爱嵌入式的小佳同学
|
2天前
|
存储 NoSQL C语言
数据结构——顺序栈与链式栈的实现-2
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
15 1
数据结构——顺序栈与链式栈的实现-2
热爱嵌入式的小佳同学
|
2天前
|
存储 C语言
数据结构——顺序栈与链式栈的实现-1
数据结构——顺序栈与链式栈的实现
热爱嵌入式的小佳同学
17 0
数据结构——顺序栈与链式栈的实现-1
toKeep
|
2天前
栈的基本应用
栈的基本应用
toKeep
12 3
toKeep
|
2天前
栈与队列理解
栈与队列理解
toKeep
13 1
Bigcrab__
|
2天前
|
存储 算法
数据结构与算法 栈与队列
数据结构与算法 栈与队列
Bigcrab__
12 0
数据结构与算法 栈与队列
天玑y
|
2天前
|
C++
数据结构（顺序队列 循环队列
数据结构（顺序队列 循环队列
天玑y
10 0
天玑y
|
2天前
|
C++
数据结构（共享栈
数据结构（共享栈
天玑y
9 0

热门文章

最新文章

  • 1
    python学习-函数模块，数据结构，字符串和列表（下）
  • 2
    Redis入门到通关之Redis数据结构-String篇
  • 3
    Redis入门到通关之Redis数据结构-List篇
  • 4
    Redis入门到通关之数据结构解析-SkipList
  • 5
    Pandas数据结构详解：Series与DataFrame的奥秘
  • 6
    Redis入门到通关之Redis数据结构-Hash篇
  • 7
    二叉树和数据结构
  • 8
    数据结构---B+Tree
  • 9
    Redis入门到通关之数据结构解析-Dict
  • 10
    单链表——“数据结构与算法”
  • 1
    vue面试题目汇总
    40
  • 2
    首次面试经历（忘指导）当我在简历上写了苍穹外卖，瑞吉外卖时……
    334
  • 3
    【springboot原理篇】Bean的加载方式，面试必看
    54
  • 4
    【Kafka面试演练】那Kafka消费者手动提交、自动提交有什么区别？
    79
  • 5
    【数组相关面试题】LeetCode试题
    20
  • 6
    网安面试指南——（渗透，攻击，防御）
    105
  • 7
    全球AI人才报告：硅谷40万人大裁员，码农地狱级面试12场！
    35
  • 8
    Java开发面试题 | 2023
    60
  • 9
    【怒怼大厂面试官】你先说说知道哪些MySQL的高级特性
    56
  • 10
    LeetCode刷题--- 面试题 01.07. 旋转矩阵（原地旋转+翻转替旋转）
    44

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 面试常考算法
  • 阿里云技术面试红宝书
  • 阿里云技术面试红宝书
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考