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

简介: 【数据结构】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/


题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(pushpoppeekempty):

实现 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)的栈,并支持普通栈的全部四种操作(pushtoppopempty)。

实现 MyStack 类:

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

注意:

  • 你只能使用队列的基本操作 —— 也就是 push to backpeek/pop from frontsizeis 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);
}

提交运行:


结语

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



目录
打赏
0
0
0
0
13
分享
相关文章
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
108 1
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
109 3
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
21 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
6月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
300 77
|
5月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
79 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
6月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
159 7
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问