AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

（C语言版）力扣（LeetCode）栈和队列面试题

2023-07-24 94
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

8b1fb049de17442abac3541034538f02.png


20. 有效的括号


题目


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


有效字符串需满足：


左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。


题目链接：有效的括号


解法一：建立栈解决


代码如下：


typedef char STDataType;
typedef struct Stack
{
  STDataType* a;
  int top;
  int capacity;
}ST;
void StackInit(ST* ps)
{
  assert(ps);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->capacity = ps->top = 0;
}
void StackPush(ST* ps, STDataType x)
{
  assert(ps);
  if (ps->top == ps->capacity)
  {
    int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    STDataType* tmp = realloc(ps->a, sizeof(STDataType)*newCapacity);
    if (tmp == NULL)
    {
      printf("realloc fail\n");
      exit(-1);
    }
    ps->a = tmp;
    ps->capacity = newCapacity;
  }
  ps->a[ps->top] = x;
  ps->top++;
}
void StackPop(ST* ps)
{
  assert(ps);
  ps->top--;
}
STDataType StackTop(ST* ps)
{
  assert(ps);
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
bool StackEmpty(ST* ps)
{
  assert(ps);
  return ps->top == 0;
}
bool isValid(char * s){
    ST st;
    StackInit(&st);
    while(*s)
    {
        if(*s == '('
        || *s == '{'
        || *s == '[')
        {
            StackPush(&st,*s);
            ++s;
        }
        else
        {
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            STDataType top = StackTop(&st);
            StackPop(&st);
            if((*s == '}') && top != '{'
            || (*s == ']') && top != '['
            || (*s == ')') && top != '(')
            {
                StackDestroy(&st);
                return false;
            }
            else
            {
                ++s;
            }
        }
    }
    bool ret=StackEmpty(&st);
    StackDestroy(&st);
    return ret;
}


在C语言中，因为没有现成的栈可以调用，所以这里首先我们建立一个栈结构及各种操作函数建立，以便于这里的函数实现进行调用，这里我们首先建立一个栈st，初始化栈st，第一层while循环判定数组中有没有元素，进入循环后如果首元素为左括号入栈，并将指针位置后移一位，再看else语句，如果栈为空，说明上一段条件语句没执行，直接返回false，不执行这句，说明栈中有元素，则先将栈顶值记录，再删除栈顶元素，再进行括号匹配，如果s此时指向的是右括号并且top不等于左括号，说明不匹配，等于就将指针位置后移再进行匹配，最后遍历完，如果栈为空，则都匹配，否则就不匹配。这种写法代码虽然长，但是相对来说很好理解。

如下图：


03f60a898e71482ea49678fb91da243b.png


解法二：数组模拟栈解决


代码如下：


char pairs(char a)
{
    if(a==')') return '(';
    if(a=='}') return '{';
    if(a==']') return '[';
    return 0;
}
bool isValid(char * s){
    int n=strlen(s);
    if(n%2==1)
        return false;
    int stk[n],i=0,top=0;
    for(i=0;i<n;i++)
    {
        char ch=pairs(s[i]);
        if(ch)
        {
        if(top==0||stk[top-1]!=ch)
            return false;
        top--;
        }
        else
            stk[top++]=s[i];
    }
    return top==0;
}


这里我们创建一个pairs函数进行返回匹配，如果a是右括号则返回左括号，否则返回0，再看我们的主调函数，我们首先记录字符串长度，如果长度为奇数，直接返回false，如果没进入条件语句，则执行下面语句，首先我们建立字符串长度的数组stk，然后就是一个for循环，循环次数为字符串长度（防止最坏情况，全为左括号），首先记录第一个字符调用pairs函数进行匹配，如果是左括号，返回0；进入else语句，stk首元素记录第一个字符，top+1，再进行第二次循环，如果为右括号，则ch记录为左括号，进行匹配，如果相同，top-1，不相同则直接返回false，循环结束，如果top等于0，则返回ture，否则为false，其实这种写法原理和上面是一样的，只不过编写形式不一样。

如下图：


3659174bfe9d472c90bdf1b87a28204f.png


225. 用队列实现栈


题目


请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。


实现 MyStack 类：


void push(int x) 将元素 x 压入栈顶。

int pop() 移除并返回栈顶元素。

int top() 返回栈顶元素。

boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。


注意

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。

你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。


题目链接：用队列实现栈


解法：两个队列实现栈


代码如下：


typedef struct {
    int queue1[100];
    int queue2[100];
    int front1;
    int front2;
    int rear1;
    int rear2;
} MyStack;
MyStack* myStackCreate() {
    MyStack* stack=malloc(sizeof(MyStack));
    stack->front1=0;
    stack->front2=0;
    stack->rear1=0;
    stack->rear2=0;
    return stack;
}
void myStackPush(MyStack* obj, int x) {
    obj->queue1[(obj->rear1)++]=x;
}
int myStackPop(MyStack* obj) {
    int front1=obj->front1;
    int front2=obj->front2;
    int rear1=obj->rear1;
    int rear2=obj->rear2;
    while(rear1-front1>1)
    {
        obj->queue2[rear2++]=obj->queue1[front1++];
    }
    int top=obj->queue1[front1++];
    while(front2!=rear2)
    {
        obj->queue1[rear1++]=obj->queue2[front2++];
    }
    obj->front1=front1;
    obj->front2=front2;
    obj->rear1=rear1;
    obj->rear2=rear2;
    return top;
}
int myStackTop(MyStack* obj) {
    return obj->queue1[obj->rear1-1];
}
bool myStackEmpty(MyStack* obj) {
    return obj->queue1[obj->front1]==obj->queue2[obj->front2];
}
void myStackFree(MyStack* obj) {
    obj->front1=obj->front2=obj->rear1=obj->rear2=0;
}


具体思路如下图：


d3eb829e3554476a9edaf8c9237aea23.png


入栈


8f34c577570747e0839d1dde2e99d060.png


入栈


f537a0f867d34caf9fd3baa52df2252c.png

aebc800256d64d03bd512f4b6dccc8c6.png


27eb3c00678a48d596b012acfb33e003.png


出栈


3bd2699ae9f6425e8e19b5a3532d449c.png


232. 用栈实现队列


题目


请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：


实现 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（双端队列）来模拟一个栈，只要是标准的栈操作即可。


解法：两个栈实现队列


代码如下：


typedef struct {
    int* stk;
    int stksize;
    int stkcapacity;
}Stack;
Stack* createStack(int capacity)
{
    Stack* ret=malloc(sizeof(Stack));
    ret->stk=malloc(sizeof(int)*capacity);
    ret->stksize=0;
    ret->stkcapacity=capacity;
    return ret;
}
void stackpush(Stack* obj,int x)
{
    obj->stk[obj->stksize++]=x;
}
void stackpop(Stack* obj)
{
    obj->stksize--;
}
int stacktop(Stack* obj)
{
    return obj->stk[obj->stksize-1];
}
bool stackempty(Stack* obj)
{
    return obj->stksize==0;
}
void stackfree(Stack* obj)
{
    free(obj->stk);
}
typedef struct {
    Stack* inqueue;
    Stack* outqueue;
} MyQueue;
MyQueue* myQueueCreate() {
    MyQueue* ret=malloc(sizeof(MyQueue));
    ret->inqueue=createStack(100);
    ret->outqueue=createStack(100);
    return ret;
}
void inout(MyQueue* obj)
{
    while(!stackempty(obj->inqueue))
    {
        stackpush(obj->outqueue,stacktop(obj->inqueue));
        stackpop(obj->inqueue);
    }
}
void myQueuePush(MyQueue* obj, int x) {
    //stackpush(obj->inqueue,x);
    obj->inqueue->stk[obj->inqueue->stksize++]=x;
}
int myQueuePop(MyQueue* obj) {
    if(stackempty(obj->outqueue))
    {
        inout(obj);
    }
    int x=stacktop(obj->outqueue);
    stackpop(obj->outqueue);
    return x;
}
int myQueuePeek(MyQueue* obj) {
    if(stackempty(obj->outqueue))
    {
        inout(obj);
    }
    return stacktop(obj->outqueue);
}
bool myQueueEmpty(MyQueue* obj) {
    return (stackempty(obj->inqueue)&&stackempty(obj->outqueue));
}
void myQueueFree(MyQueue* obj) {
    stackfree(obj->inqueue);
    stackfree(obj->outqueue);
}


具体思路如下图：


dfd301f30b9c46ea9a3ffe8767bb743b.png


622. 设计循环队列


题目


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


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


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


MyCircularQueue(k): 构造器，设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空，返回 -1 。

Rear: 获取队尾元素。如果队列为空，返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。


题目链接：设计循环队列


解法一：数组


代码如下：


typedef struct {
    int front;//队首
    int rear;//队尾
    int capacity;//容量
    int* elem;//元素
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* ret=malloc(sizeof(MyCircularQueue));
    ret->capacity=k+1;
    ret->elem=malloc(sizeof(int)*ret->capacity);
    ret->front=ret->rear=0;
    return ret;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if((obj->rear+1)%obj->capacity==obj->front)
        return false;
    obj->elem[obj->rear]=value;
    obj->rear=(obj->rear+1)%obj->capacity;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
        return false;
    obj->front=(obj->front+1)%obj->capacity;
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
        return -1;
    return obj->elem[obj->front];
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if(obj->front==obj->rear)
        return -1;
    return obj->elem[(obj->rear-1+obj->capacity)%obj->capacity];
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->front==obj->rear;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return (obj->rear+1)%obj->capacity==obj->front;
}
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->elem);
    free(obj);
}


