栈和队列OJ题

简介: 栈和队列OJ题



今天接着栈&队列OJ题目。

【1】括号匹配问题

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

有效字符串需满足:

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

思路分析

  • 左括号入栈
  • 右括号与栈顶元素匹配(记得Pop)(顺序匹配)
  • 考虑左/右括号多了(数量匹配)

易错总结

  • 同一个域不能存在同名变量
  • 类型的匹配度100%
  • 字符串的比较用strcmp 字符比较==即可(字符的比较都是ASCII码)
  • 出栈的性质:必须出了栈顶元素才能访问下一个元素
  • 括号的匹配不是==
*s == ')'&& top != '(' ||  *s == '}'&& top != '{'||   *s == ']'&& top != '['
  • return 之前都必须free ,不然会造成内存泄露的问题!!非常严重 先销毁再返回!!

Stack.h&Stack.c手撕栈

//stack.h
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef char STDatatype;
typedef struct Stack
{
  STDatatype* a;
  int top;
  int capacity;
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst, STDatatype x);
void STPop(ST* pst);
STDatatype STTop(ST* pst);
bool STempty(ST* pst);
int STSize(ST* pst);
//stack.c
void STInit(ST* pst)
{
  assert(pst);
  pst->a = 0;
  pst->top = 0;
  pst->capacity = 0;
}
void Createcapacity(ST* pst)
{
  if (pst->top == pst->capacity)
  {
    int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
    STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(ST) * newcapacity);
    if (tmp == NULL)
    {
      perror("realloc fail");
      return;
    }
    pst->a = tmp;
    pst->capacity = newcapacity;
  }
}
void STPush(ST* pst, STDatatype x)
{
  assert(pst);
  Createcapacity(pst);
  pst->a[pst->top] = x;
  pst->top++;
}
void STPop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  pst->top--;
}
STDatatype STTop(ST* pst)
{
  assert(pst);
  assert(pst->top > 0);
  return pst->a[pst->top-1];
}
bool STempty(ST* pst)
{
  assert(pst);
  return pst->top == 0;
}
int STSize(ST* pst)
{
  assert(pst);
  return pst->top;
}
void STDestroy(ST* pst)
{
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = 0;
  pst->capacity = 0;
}

isValid括号匹配

bool isValid(char* s) {
    ST stack;
    STInit(&stack);
    //遍历字符串
    while(*s)
    {
        //左括号入栈
        if(*s == '(' ||
        *s == '{' ||
        *s == '[' )
        {
            STPush(&stack,*s);
        }
        else//右括号
        {
            //数量匹配 左括号<右括号
      if(STempty(&stack))
      {
         STDestroy(&stack);
         return false;
      }
            
            //右括号取栈顶的元素比较
            //记住要Pop
            char top=STTop(&stack);
            STPop(&stack);
            //因为true 不是一次匹配成功  flase是依次成功
            if( *s == ')'&& top != '(' ||
            *s == '}'&& top != '{'||
            *s == ']'&& top != '[' )
            {
          STDestroy(&stack);
                return false;
            }
        }
        s++;
    }
    //数量匹配,左括号>右括号
  STDestroy(&stack);
    return STempty(&stack);
}

【2】设计循环队列

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满

//用数组实现+多开辟一个空间不放元素
typedef struct {
    int*a;
    int front;
    int back;//数组下标
    int k;//循环队列的最多放置数据
} 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->back=0;//指向最后一个元素的下一个
    obj->k=k;
    return obj;
}
//判断循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front == obj->back;//==0 
}
//判断是否为满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->back+1) % (obj->k+1) == obj->front;//back+1=front
    //操作符优先级问题
}
//插入元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))//true 满了
    {
        return false;
    }
        obj->a[obj->back] = value;
        obj->back++;
        obj->back %= obj->k+1;//处理
        //obj->front+1%=obj->k+1;//处理左边不能为计算表达式
       return true;
}
//删除元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
    }
    else
    {
        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->back-1+obj->k+1)%(obj->k+1)];
    return obj->a[(obj->back+obj->k)%(obj->k+1)];
}
//释放空间
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->a);
    free(obj);
    obj=NULL;
}
/**
 * Your MyCircularQueue struct will be instantiated and called as such:
 * MyCircularQueue* obj = myCircularQueueCreate(k);
 * bool param_1 = myCircularQueueEnQueue(obj, value);
 
 * bool param_2 = myCircularQueueDeQueue(obj);
 
 * int param_3 = myCircularQueueFront(obj);
 
 * int param_4 = myCircularQueueRear(obj);
 
 * bool param_5 = myCircularQueueIsEmpty(obj);
 
 * bool param_6 = myCircularQueueIsFull(obj);
 
 * myCircularQueueFree(obj);
*/

这个是用数组实现【循环队列】&后面博文会详细讲解。

  • 数组实现【循环队列】
  • 单链表实现【循环队列】
  • 双向链表实现【循环队列】

✔✔✔✔✔最后,感谢大家的阅读,若有错误和不足,欢迎指正!之后可能到1月分才会频繁继续更新博文了,要去准备英语和西语的考试,大家要乖乖敲代码哦!

目录
相关文章
|
9天前
|
消息中间件 存储 搜索推荐
深入理解栈和队列(二):队列
深入理解栈和队列(二):队列
27 0
【队列】数据结构队列的实现
【队列】数据结构队列的实现
|
1月前
【栈】数据结构栈的实现
【栈】数据结构栈的实现
|
10天前
|
存储 算法 索引
【算法与数据结构】队列的实现详解
【算法与数据结构】队列的实现详解
|
14天前
|
算法 C语言
【算法与数据结构】 C语言实现单链表队列详解2
【算法与数据结构】 C语言实现单链表队列详解
|
14天前
|
存储 算法 C语言
【算法与数据结构】 C语言实现单链表队列详解1
【算法与数据结构】 C语言实现单链表队列详解
|
18天前
|
存储
【数据结构】什么是栈?
【数据结构】什么是栈?
24 0
【数据结构】什么是栈?
|
22天前
|
存储 设计模式 算法
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
【C/C++ 数据结构 线性表】深入理解与实现栈:从基础到应用的全面探索
52 0
|
1月前
|
存储
数据结构--栈和队列
数据结构--栈和队列
|
1月前
|
存储 算法 数据处理
数据结构从入门到精通——栈
栈,作为一种后进先出(LIFO)的数据结构,在计算机科学中扮演着重要的角色。它的特性使得它在处理函数调用、括号匹配、表达式求值等问题时具有得天独厚的优势。然而,如果我们跳出传统思维的束缚,会发现栈的用途远不止于此。
49 0

热门文章

最新文章