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

经典栈和队列OJ题

news 2025/6/27 7:39:57

目录

栈

1、括号匹配问题

 2、用栈实现队列

队列 

3、用队列实现栈

4、设计循环队列

栈

1、括号匹配问题

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

有效字符串需满足：

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

思路：

利用栈的后进先出，边进边出的性质

将左括号存入栈中，后进入的左括号先出来，与右括号进行匹配

// 支持动态增长的栈
typedef char STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 栈顶int _capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}//动态申请
void Stackcapacity(Stack* ps)
{if (ps->_top == ps->_capacity){ps->_capacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, ps->_capacity * sizeof(STDataType));if (tmp == NULL){perror("Stackcapacity()::realloc()");return;}ps->_a = tmp;}
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);Stackcapacity(ps);//动态申请ps->_a[ps->_top] = data;ps->_top++;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);if (ps->_top == 0){printf("栈已空\n");return;}ps->_top--;
}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_top != 0);return ps->_a[ps->_top - 1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);if (ps->_top == 0)return 1;elsereturn 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}bool isValid(char* s) {Stack stack;StackInit(&stack);for(int i = 0;i<strlen(s);i++){if(s[i] == '('||s[i] == '['||s[i] == '{')//栈存左括号{StackPush(&stack,s[i]);continue;//已经push,就进行下一次循环，判断下一个括号}if(StackEmpty(&stack))//栈空了，当前无左括号，与右括号匹配{StackDestroy(&stack);//return前要destroy，leetcode内存泄漏不报错return  false;}char a = StackTop(&stack);StackPop(&stack);if(a == '('&&s[i] != ')'||a == '['&&s[i] != ']'||a == '{'&&s[i] != '}'){StackDestroy(&stack);return  false;}}if(!StackEmpty(&stack))//匹配完后，栈里多了左括号{StackDestroy(&stack);return  false;}return true;
}

 2、用栈实现队列

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

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：

一个栈push，一个栈pop(当pop没有元素时，push的全部元素转移到pop)，

pop的栈顶元素就是队头元素(因为已逆置)

destroy时，注意指针里有指针

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 栈顶int _capacity;  // 容量 
}Stack;// 初始化栈 
void StackInit(Stack* ps)
{assert(ps);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}//动态申请
void Stackcapacity(Stack* ps)
{if (ps->_top == ps->_capacity){ps->_capacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;STDataType* tmp = (STDataType*)realloc(ps->_a, ps->_capacity * sizeof(STDataType));if (tmp == NULL){perror("Stackcapacity()::realloc()");return;}ps->_a = tmp;}
}// 入栈 
void StackPush(Stack* ps, STDataType data)
{assert(ps);Stackcapacity(ps);//动态申请ps->_a[ps->_top] = data;ps->_top++;
}// 出栈 
void StackPop(Stack* ps)
{assert(ps);if (ps->_top == 0){printf("栈已空\n");return;}ps->_top--;
}// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{assert(ps);assert(ps->_top != 0);return ps->_a[ps->_top - 1];
}// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{assert(ps);return ps->_top;
}// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{assert(ps);if (ps->_top == 0)return 1;elsereturn 0;
}// 销毁栈 
void StackDestroy(Stack* ps)
{assert(ps);free(ps->_a);ps->_a = NULL;ps->_top = ps->_capacity = 0;
}typedef struct {Stack push;Stack pop;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));StackInit(&(obj->push));StackInit(&(obj->pop));return obj;
}void myQueuePush(MyQueue* obj, int x) {StackPush(&(obj->push),x);
}bool myQueueEmpty(MyQueue* obj) {if(StackEmpty(&(obj->push))&&StackEmpty(&(obj->pop)))return true;elsereturn false;
}int myQueuePop(MyQueue* obj) {if(myQueueEmpty(obj))return -1;int x = myQueuePeek(obj);StackPop(&(obj->pop));return x;
}int myQueuePeek(MyQueue* obj) {if(myQueueEmpty(obj))return -1;if(StackEmpty(&(obj->pop)))while(!StackEmpty(&(obj->push))){StackPush(&(obj->pop),StackTop(&(obj->push)));StackPop(&(obj->push));}return StackTop(&(obj->pop));
}void myQueueFree(MyQueue* obj) {StackDestroy(&(obj->push));StackDestroy(&(obj->pop));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);
*/

队列 

3、用队列实现栈

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

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

思路：

元素全push到一个队列里，保持一个非空队列，一个空队列，但不是固定的，因为会转移元素

要取栈顶元素，调用非空队列的queueback()，

删除栈顶元素，把非空队列的元素转移到空队列，当非空队列只有一个元素时，跳出循环，保存栈顶元素，pop掉栈顶元素

destroy时，注意指针里有指针

typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* _front;QNode* _rear;int size;
}Queue;// 初始化队列 
void QueueInit(Queue* q)
{assert(q);q->_front = q->_rear = NULL;q->size = 0;
}// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{assert(q);QNode* tmp = (QNode*)malloc(sizeof(QNode));if (tmp == NULL){perror("QueueNode()::malloc()");return;}tmp->_next = NULL;tmp->_data = data;if (q->size == 0){q->_front = q->_rear = tmp;}else{q->_rear->_next = tmp;q->_rear = tmp;}q->size++;
}// 队头出队列 
void QueuePop(Queue* q)
{assert(q);if (q->size == 0){printf("队列已空\n");return;}QNode* del = q->_front;q->_front = q->_front->_next;if (q->_front == NULL){q->_rear = NULL;}free(del);del = NULL;q->size--;
}// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{assert(q);assert(q->_front);return q->_front->_data;
}// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{assert(q);assert(q->_rear);return q->_rear->_data;
}// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{return q->size;
}// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{if (q->size == 0)return 1;elsereturn 0;
}// 销毁队列 
void QueueDestroy(Queue* q)
{while (q->_front){QNode* del = q->_front;q->_front = q->_front->_next;free(del);}q->_rear = NULL;q->size = 0;
}typedef struct {Queue Q1;Queue Q2;
} MyStack;MyStack* myStackCreate() {MyStack* obj = (MyStack*)malloc(sizeof(MyStack));assert(obj);QueueInit(&(obj->Q1));QueueInit(&(obj->Q2));return obj;
}void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&(obj->Q1)))//push非空的，开始pushQ2QueuePush(&(obj->Q1),x);elseQueuePush(&(obj->Q2),x);
}bool myStackEmpty(MyStack* obj) {if(QueueEmpty(&(obj->Q1))&&QueueEmpty(&(obj->Q2)))return true;elsereturn false;
}int myStackPop(MyStack* obj) {if(myStackEmpty(obj))return -1;Queue* empty = &(obj->Q1);Queue* noempty = &(obj->Q2);//要改变Q1,Q2,用指针if(QueueEmpty(&(obj->Q2)))//假设法{empty = &(obj->Q2);noempty = &(obj->Q1);}while(QueueSize(noempty) != 1){QueuePush(empty,QueueFront(noempty));QueuePop(noempty);}int x = QueueFront(noempty);QueuePop(noempty);return x;
}int myStackTop(MyStack* obj) {if(myStackEmpty(obj))return -1;if(!QueueEmpty(&(obj->Q1)))return QueueBack(&(obj->Q1));elsereturn QueueBack(&(obj->Q2));
}void myStackFree(MyStack* obj) {QueueDestroy(&(obj->Q1));QueueDestroy(&(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);
*/

4、设计循环队列

思路：

数组+%进行循环

typedef struct {int* arr;int front;int rear;int size;int capacity;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));obj->arr = (int*)malloc(sizeof(int)*k);obj->front = obj->rear = obj->size = 0;obj->capacity = k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {if(obj->size == 0)return true;elsereturn false;
}bool myCircularQueueIsFull(MyCircularQueue* obj) {if(obj->front == obj->rear&&obj->size != 0)return true;elsereturn false;
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;else{obj->arr[obj->rear] = value;obj->rear = (obj->rear+1)%obj->capacity;obj->size++;return true;}
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;else{obj->front = (obj->front+1)%obj->capacity;obj->size--;return true;}
}int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->arr[obj->front];
}int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return -1;elsereturn obj->arr[(obj->rear-1+obj->capacity)%obj->capacity];
}void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);free(obj);
}/*** 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);
*/


http://www.mrgr.cn/news/22166.html

相关文章：

  • API 架构（RPC风格、RESTful风格）
  • 用Pytho解决分类问题_DBSCAN聚类算法模板
  • C++函数提高
  • 在Python中读取Excel文件
  • PAT甲级-1085 Perfect Sequence
  • Linux下的PWM驱动
  • C++万字解析类和对象（上）
  • 面试真题 | 记录一次面试真题
  • 「iOS学习」——Masonry学习
  • 如何解决缓存（redis）和数据库（MySQL）数据不一致的问题？
  • 衡石分析平台使用手册-快速入门
  • 长短期记忆神经网络-LSTM回归预测-MATLAB代码实现
  • 一名优秀的工程师应该学会在工作中提升自己，面试篇
  • matlab读取NC文件（含group）
  • vulhub远程执行命令漏洞CVE-2022-22963
  • SprinBoot+Vue校园数字化图书馆系统的设计与实现
  • Vulhub Apache Airflow （CVE-2020-11978）
  • QML入门之创建可重用的组件（一）
  • 828华为云征文｜Flexus X实例C#/.Net Core 结合（git代码管理、docker自定义镜像）快速发布部署-让你的项目飞起来~
  • 【微前端记录】微前端qiankun初体验