首先是队列结构体的建立，然后是队列初始化创建，和普通队列不同的是这里的capacity是给定值k+1，这里的用处在后面的函数会体现。


入队列：首先判定队尾下标+1模上容量等于队首下标，说明队列已经满了，返回false。入队为队尾值为下标，更新队尾值为+1模上容量，而不是直接++。


出队列：题目要求是直接删除，返回逻辑值，所以这里直接删除队首值对应下标元素，同样是队首值+1模上容量，实际此时并没删除，但是等到队尾值对应下标访问该位置入队列时会直接覆盖，而且此时这个位置也不是合法位置，所以不需要直接将其删除。


返回队首值：题目要求队列为空返回-1，只有队首等于队尾时，队列才为空，否则直接返回队首值对应下标元素即为队首。


返回队尾值：为空和上面一样，否则返回队尾值-1加上容量值再%上容量，很多人看不懂这句，举个例子，假设这时队列是满的，那么如果队尾值为0，减去1的话为负值，再去取余数就出现了越界，而且返回值是错的。


返回队列是否为空：返回队首队尾是否相等即可


返回队列是否已满：队尾值+1模上容量如果等于front，那就满了


讲到这你会发现容量的初始值设定非常的奇妙，它是循环队列思路的关键。


解法二：链表


代码如下：


