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

LeetCode 热题100——栈与队列专题（三）

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

一、有效的括号

20.有效的括号（题目链接）



思路：


1）括号的顺序匹配：用栈实现，遇到左括号入，遇到右括号出（保证所出的左括号与右括号对应），否则顺序不匹配。


2）括号的数量匹配：


1>左括号大于右括号：用栈实现，遇到左括号入，遇到右括号出，遍历完字符数组，此时栈不为空，则说明左括号数量大于右括号；


2>右括号大于左括号：遇到右括号出时，判断栈是否为空，若此时栈为空，说明右括号数量大于左括号；


typedef char  SDateType;
typedef struct Stack
{
  SDateType* a;
  int top;
  int capacity;
}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void DestoryStack(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{
  assert(ps);
  //扩容
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
    if (tmp == NULL)
    {
      perror("realloc fail:");
      return;
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
  //尾插
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);//只少有一个元素，才能删除
  ps->top--;
}
//栈的有效个数和栈顶元素
int  StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
int   StackTop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
int isValid(char* s) {
  Stack ps;
  InitStack(&ps);
  while (*s)
  {
    if (*s == '[' || *s == '(' || *s == '{')
    {
      StackPush(&ps, *s);
      s++;
    }
    else
    {
      if (StackEmpty(&ps))
      {
        return false;
      }
      char tmp = StackTop(&ps);
      StackPop(&ps);
      if ((*s == ']' && tmp != '[') ||
        (*s == '}' && tmp != '{') ||
        (*s == ')' && tmp != '('))
      {
        return false;
      }
      s++;
    }
  }
  if (!StackEmpty(&ps))
  {
    return false;
  }
  else {
    return true;
  }
  DestoryStack(&ps);
}


二、用队列实现栈

225. 用队列复制栈（题目链接）


思路： 栈是后进先出，队列是先进先出。

用俩队列实现栈

1）入栈时，选择有数据的队列入数据；

2）出栈时，将有数据队列中前k-1个数据出队列，并入到空队列中，返回并出有数据队列的最后一个数据


a8dc38fe8101a76f5ba91d6addf8468a_513722ad696647e1b41a04d54848aecd.png

typedef int QDateType;
typedef struct QueueNode
{
  QDateType val;
  struct QueueNode * next;
}QueueNode;
typedef struct Queue
{
  QueueNode *head;
  QueueNode *tail;
  QDateType size;
}Queue;
// 初始化队列
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
void QueuePush(Queue* pq, QDateType x)
{
  assert(pq);
  QueueNode* node = (QueueNode*)malloc(sizeof(QueueNode));
  node->val = x;
  node->next = NULL;
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = node;
    pq->size++;
  }
  else
  {
    pq->tail->next = node;
    pq->tail = node;
    pq->size++;
  }
}
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head != NULL);//只少保证一个节点
  QueueNode* del = pq->head;
  pq->head = pq->head->next;
  free(del);
  del = NULL;
  pq->size--;
  if (pq->head == NULL)//只有一个节点处理
  {
    pq->tail = NULL;
  }
}
// 返回队头和队尾
QDateType QueueFront(Queue* pq)
{
  assert(pq);
  return pq->head->val;
}
QDateType QueueBack(Queue* pq)
{
  assert(pq);
  return pq->tail->val;
}
// 获取队列中有效元素个数
int QueueSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head==NULL;
}
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QueueNode* cur = pq->head;
  while (cur)
  {
    QueueNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
  pq->size = 0;
}
typedef struct {
    Queue q1;
     Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}
void myStackPush(MyStack* obj, int x) {
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else{
        QueuePush(&obj->q2,x);
    }
}
bool myStackEmpty(MyStack* obj) {
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
int myStackPop(MyStack* obj) {
    assert(!myStackEmpty(obj));
    Queue * empty=&obj->q1;
    Queue * nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    while(QueueSize(nonempty)!=1)
    {
       int tmp= QueueFront(nonempty);
       QueuePush(empty,tmp);
        QueuePop(nonempty);
    }
     int tmp= QueueFront(nonempty);
      QueuePop(nonempty);
      return tmp;
}
int myStackTop(MyStack* obj) {
     assert(!myStackEmpty(obj));
    Queue * empty=&obj->q1;
    Queue * nonempty=&obj->q2;
    if(!QueueEmpty(empty))
    {
        empty=&obj->q2;
        nonempty=&obj->q1;
    }
    return QueueBack(nonempty);
}
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}


三、用栈实现队列

225. 用栈实现队列（题目链接）


思路： 栈是后进先出，队列是先进先出。

1）入队列：s1栈用来在栈顶入数据；

2）出队列：s2栈用来出栈顶数据，如果s2为空，则从s1出数据入到s2中去（比如;s1中的数据为1，2，3，入到s2变为3，2，1），再出s2的栈顶数据，这样就满足队列的性质了


