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

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

2023-11-22 46
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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栈与队列
日刷百题
目录
相关文章
码农阿豪
|
4月前
|
存储 算法 测试技术
力扣经典150题第五十四题：最小栈
力扣经典150题第五十四题：最小栈
码农阿豪
35 0
nsu_xxy
|
5月前
|
存储 算法 索引
力扣每日一题 6/24 模拟 数组 单调栈
力扣每日一题 6/24 模拟 数组 单调栈
nsu_xxy
33 0
Codelinghu
|
1月前
【LeetCode 24】225.用队列实现栈
【LeetCode 24】225.用队列实现栈
Codelinghu
10 0
Codelinghu
|
1月前
|
算法
【LeetCode 23】232.用栈实现队列
【LeetCode 23】232.用栈实现队列
Codelinghu
18 0
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码，确保min、push和pop操作的时间复杂度为O(1)。
BetterBench
27 4
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】946. 验证栈序列
LeetCode题目“946. 验证栈序列”的Python解决方案，通过模拟栈的压入和弹出操作来验证给定的两个序列是否能通过合法的栈操作得到。
BetterBench
29 6
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】剑指 Offer 09. 用两个栈实现队列
使用两个栈实现队列的Python解决方案，包括初始化两个栈、实现在队列尾部添加整数的appendTail方法和在队列头部删除整数的deleteHead方法，以及相应的示例操作。
BetterBench
39 2
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】641.循环双端队列
文章介绍了如何实现一个循环双端队列，包括其操作如插入、删除、获取队首和队尾元素，以及检查队列是否为空或已满，并提供了Python语言的实现代码。
BetterBench
22 0
BetterBench
|
3月前
|
Python
【Leetcode刷题Python】232. 用栈实现队列
如何使用Python语言通过两个栈来实现队列的所有基本操作，包括入队(push)、出队(pop)、查看队首元素(peek)和判断队列是否为空(empty)，并提供了相应的代码实现。
BetterBench
20 0
一只大鸽子
|
5月前
|
存储 算法 Python
二刷力扣--栈和队列
二刷力扣--栈和队列
一只大鸽子
35 1