数据结构-栈和队列力扣题

简介: 数据结构-栈和队列力扣题

有效的括号

题目链接:力扣(LeetCode)

思路:这道题可以用栈来解决,先让字符串中的左括号' ( ',' [ ',' { '入栈,s指向字符串下一个字符,如果该字符也是左括号,那就继续入栈,如果是右括号,那就让其与栈顶元素相匹配(每次都要弹出栈顶元素),匹配上了,继续循环,匹配不上就返回false,注意在每次返回false之前都要销毁栈。

还要考虑极端情况,如果全是左括号,我们要在代码最后进行判空,不为空,返回false,同时,这次判空也能解决前面几对都匹配上,只有最后一个左括号没匹配上的问题(例如:"()[]{}{")。

如果全是右括号,说明整个过程中没有入栈元素,此时判空,如果为空返回false,同时,这次判空也能解决前面几对都匹配上,只有最后一个右括号没匹配上的问题(例如:"()[]{}}")。

如果用C语言来解题的话,栈需要自己写。

代码如下:

typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;
  int capacity;
}ST;
//初始化栈
void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDatatype x)
{
  //开辟空间
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
  //插入
  pst->a[pst->top] = x;
  pst->top++;
}
//判空函数
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
//出栈
void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;
}
//获取栈顶元素
STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top - 1];
}
//获取栈中有效数据的个数
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
//销毁栈
void STDestory(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}
bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
        if(*s=='('||*s=='['||*s=='{')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
      {
         STDestory(&st);
               return false;
      }
      char top=STTop(&st);
      STPop(&st);
            if((top!='('&&*s==')')
              ||(top!='['&&*s==']')
              ||(top!='{'&&*s=='}'))
            {
                STDestory(&st);
                return false;
            }
        }
         ++s;
    }
  bool ret=STEmpty(&st);
  STDestory(&st);
    return ret;
}

用队列实现栈

题目链接:力扣(LeetCode)

思路:队列是先入先出,栈是先入后出,要用队列实现栈,我们可以定义两个栈q1和q2,当它们都为空时,随便选一个存入数据,假设q1中有数据1 2 3 4,我们可以把q1中的1 2 3 push进q2中,然后把q1中的4pop出去,接着把q2中的1 2 push进q1,然后把q2中的3pop出去,这样循环在q1和q2中倒数据,就实现了4 3 2 1依次出栈,即先入后出。

当我们在出栈的同时,想要入栈,就把数据push进有数据的队列即可。

想要用C语言做这道题,队列的实现代码也要自己写。

注意,我们下列代码是结构体的三层嵌套,所以销毁时要先销毁q1和q2,再销毁obj,如果只销毁obj,由于我们的队列q1和q2中分别有两个头尾指针还有节点,会造成内存泄漏的问题。

它们的关系图如下:

代码如下:

typedef int QDatatype;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDatatype data;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;
//初始化队列
void QueueInit(Queue* pq)
{
  pq->phead = NULL;
  pq->ptail = NULL;
  pq->size = 0;
}
//队尾入队列
void QueuePush(Queue* pq, QDatatype x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->data = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
    assert(pq->phead == NULL);
    pq->phead = pq->ptail=newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
//判空函数
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->size ==0 ;
}
//队头出队列
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  //一个节点
  //多个节点
  if (pq->phead->next == NULL)
  {
    free(pq->phead);
    pq->phead = pq->ptail= NULL;
  }
  else
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->size--;
}
//获取队列头部元素
QDatatype QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->phead->data;
}
//获取队列尾部元素
QDatatype QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->ptail->data;
}
//获取队列中有效元素个数
int Queuesize(Queue* pq)
{
  assert(pq);
  return pq->size;
}
//销毁队列
void DestoryQueue(Queue* pq)
{
  assert(pq);
  while (pq->phead)
  {
    QNode* next = pq->phead->next;
    free(pq->phead);
    pq->phead = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* obj=(MyStack*)malloc(sizeof(MyStack));
    if(obj==NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    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);
    }
}
int myStackPop(MyStack* obj) {
    Queue* pemptyq=&obj->q1;
    Queue* pnoemptyq=&obj->q2;
    if(!QueueEmpty(&obj->q1))
    {
        pemptyq=&obj->q2;
        pnoemptyq=&obj->q1;
    }
    while(Queuesize(pnoemptyq)>1)
    {
        QueuePush(pemptyq,QueueFront(pnoemptyq));
    QueuePop(pnoemptyq);
    }
    int top=QueueFront(pnoemptyq);
    QueuePop(pnoemptyq);
    return top;
}
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1))
        return QueueBack(&obj->q1);
  else
    return QueueBack(&obj->q2);
}
bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2);
}
void myStackFree(MyStack* obj) {
    DestoryQueue(&obj->q1);
  DestoryQueue(&obj->q2);
    free(obj);
}

