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

栈和队列题目练习

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

本节小编选了两道题来加深对栈和队列的认识理解！

有效的括号

方法1：直接用栈的结构（动态数组）

本题可以用栈这个结构来解答，将'(','{','['  左括号压入栈中，然后取出栈顶元素与右括号')','}',']'匹配。不匹配的话，返回false,我们同时也要考虑空集的情况，即栈中元素为空，则返回false。

因为本题使用c语言写的，所以需要手撕栈的结构，可以运用上篇博客所写的栈的代码。

typedef  char  datatype;
typedef struct stack {
  datatype* a;
  int top;//栈顶
  int capacity;
}ST;
void STInit(ST* pst){
  assert(pst);
  pst->a = NULL;
  //top指向栈顶数据的下一个位置,可以理解为下标
  pst->top = 0;
  pst->capacity = 0;
}
void STDestory(ST* pst) {
  assert(pst);
  free(pst->a);
  pst->a = NULL;
  pst->top = pst->capacity = 0;
}
//容量检查
void Checkcapacity(ST* pst) {
  assert(pst);
  if (pst->top == pst->capacity) {
    int newcapacity = pst->capacity==0?4:pst->capacity * 2;
    datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype));
    if (temp == NULL) {
      perror("relloc fail");
      return;
    }
    pst->a = temp;
    pst->capacity = newcapacity;
  }
}
//入栈和出栈
void STPush(ST* pst, datatype x) {
  assert(pst);
  Checkcapacity(pst);
  pst->a[pst->top] = x;
  pst->top++;
}
void STPop(ST* pst) {
  assert(pst);
  assert(pst->top>0);
  pst->top--;
}
//获取栈顶数据
datatype 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;
}
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;
        //STPop(&st);
    }
    }
    s++;
    }
//看最后是否栈为空，探讨左右括号数量不匹配的情况。
   bool ret=(STEmpty(&st));
     STDestory(&st);
     return ret;
}

方法2：通过数组模拟栈来实现

使用一个字符数组作为栈，通过使用top标记栈顶的位置来实现栈的操作。在遍历字符串的过程中，遇到左括号就将其压入栈中，遇到右括号就与栈顶元素进行匹配。如果匹配成功，则将栈顶元素出栈，否则返回false。最后，如果栈为空，则说明所有的括号都匹配成功，返回true；否则，返回false。

bool isValid(char* s) {
    char stack[10000];
    int top = -1;
    int len = strlen(s);
    for (int i = 0; i < len; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            stack[++top] = s[i];
        } else {
            if (top == -1) {
                return false;
            }
            
            if ((s[i] == ')' && stack[top] == '(') || 
                (s[i] == '}' && stack[top] == '{') || 
                (s[i] == ']' && stack[top] == '[')) {
                top--;
            } else {
                return false;
            }
        }
    }
    
    return top == -1;
}

设计循环队列

方法1:使用动态数组

通过画图发现，当head==tail时，既是队列为空的条件，也是队列满的条件，所以我们可以通过增加一个空间来辅助判满，当tail+1=head时。还有另外一个方法，通过定义size变量，当size大小等于k时，也是队列满的时候。

在后续解决回绕的问题时，我们多次采用取模的方法，因为一个数除以比他大的数，取模后大小不变，当相等时，模为0，刚好回到起点处，完美的解决了回绕问题。

 
 
//循环队列先进先出
typedef struct {
    int *arr;
    int head;
    int tail;//指向尾下一个
    int k;
} MyCircularQueue;
 
//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //多开辟一个空间
  obj->arr=(int*)malloc(sizeof(int)*(k+1));
    
  obj->head=0;
    obj->tail=0;
    obj->k=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    //头尾相等时队列为空
  return (obj->head)==obj->tail;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //当tail+1=head时，为满，通过取模解决回绕问题
  return((obj->tail+1)%(obj->k+1))==obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //队列满的时候，返回false
  if(myCircularQueueIsFull(obj))
    return false;
    //插入一个数据，tail后移
  obj->arr[obj->tail]=value;
    obj->tail++;
    //解决回绕，重头再来
    obj->tail %=(obj->k+1);
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    //head前进，删除数据
  obj->head++;
  //解决回绕问题
    obj->head %=(obj->k+1);
    return true;
}
 
int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    return obj->arr[obj->head];
}
 
int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return -1;
    else
    //分类讨论取尾元素
    return obj->tail==0?obj->arr[obj->k]:obj->arr[obj->tail-1];
    //return obj->arr[(obj->tail-1+obj->k+1)%(obj->k+1)];//取模的方法很巧妙
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
}

方法2：双向链表实现

使用双向链表实现，其中每个节点（Node）包含一个整数值（val），以及指向前一个节点和后一个节点的指针（prev和next）。循环队列（MyCircularQueue）包含一个指向队列头部和尾部的指针（head和tail），以及队列的大小（size）和容量（capacity）。