4c1eac12736a4b68ed47959a8a342a6a_ba22b98897cd475e836599a71ecf2665.png

typedef int  SDateType;
typedef struct Stack
{
  SDateType* a;
  int top;
  int capacity;
}Stack;
//初始化栈和销毁栈
void InitStack(Stack* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void DestoryStack(Stack* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
//出栈和入栈
void StackPush(Stack* ps, SDateType x)
{
  assert(ps);
  //扩容
  if (ps->top == ps->capacity)
  {
    int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    SDateType* tmp = (SDateType*)realloc( ps->a,newcapacity * sizeof(SDateType));
    if (tmp == NULL)
    {
      perror("realloc fail:");
      return;
    }
    ps->a = tmp;
    ps->capacity = newcapacity;
  }
  //尾插
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);//只少有一个元素，才能删除
  ps->top--;
}
//栈的有效个数和栈顶元素
int  StackSize(Stack* ps)
{
  assert(ps);
  return ps->top;
}
int   StackTop(Stack* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
//栈是否为空
bool StackEmpty(Stack* ps)
{
  assert(ps);
  return ps->top == 0;
}
typedef struct {
    Stack s1;
    Stack s2;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue* )malloc(sizeof(MyQueue));
    InitStack(&obj->s1);
    InitStack(&obj->s2);
    return obj;
}
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->s1,x);
}
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->s1)&&StackEmpty(&obj->s2);
}
int myQueuePop(MyQueue* obj) {
    assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->s2))
    {
       while(!StackEmpty(&obj->s1))
       {
          int tmp= StackTop(&obj->s1);
          StackPush(&obj->s2,tmp);
          StackPop(&obj->s1);
       }
    }
     int tmp= StackTop(&obj->s2);
       StackPop(&obj->s2);
       return tmp;
}
int myQueuePeek(MyQueue* obj) {
     assert(!myQueueEmpty(obj));
    if(StackEmpty(&obj->s2))
    {
       while(!StackEmpty(&obj->s1))
       {
          int tmp= StackTop(&obj->s1);
          StackPush(&obj->s2,tmp);
          StackPop(&obj->s1);
       }
    }
    return StackTop(&obj->s2);
}
void myQueueFree(MyQueue* obj) {
   DestoryStack(&obj->s1);
   DestoryStack(&obj->s2);
   free(obj);
}


四、设计循环队列

622.设计循环队列（题目链接）


思路一：数组

以front为队列头下标，tail为队列尾下一个元素下标，一共k个数据，开辟k+1个整型大小空间，方便区分队列为空、为满以及一个元素的情况


1）队列为空，front=tail


2）队列为1个元素，front+1=tail


3)   队列为满，（tail+1)%(k+1)==front


3b9517fb88613c7ba621218b966ce9f8_3656bfcee96442b2b171ac2c861f3276.png

3b9517fb88613c7ba621218b966ce9f8_3656bfcee96442b2b171ac2c861f3276.png

typedef struct {
    int *a;
    int front;
    int rear;
    int n;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    int * tmp=(int *)malloc(sizeof(int)*(k+1));
    obj->a=tmp;
    obj->front=0;
    obj->rear=0;
    obj->n=k;
    return obj;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if((obj->rear+1)%(obj->n+1)==obj->front)
    {
        return true;
    }
    return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull( obj))
    {
        return false;
    }
    obj->a[obj->rear]=value;
    obj->rear++;
    obj->rear=obj->rear%(obj->n+1);
    return true;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
    {
        return true;
    }
    return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return false;
    }
    obj->front++;
    obj->front=obj->front%(obj->n+1);
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return obj->a[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return  obj->a[(obj->rear-1+obj->n+1)%(obj->n+1)];
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
}

思路二：单向循环链表

以head为队列头节点，tail为队列尾尾节点的下一个节点，一共k个数据，开辟k+1个节点的循环单向链表，方便区分队列为空、为满以及一个元素的情况


1）队列为空，head=tail


2）队列为1个元素，head->next=tail


3)   队列为满，tail->next=head


6636aa1f6ad336907c2fc5fe24745a51_1ca28be57df748c2a9fe98e1f17186e0.pngdb5a56317c4593aaf9dc4605ab6e26e1_e6d5beffcd08411ea89067ba1a777abb.png