用栈实现队列

题目链接:力扣(LeetCode)

思路:这道题用上道题的思路也能实现,但是过于复杂。

简单思路:我们定义两个栈pushstpopst,栈中数据遵循先入后出的原则,如果在pushstpush进去1 2 3 4,那他从栈顶到栈底依次是 4 3 2 1 ,但是如果我们把pushst中的数据再pushpopst中,那popst中从栈顶到栈底依次是 1 2 3 4,此时我们只要将popst中的数据按照栈本身先入后出的原则pop出去,就是1 2 3 4,这样就实现了先入先出。如下图:

当我们在出队列的同时,想要入队列,要先等popst中的数据出完才行,所以当popst为空,pushst不为空时,才能把pushst中的数据往popstpush

代码如下:

typedef int STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;
  int capacity;
}ST;
//初始化栈
void STInit(ST* pst)
{
  assert(pst);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}
//入栈
void STPush(ST* pst, STDatatype x)
{
  //开辟空间
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
  //插入
  pst->a[pst->top] = x;
  pst->top++;
}
//判空函数
bool STEmpty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
//出栈
void STPop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  pst->top--;
}
//获取栈顶元素
STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(!STEmpty(pst));
  return pst->a[pst->top - 1];
}
//获取栈中有效数据的个数
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
//销毁栈
void STDestory(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}
typedef struct {
    ST pushst;
    ST popst;
} MyQueue;
MyQueue* myQueueCreate() {
    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) {
        STPush(&obj->pushst,x);
}
int myQueuePop(MyQueue* obj) {
   int front= myQueuePeek(obj);
   STPop(&obj->popst);
   return front;
}
int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->popst))
    {
        while(!STEmpty(&obj->pushst))
        {
        STPush(&obj->popst,STTop(&obj->pushst));
        STPop(&obj->pushst);
        }
    }
    return STTop(&obj->popst);
}
bool myQueueEmpty(MyQueue* obj) {
    assert(obj);
    return STEmpty(&obj->pushst)&&STEmpty(&obj->popst);
}
void myQueueFree(MyQueue* obj) {
    STDestory(&obj->pushst);
    STDestory(&obj->popst);
    free(obj);
}

设计循环队列

题目链接:力扣(LeetCode)

思路: 本题用数组队列和链表队列都能实现,在这里我们使用数组队列,首先,要设计一个循环队列,我们就要知道队列什么时候满,什么时候空,空很容易判断,当front=rear时就为空,问题是当我们循环一圈以后,队列已经满了,但此时front也等于rear,所以为了不发生混淆,我们在开辟空间时多开辟一块,假设要存7个数据就开辟8个空间:

此时当rear+1==front时就为满。但这只是上图为了形象展示,实际上在数组中,每存一个数,rear++,但是数组首尾并没有相连,不能用rear+1==front判断是否满了,我们可以用下标rear,当(rear+1)%(k+1)==front时就说明队列满了

而要在队列中插入数据,每次插入之后下标rear++,但是当队列满了之后,rear就是数组中最后一个下标,这时如果我们在队头出了两个数据,想再往队列里插数据,就要让rear回到开始的位置,所以每次rear++后,让rear=rear%(k+1),此时再插入,就形成了一个完美的循环,同理,删除数据也一样,每次删完都让front=front%(k+1)

obj->a[(obj->rear+obj->k)%(obj->k+1)]这段代码是为了返回队尾元素。

代码如下:

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

栈与队列的内容到这里就结束了,下节开始学习堆与二叉树

未完待续。。。

目录
相关文章
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
22天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
43 5
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
48 0
|
3月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
62 6
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
124 2
|
1月前
|
机器学习/深度学习 人工智能 自然语言处理
280页PDF,全方位评估OpenAI o1,Leetcode刷题准确率竟这么高
【10月更文挑战第24天】近年来,OpenAI的o1模型在大型语言模型(LLMs)中脱颖而出,展现出卓越的推理能力和知识整合能力。基于Transformer架构,o1模型采用了链式思维和强化学习等先进技术,显著提升了其在编程竞赛、医学影像报告生成、数学问题解决、自然语言推理和芯片设计等领域的表现。本文将全面评估o1模型的性能及其对AI研究和应用的潜在影响。
43 1
|
3月前
|
数据采集 负载均衡 安全
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口
本文提供了多个多线程编程问题的解决方案,包括设计有限阻塞队列、多线程网页爬虫、红绿灯路口等,每个问题都给出了至少一种实现方法,涵盖了互斥锁、条件变量、信号量等线程同步机制的使用。
LeetCode刷题 多线程编程九则 | 1188. 设计有限阻塞队列 1242. 多线程网页爬虫 1279. 红绿灯路口