typedef struct {
    struct ListNode *head;//队首指针
    struct ListNode *tail;//队尾指针
    int capacity;//容量
    int size;//长度
} MyCircularQueue;
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue *obj = (MyCircularQueue *)malloc(sizeof(MyCircularQueue));
    obj->capacity = k;
    obj->size = 0;
    obj->head = obj->tail = NULL;
    return obj;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (obj->size >= obj->capacity) {
        return false;
    }
    struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
    node->val = value;
    node->next = NULL;
    if (!obj->head) {
        obj->head = obj->tail = node;
    } else {
        obj->tail->next = node;
        obj->tail = node;
    }
    obj->size++;
    return true;
}
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (obj->size == 0) {
        return false;
    }
    struct ListNode *node = obj->head;
    obj->head = obj->head->next;  
    obj->size--;
    free(node);
    return true;
}
int myCircularQueueFront(MyCircularQueue* obj) {
    if (obj->size == 0) {
        return -1;
    }
    return obj->head->val;
}
int myCircularQueueRear(MyCircularQueue* obj) {
    if (obj->size == 0) {
        return -1;
    }
    return obj->tail->val;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size == 0;
}
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size == obj->capacity;
}
void myCircularQueueFree(MyCircularQueue* obj) {
    for (struct ListNode *curr = obj->head; curr;) {
        struct ListNode *node = curr;
        curr = curr->next;
        free(node);
    }
    free(obj);
}


这种写法是使用双向循环链表的写法，个人觉得这种写法比上面的要更好理解

首先是队列结构体的建立和初始化队列


入队列：如果长度等于容量队列已满，返回false，这里插入分两种情况，第一种是第一次插入时，首位指针都指向该元素结点，之后每次插入为第二种情况，一直挪动尾指针即可，插入成功，size+1，返回true


出队列：如果size为0，返回false，头指针指向下一结点，size-1，返回true


返回队首值：直接返回队首指针指向元素即为队首。


返回队尾值：直接返回队尾指针指向元素即为队尾。


返回队列是否为空：返回队首size是否为0。


返回队列是否已满：size等于capacity就满了。


结语


这里的解法代码部分来自力扣官方和作者自己的解法，作者只是进行了详细的剖析和部分改动方便大家理解和提升自己，学会多角度观察问题，解决问题。


有兴趣的小伙伴可以关注作者，如果觉得内容不错，请给个一键三连吧，蟹蟹你哟！！！

制作不易，如有不正之处敬请指出

感谢大家的来访，UU们的观看是我坚持下去的动力

在时间的催化剂下，让我们彼此都成为更优秀的人吧！！！

2f1def81008c4dd3a8e10980062886a8.png

