当前位置： 首页 > news >正文

【数据结构入门】栈和队列的OJ题

news 2025/8/11 8:37:46

目录

1. 有效的括号

分析：

代码：

2. 用队列实现栈

分析：

代码：

3. 用栈实现队列

分析：

代码：

4. 设计循环队列

思路：

代码：

1. 有效的括号

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

有效字符串需满足：

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

示例 1：

输入：s = "()"

输出：true

示例 2：

输入：s = "()[]{}"

输出：true

示例 3：

输入：s = "(]"

输出：false

示例 4：

输入：s = "([])"

输出：true

示例 5：

输入：s = "([)]"

输出：false

分析：

        这里由于是用C语言来oj，所以需要提前写好一个栈。

        每一次循环判断当前元素是否是左括号，如果是左括号那么就入栈，如果不是左括号就判断当前元素和栈顶元素是否相同，相同就出栈，如果不相同就直接返回false；

        需要注意的一点是如果此时字符串只有一个左括号，那么循环就会压入一个栈元素，就会停止，此时还需要判断栈是否为空，如果为空，那么就返回true，不为空，说明左括号比右括号多，没有完全配对成功；那么只有一个右括号就会直接在循环内返回false。

代码：

typedef char dataType;
typedef struct Stack 
{dataType* _a; // 用数组来实现int _top;// 栈的数据的个数、栈顶元素下表int _capacity; // 栈的容量
}Stack;// 初始化
void InitStack(Stack* stk);
// 销毁
void DestroyStack(Stack* stk);
// 入栈
void PushStack(Stack* stk,dataType x);
// 出栈
void PopStack(Stack* stk);
// 栈的元素个数
int SizeStack(Stack* stk);
// 栈是否为空
int isEmpty(Stack* stk);
// 获取栈顶数据
dataType getTop(Stack* stk);
// 初始化
void InitStack(Stack* stk)
{assert(stk);stk->_a = malloc(sizeof(dataType) * 4);stk->_capacity = 4;stk->_top = 0;// 栈顶元素下标为0
}
// 销毁
void DestroyStack(Stack* stk)
{assert(stk);free(stk->_a);stk->_a = NULL;stk->_capacity = stk->_top = 0;
}
// 入栈
void PushStack(Stack* stk, dataType x)
{assert(stk);if (stk->_capacity == stk->_top) // 容量和栈元素个数相等，就扩容{stk->_capacity *= 2;dataType* tmp = (dataType*)realloc(stk->_a, sizeof(dataType) * stk->_capacity);if (tmp == NULL){printf("内存不足！");exit(-1);}else{stk->_a = tmp;}}// 正常插入stk->_a[stk->_top] = x;stk->_top++;}
// 出栈
void PopStack(Stack* stk)
{assert(stk);assert(stk->_top > 0);// 有元素才能删除stk->_top--;
}
// 栈的元素个数
int SizeStack(Stack* stk) 
{assert(stk);return stk->_top;
}
// 栈是否为空
int isEmpty(Stack* stk) 
{assert(stk);return stk->_top == 0 ? 1 : 0; // 没有元素就是空
}
// 获取栈顶数据
dataType getTop(Stack* stk) 
{ assert(stk);if (stk->_top > 0){return stk->_a[stk->_top - 1];}else {return -1;}
}bool isValid(char* s) {char* curr = s; Stack stk;InitStack(&stk);while(*curr != '\0'){if((*curr) == '[' || (*curr) == '{' || (*curr) == '(')       // 前括号{PushStack(&stk,*curr);}else{// 反括号if((*curr) == ']' && getTop(&stk) == '['){PopStack(&stk);}else if((*curr) == '}' && getTop(&stk) == '{'){PopStack(&stk);}else if((*curr) == ')' && getTop(&stk) == '('){PopStack(&stk);}else{// 匹配就出栈，不匹配返回falseDestroyStack(&stk);return false;}}curr++;}if(isEmpty(&stk)){DestroyStack(&stk);return true;}else{DestroyStack(&stk);return false;}}

2. 用队列实现栈

请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

分析：

使用两个队列即可

入栈：随便选择一个不为空的队列入队即可。

出栈：出队到只剩一个节点为止，将那个节点出队。

获取栈顶元素：获取不为空的队列的tail即可。

判空：两个队列为空，栈为空。

初始化栈：创建堆空间给栈，初始化两个队列，返回栈指针。

释放空间：由于C++没有检测内存泄露的手段，所以此模块不写oj也不会报错；如果要写的话，那么先释放队列的空间，可以使用destroy接口，释放完毕，free栈空间。

由于是c语言实现，所以需要提前实现队列。

代码：


typedef int dataType;typedef struct QueueNode {dataType data;struct QueueNode* next;
} QueueNode;typedef struct Queue {QueueNode* head;QueueNode* tail;
} Queue;void QueInit(Queue* pq);
void QueDestroy(Queue* pq);
void QuePush(Queue* pq, dataType x);
void QuePop(Queue* pq);
dataType QueFront(Queue* pq);
dataType QueBack(Queue* pq);
int isEmpty(Queue* pq);
int QueSize(Queue* pq);void QueInit(Queue* pq) {assert(pq);pq->head = pq->tail = NULL;
}void QueDestroy(Queue* pq) {assert(pq);QueueNode* curr = pq->head;while (curr) {QueueNode* next = curr->next;free(curr);curr = next;}pq->head = pq->tail = NULL;
}void QuePush(Queue* pq, dataType x) {assert(pq);QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));newNode->data = x;newNode->next = NULL;if (pq->head == NULL) // 如果队列为空，插入一个节点{pq->head = pq->tail = newNode;} else {pq->tail->next = newNode; // 队列不为空，tail插入节点pq->tail = newNode;}
}
void QuePop(Queue* pq) {assert(pq);assert(pq->head);QueueNode* next = pq->head->next;free(pq->head);pq->head = next;if (pq->head == NULL) {// tail   head == NULL，删除的过程中，删除到最后一个的时候需要将tail置空pq->tail = NULL;}
}
dataType QueFront(Queue* pq) {assert(pq);assert(pq->head);return pq->head->data;
}
dataType QueBack(Queue* pq) {assert(pq);assert(pq->tail);return pq->tail->data;
}
int isEmpty(Queue* pq) {assert(pq);if (pq->head == NULL) {return 1;} else {return 0;}
}
int QueSize(Queue* pq) {assert(pq);QueueNode* curr = pq->head;int size = 0;while (curr) {curr = curr->next;size++;}return size;
}
// 内部使用两个队列即可
typedef struct {Queue q1;Queue q2;
} MyStack;MyStack* myStackCreate() {MyStack* stk = (MyStack*)malloc(sizeof(MyStack));// 两个队列初始化QueInit(&stk->q1);QueInit(&stk->q2);return stk;
}void myStackPush(MyStack* obj, int x) {if (!isEmpty(&obj->q1)) // 哪个队列不为空就进去{QuePush(&obj->q1, x);} else {QuePush(&obj->q2, x);}
}int myStackPop(MyStack* obj) {// 默认q1为空Queue* empty = &obj->q1;Queue* nonempty = &obj->q2;if(isEmpty( &obj->q2)){empty = &obj->q2;nonempty = &obj->q1;}while(QueSize(nonempty) > 1){QuePush(empty,QueFront(nonempty));QuePop(nonempty);}// 此时nonemty的队列就剩1个int ret = nonempty->head->data;QuePop(nonempty);return ret;
}int myStackTop(MyStack* obj) {if (!isEmpty(&obj->q1)) {return obj->q1.tail->data;} else {return obj->q2.tail->data;}
}bool myStackEmpty(MyStack* obj) {if (isEmpty(&obj->q1) == 1 && isEmpty(&obj->q2) == 1) {return true;} else {return false;}
}void myStackFree(MyStack* obj) {QueDestroy(&obj->q1);QueDestroy(&obj->q2);free(obj);
}/*** Your MyStack struct will be instantiated and called as such:* MyStack* obj = myStackCreate();* myStackPush(obj, x);* int param_2 = myStackPop(obj);* int param_3 = myStackTop(obj);* bool param_4 = myStackEmpty(obj);* myStackFree(obj);
*/

3. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

分析：

        这里可以用两个栈来实现队列，stk1、stk2。

入队：stk1用来压入数据，每次进队列的时候可以直接将数据放入stk1中。

出队：将stk1进行出栈，每一次出栈的元素再入栈到stk2，这样我们发现元素就会进行逆置，此时再出栈stk2就把队列的第一个元素就删除了。

peek：和出队类似，不过这里只是把stk2的栈顶元素进行返回而不是删除。

判空：判断两个栈均不为空。

复用：peek的本质是将stk1的内容转移到stk2，返回stk2的栈顶元素，所以出队的时候可以先调用peek，将stk2的首元素保存，然后再弹出stk2的栈顶元素，最后返回保存的stk2的之前的栈顶元素。

释放内存：先释放两个栈，再free队列。

代码：


typedef int dataType;
typedef struct Stack {int* _a;       // 用数组来实现int _top;      // 栈的数据的个数、栈顶元素下表int _capacity; // 栈的容量
} Stack;// 初始化
void InitStack(Stack* stk) {assert(stk);stk->_a = malloc(sizeof(dataType) * 4);stk->_capacity = 4;stk->_top = 0; // 栈顶元素下标为0
}
// 销毁
void DestroyStack(Stack* stk) {assert(stk);free(stk->_a);stk->_a = NULL;stk->_capacity = stk->_top = 0;
}
// 入栈
void PushStack(Stack* stk, dataType x) {assert(stk);if (stk->_capacity == stk->_top) // 容量和栈元素个数相等，就扩容{stk->_capacity *= 2;dataType* tmp =(dataType*)realloc(stk->_a, sizeof(dataType) * stk->_capacity);if (tmp == NULL) {printf("内存不足！");exit(-1);} else {stk->_a = tmp;}}// 正常插入stk->_a[stk->_top] = x;stk->_top++;
}
// 出栈
void PopStack(Stack* stk) {assert(stk);assert(stk->_top > 0); // 有元素才能删除stk->_top--;
}
// 栈的元素个数
int SizeStack(Stack* stk) {assert(stk);return stk->_top;
}
// 栈是否为空
int isEmpty(Stack* stk) {assert(stk);return stk->_top == 0 ? 1 : 0; // 没有元素就是空
}
// 获取栈顶数据
dataType getTop(Stack* stk) {assert(stk);if (stk->_top > 0) {return stk->_a[stk->_top - 1];} else {return -1;}
}typedef struct {// 两个栈Stack stk1;Stack stk2;} MyQueue;MyQueue* myQueueCreate() {MyQueue* ret = (MyQueue*)malloc(sizeof(MyQueue));InitStack(&ret->stk1);InitStack(&ret->stk2);return ret;
}void myQueuePush(MyQueue* obj, int x) { PushStack(&obj->stk1, x); }int myQueuePeek(MyQueue* obj) {if(!isEmpty(&obj->stk2)){return getTop(&obj->stk2);// stk2有值就说明，stk1一定没有值，已经转换完毕}while (!isEmpty(&obj->stk1)) {PushStack(&obj->stk2, getTop(&obj->stk1));PopStack(&obj->stk1);}int ret = getTop(&obj->stk2);return ret;
}int myQueuePop(MyQueue* obj) {int ret = myQueuePeek(obj); //把stk1所有元素导入到stk2PopStack(&obj->stk2);return ret;
}bool myQueueEmpty(MyQueue* obj) {if (isEmpty(&obj->stk1) && isEmpty(&obj->stk2)) {return true;} else {return false;}
}void myQueueFree(MyQueue* obj) {DestroyStack(&obj->stk1);DestroyStack(&obj->stk2);free(obj);
}/*** Your MyQueue struct will be instantiated and called as such:* MyQueue* obj = myQueueCreate();* myQueuePush(obj, x);* int param_2 = myQueuePop(obj);* int param_3 = myQueuePeek(obj);* bool param_4 = myQueueEmpty(obj);* myQueueFree(obj);
*/

4. 设计循环队列

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

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

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

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

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

思路：

        此题使用数组进行实现，使用两个指针，一个指针是rear，当插入数据的时候需要后移指针，一个指针是front，当删除一个数据的时候，需要后移指针，这样一来就会出现问题：

①当循环队列为空的时候：rear == front：

②当删除、增加几个元素的时候，此时rear == front

也就是说没有办法确定当rear和front相等的时候，此时是队列满还是队列空。

解决方法：

        多留一个位置，例如如果队列是4个位置，那么实际上要开辟5个位置：

        此时（rear + 1） % 实际长度 == front的下标（即1），说明此时的队列是满的；

如果rear == front说明此时队列是空的。

        如此以来就区分了当指针相同的时候遇到的两种情况，注意这里的空，并不是一个固定的位置。

        这里的首尾相接是这么处理的：当front或者rear走到数组的末端，需要向下继续走的时候，这时候会跳转到数组的首位（通过%数组的真实长度实现）。

代码：

http://www.lryc.cn/news/616003.html

相关文章：

  • Shell脚本-其他变量定义
  • vue和react和uniapp的状态管理分别是什么，并且介绍和怎么使用
  • How Websites Work 网站如何运作
  • Vue 事件冒泡处理指南：从入门到精通
  • 五种Excel表格导出方案
  • sqllabs——Less1
  • 前端学习日记 - 前端函数防抖详解
  • 遇到前端导出 Excel 文件出现乱码或文件损坏的问题
  • 打靶日常-upload-labs(21关)
  • Spring Boot配置文件加密详解
  • crc32算法php版----crc32.php
  • 【redis初阶】--------Set 集合类型
  • 如何通过API接口实现批量获取淘宝商品数据？（官方与非官方渠道分享）
  • Linux 路由子系统深度分析：框架、实现与代码路径
  • [Python 基础课程]常用函数
  • X265性能分析开源代码
  • 【高等数学】第八章 向量代数与空间解析几何——第六节 空间曲线及其方程
  • Video Lecture 8 Page Fault
  • 使用 Python 进行图片识别的项目开发
  • git merge和git rebase的区别
  • MIRO中文本如何传入FI凭证的
  • 基于Spring SSE构建实时监控系统
  • SpringCloud详细笔记
  • es-drager-blog
  • Java 日常开发笔记（小程序页面交互传参-id）
  • 震动马达实现库函数版（STC8）
  • 升级 JDK 17 碰到的请求 https 问题
  • 如何在Python中使用flask框架搭建web服务？
  • org.apache.hadoop.hbase.TableNotFoundException: ApplicationIndex
  • C/C++类型转换（C++四大强制类型转换）