//节点建立
typedef struct Node {
    int val;
    struct Node* prev;
    struct Node* next;
} Node;
//双向链表实现队列
typedef struct {
    Node* head;
    Node* tail;
    int size;
    int capacity;
} MyCircularQueue;
 
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->head = NULL;
    obj->tail = NULL;
    obj->size = 0;
    obj->capacity = k;
    return obj;
}
//判空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->size == 0;
}
//判满
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size == obj->capacity;
}
//插入数据
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if (myCircularQueueIsFull(obj)) {
        return false;
    }
 
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = value;
    newNode->prev = NULL;
    newNode->next = NULL;
 //队列为空时
    if (myCircularQueueIsEmpty(obj)) {
        obj->head = newNode;
        obj->tail = newNode;
        newNode->next = newNode;
        newNode->prev = newNode;
    } 
  // 不为空时
 
else {
        newNode->prev = obj->tail;
        newNode->next = obj->head;
        obj->tail->next = newNode;
        obj->head->prev = newNode;
        obj->tail = newNode;
    }
    obj->size++;
    return true;
}
//数据的删除
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if (myCircularQueueIsEmpty(obj)) {
        return false;
    }
 
    Node* del = obj->head;
    if (obj->size == 1) {
        obj->head = NULL;
        obj->tail = NULL;
    } else {
        obj->head = obj->head->next;
        obj->head->prev = obj->tail;
        obj->tail->next = obj->head;
    }
 
    obj->size--;
    free(del);
    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->tail->val;
}
//队列销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    Node* curr = obj->head;
    while (curr != obj->tail) {
        Node* next = curr->next;
        free(curr);
        curr = next;
    }
    obj->tail=NULL;
 
    free(obj);
}

补充方法3：

使用链表（单链表）-投机取巧哈哈哈

不过这种方法没有关系到循环队列，也能通过该题目。

可以用链表实现队列，用链表实现队列则较为简单，因为链表可以在 O(1)时间复杂度完成插入与删除。入队列时，将新的元素插入到链表的尾部；出队列时，将链表的头节点返回，并将头节点指向下一个节点。

循环队列的属性如下:

head：链表的头节点，队列的头节点。

tail：链表的尾节点，队列的尾节点。

capacity：队列的容量，即队列可以存储的最大元素数量。

size：队列当前的元素的数量。

相比较与数组，我们使用了size的方法来判断队列为空为满的状态，

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
//中间节点创建和函数主体
typedef struct node {
    int val;
    struct node* next;
} node;
//循环队列先进先出
typedef struct {
    node* head;
    node* tail;
    int size;
    int capacity;
} MyCircularQueue;
 
//创建循环队列
MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->head=obj->tail=NULL;
    obj->size=0;
    obj->capacity=k;
    return obj;
}
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
   if(obj->size==0)
   return true;
   else
   return false;
//return obj->size==0;
}
 
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    return obj->size==obj->capacity;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    if(myCircularQueueIsFull(obj))
    return false;
    node* newnode=(struct node*)malloc(sizeof(node));
    newnode->val=value;
    newnode->next=NULL;
    if(obj->size==0)
    {
        obj->head=newnode;
        obj->tail=newnode;
    }
    else{
    obj->tail->next=newnode;
    obj->tail=newnode;
    }
    obj->size++;
    return true;
}
 
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj))
    return false;
    node*del=obj->head;
    obj->head=obj->head->next;
    free(del);
    obj->size--;
    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->tail->val;
}
 
void myCircularQueueFree(MyCircularQueue* obj) {
    node* curr = obj->head;
    while (curr != NULL) {
        node* next = curr->next;
        free(curr);
        curr = next;
    }
    
    obj->size = obj->capacity = 0;
    obj->head = obj->tail = NULL;
    free(obj);
}
 
//手动测试部分
int main() {
    MyCircularQueue* obj = myCircularQueueCreate(5);
    myCircularQueueEnQueue(obj, 1);
    myCircularQueueEnQueue(obj, 2);
    myCircularQueueEnQueue(obj, 3);
    myCircularQueueEnQueue(obj, 4);
    myCircularQueueEnQueue(obj, 5);
    printf("%d\n", myCircularQueueRear(obj));
    printf("%d\n", myCircularQueueFront(obj));
    myCircularQueueDeQueue(obj);
    printf("%d\n", myCircularQueueFront(obj));
    myCircularQueueFree(obj);
    return 0;
}

OK，本节内容到此结束，各位友友留下三连和评论吧，有更好的方法希望各位佬私信交流！！！

文章标签：
C语言
存储
关键词：
栈数据结构
栈题目数据结构
队列题目数据结构
题目数据结构
队列数据结构
禁默
目录
相关文章
那年春天
|
1月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
32 1
龙大吉
|
23天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
44 5
德国都芳最好
|
1月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构，在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈，可以有效地解决许多与数据存储和操作相关的问题。
德国都芳最好
83 21
html的七十二变
|
1月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
33 2
dufadayang
|
1月前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息？
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息，操作系统能够实现用户模式和内核模式之间的无缝切换，为用户程序提供稳定、可靠的系统服务。
dufadayang
51 4
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
48 0
ephemerals__
|
1月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
178 9
java冯坚持
|
2月前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
47 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
肾透侧视攻城狮
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总（10）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
25 1
禁默
|
2月前
初步认识栈和队列
初步认识栈和队列
禁默
64 10