typedef struct QueueNode
{
  int val;
  struct QueueNode * next;
}QueueNode;
QueueNode* BuyNode(int x)
{
    QueueNode* node=(QueueNode*)malloc(sizeof(QueueNode));
    node->val=x;
    node->next=NULL;
    return node;
}
typedef struct MyCircularQueue{
   QueueNode *head;
  QueueNode *tail;
    QueueNode * pretail;
  int n;
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    QueueNode* node=BuyNode(0);
    obj->pretail=NULL;
    obj->head=obj->tail=node;
    obj->n=(k+1);
    QueueNode* cur=obj->tail;
    while(k--)
    {
       QueueNode* node=BuyNode(0);
      cur->next=node;
        cur= cur->next;
    }
   cur->next=obj->head;
    return obj;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    if(obj->tail->next==obj->head)
    {
        return true;
    }
    return false;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull( obj))
    {
        return false;
    }
    obj->tail->val=value;
    obj->pretail=obj->tail;
    obj->tail=obj->tail->next;
    return true;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    if(obj->head==obj->tail)
    {
        return true;
    }
    return false;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return false;
    }
    obj->head=obj->head->next;
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return obj->head->val;
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty( obj))
    {
        return -1;
    }
    return  obj->pretail->val;
}
void myCircularQueueFree(MyCircularQueue* obj) {
   while(obj->n--)
   {
       QueueNode*next=obj->head->next;
       free(obj->head);
       obj->head=next;
   }
   obj->head=NULL;
    free(obj);
}
关键词：
LeetCode栈
LeetCode热题
LeetCode队列
LeetCode栈队列
LeetCode栈与队列
日刷百题
目录
相关文章
日刷百题
|
6天前
LeetCode 热题100——单调栈
LeetCode 热题100——单调栈
日刷百题
20 0
GR鲸鱼
|
1天前
|
机器学习/深度学习 存储 算法
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)（下）
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)
GR鲸鱼
4 0
GR鲸鱼
|
1天前
|
算法 前端开发 C语言
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)（上）
数据结构与算法⑨(第三章_下)队列的概念和实现(力扣：225+232+622)
GR鲸鱼
11 0
GR鲸鱼
|
1天前
|
缓存 算法 C语言
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣：20. 有效的括号)
GR鲸鱼
4 0
Hacynn
|
6天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题
【LeetCode力扣】单调栈解决Next Greater Number（下一个更大值）问题
Hacynn
6 0
认真学习的小雅兰.
|
6天前
|
C语言
Leetcode每日一题——“用栈实现队列”
Leetcode每日一题——“用栈实现队列”
认真学习的小雅兰.
7 0
认真学习的小雅兰.
|
6天前
|
C语言
Leetcode每日一题——“用队列实现栈”
Leetcode每日一题——“用队列实现栈”
认真学习的小雅兰.
21 0
起飞的风筝
|
6天前
|
存储 算法
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
起飞的风筝
28 0
起飞的风筝
|
6天前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
起飞的风筝
24 0
起飞的风筝
|
6天前
《LeetCode 热题 HOT 100》—— 两数相加
《LeetCode 热题 HOT 100》—— 两数相加
起飞的风筝
16 0

热门文章

最新文章

  • 1
    代码随想录算法训练营第五十六天 | LeetCode 647. 回文子串、516. 最长回文子序列、动态规划总结
  • 2
    标准库中的string类（中）+仅仅反转字母+字符串中的第一个唯一字符+字符串相加——“C++”“Leetcode每日一题”
  • 3
    [leetcode～数位动态规划] 2719. 统计整数数目 hard
  • 4
    刷题之Leetcode206题(超级详细)
  • 5
    代码随想录算法训练营第六十天 | LeetCode 84. 柱状图中最大的矩形
  • 6
    [leetcode~dfs]1261. 在受污染的二叉树中查找元素
  • 7
    代码随想录算法训练营第五十七天 | LeetCode 739. 每日温度、496. 下一个更大元素 I
  • 8
    二叉树（中）+Leetcode每日一题——“数据结构与算法”“剑指Offer55-I. 二叉树的深度”“100.相同的树”“965.单值二叉树”
  • 9
    [leetcode] 快乐数 E
  • 10
    【leetcode】剑指 Offer II 105. 岛屿的最大面积-【深度优先DFS】
  • 1
    《LeetCode》—— 买卖股票的最佳时机
    21
  • 2
    《LeetCode》—— 摆动序列
    25
  • 3
    《LeetCode》—— LeetCode刷题日记
    30
  • 4
    《LeetCode》—— 哈希
    21
  • 5
    《LeetCode》——LeetCode刷题日记3
    21
  • 6
    《LeetCode》——LeetCode刷题日记2
    16
  • 7
    《LeetCode》——LeetCode刷题日记1
    32
  • 8
    《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
    28
  • 9
    《 LeetCode 热题 HOT 100》——无重复字符的最长子串
    24
  • 10
    《LeetCode 热题 HOT 100》—— 两数相加
    16

    • 相关电子书

    更多
  • 超全算法笔试 模拟题精解合集
  • 超全算法笔试-模拟题精解合集
  • 图解算法小抄
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考