文章标签：
C语言
存储
关键词：
C语言leetcode
LeetCode力扣
C语言力扣
LeetCode栈
LeetCode队列
爱学习的鱼佬
目录
相关文章
ephemerals__
|
1天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
28 9
可惜已不在
|
22天前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
可惜已不在
21 1
石小浪♪
|
24天前
|
C语言
数组栈的实现(C语言描述)
本文介绍了如何在C语言中使用数组来实现栈的数据结构，包括栈的创建、入栈、出栈、获取栈顶元素、检查栈是否为空、获取栈的大小以及销毁栈等操作，并提供了相应的函数实现。
石小浪♪
21 1
GuGuStudy
|
25天前
|
索引
力扣（LeetCode）数据结构练习题（3）------链表
力扣（LeetCode）数据结构练习题（3）------链表
GuGuStudy
65 0
GuGuStudy
|
25天前
力扣（LeetCode）数据结构练习题（2）
力扣（LeetCode）数据结构练习题（2）
GuGuStudy
25 0
白子寰
|
22天前
|
C语言 C++
C语言 之 内存函数
C语言 之 内存函数
白子寰
30 3
ephemerals__
|
13天前
|
存储 缓存 C语言
【c语言】简单的算术操作符、输入输出函数
本文介绍了C语言中的算术操作符、赋值操作符、单目操作符以及输入输出函数 `printf` 和 `scanf` 的基本用法。算术操作符包括加、减、乘、除和求余，其中除法和求余运算有特殊规则。赋值操作符用于给变量赋值，并支持复合赋值。单目操作符包括自增自减、正负号和强制类型转换。输入输出函数 `printf` 和 `scanf` 用于格式化输入和输出，支持多种占位符和格式控制。通过示例代码详细解释了这些操作符和函数的使用方法。
ephemerals__
30 10
c的前世今生
|
6天前
|
存储 算法 程序员
C语言：库函数
C语言的库函数是预定义的函数，用于执行常见的编程任务，如输入输出、字符串处理、数学运算等。使用库函数可以简化编程工作，提高开发效率。C标准库提供了丰富的函数，满足各种需求。
c的前世今生
13 1
ephemerals__
|
12天前
|
机器学习/深度学习 C语言
【c语言】一篇文章搞懂函数递归
本文详细介绍了函数递归的概念、思想及其限制条件，并通过求阶乘、打印整数每一位和求斐波那契数等实例，展示了递归的应用。递归的核心在于将大问题分解为小问题，但需注意递归可能导致效率低下和栈溢出的问题。文章最后总结了递归的优缺点，提醒读者在实际编程中合理使用递归。
ephemerals__
35 7
ephemerals__
|
12天前
|
存储 编译器 程序员
【c语言】函数
本文介绍了C语言中函数的基本概念，包括库函数和自定义函数的定义、使用及示例。库函数如`printf`和`scanf`，通过包含相应的头文件即可使用。自定义函数需指定返回类型、函数名、形式参数等。文中还探讨了函数的调用、形参与实参的区别、return语句的用法、函数嵌套调用、链式访问以及static关键字对变量和函数的影响，强调了static如何改变变量的生命周期和作用域，以及函数的可见性。
ephemerals__
24 4

热门文章

最新文章

  • 1
    C语言进阶之路：输入三个整数，输出最大值和最小值
  • 2
    【C语言】学习笔记4——数组
  • 3
    C语言OJ项目参考(1034) 求值
  • 4
    C# Json处理日期和Table
  • 5
    C语言取整方法详解
  • 6
    算法学习之C语言基础
  • 7
    C语言中的逗号操作符
  • 8
    c语言中常见错误总结
  • 9
    C语言连接MySQL数据库
  • 10
    《C语言及程序设计》实践参考——改造链表
  • 1
    Java的前景如何，好不好自学？，万字Java技术类校招面试题汇总
    49
  • 2
    es集群安装，邮储银行java面试
    68
  • 3
    Android 11 中的存储机制更新，面试心得体会
    83
  • 4
    真的强！借助阿里技术博主分享的Android面试笔记，我拿到了字节跳动的offer
    57
  • 5
    【redis源码学习】持久化机制，java程序员面试算法宝典pdf
    70
  • 6
    Python中return和yield的区别，面试官不讲武德
    41
  • 7
    FFmpeg流媒体调试工具(六)，软件开发项目经理面试题
    97
  • 8
    我把Spring Cloud的超详细资料介绍给你，面试官不会生气吧？geigei
    70
  • 9
    Java大文件排序（有手就能学会），kafka面试题2024
    53
  • 10
    Flutter学习笔记&学习资料推荐，15分钟的字节跳动视频面试
    88

    • 相关课程

    更多
  • 你的第一门C语言课
  • C语言学习教程
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计

    • 相关电子书

    更多
  • 阿里云技术面试红宝书
  • 超全算法笔试-模拟题精解合集
  • 程序员面试宝典
    • 下一篇
    阿里云无影云电脑免费试用，最长可试用3个月