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

栈和队列刷题篇

article 2025/1/24 21:51:39

大家好，这里是小编的博客频道
小编的博客：就爱学编程

很高兴在CSDN这个大家庭与大家相识，希望能在这里与大家共同进步，共同收获更好的自己！！！

目录

  • 1.括号匹配问题
    • （1）题目描述
    • （2）解题思路
  • 2.循环队列
    • （1）题目描述
    • （2）解题思路
  • 3.用队列实现栈
    • （1）题目描述
    • （2）解题思路
  • 4.用两个栈实现队列
    • （1）题目描述
    • （2）解题思路
  • 快乐的时光总是短暂，咱们下篇博文再见啦！！！如果小编的文章会对你有帮助的话不要忘了，记得给小编点赞、收藏支持一下，在此非常感谢！！！

在这里插入图片描述

废话不多说，我们直接看题。

1.括号匹配问题

（1）题目描述

在这里插入图片描述
在这里插入图片描述

（2）解题思路

  • 左括号入栈，右括号出栈，一一配对
  • 我们先对字符串的每个元素进行判断------如果是左括号就让左括号入栈，如果是右括号就出栈顶元素进行匹配------如果是一一匹配就是true，不是就是false

代码实现：

#define MAXCAPACITY 4
typedef char Datastyle;
typedef struct stack {
	Datastyle* a;            
	int top;
	int capacity;
}ST;
void STInit(ST* ps);
void  STDestory(ST* ps);
void STPush(ST* ps, Datastyle x);
void STPop(ST* ps);
Datastyle STTop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);

//初始化栈
void STInit(ST* ps) {
	assert(ps);
	Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
	if (temp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = MAXCAPACITY;
	ps->top = 0;
}

//销毁栈
void  STDestory(ST* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x) {
	assert(ps);
	//判断是否满了
	if (ps->top == ps->capacity) {
		Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle));				//扩容为当前容量的两倍比较合理
		if (temp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->a = temp;
        ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
    ps->top++;
}

//判空
bool STEmpty(ST* ps) {
	return (ps->top == 0);
}

//删除数据（从栈顶）----（出栈）
void STPop(ST* ps) {
	assert(ps && !STEmpty(ps));
	--ps->top;
}

//访问栈顶元素
Datastyle STTop(ST* ps) {
	return ps->a[ps->top - 1];
}

//得出栈的元素个数
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}

bool isValid(char* s) {
    //求解这道题的思路是：我们先对字符串的每个元素进行判断------如果是左括号就让左括号入栈，如果是右括号就出栈顶元素进行匹配------如果是一一匹配就是true，不是就是false
    
    //1、创建一个栈
    ST st;

    //2、初始化栈
    STInit(&st);

    //3、开始判断
    while(*s){
        if(*s == '[' || *s == '{' || *s == '('){
            STPush(&st, *s);                             //入栈
        }
        else{
            if(STEmpty(&st)) 
            {
                //4、销毁栈
                STDestory(&st);
                return false;
            }          //如果一开始就没有左括号进栈就说明括号不可能匹配的上（这里可以用判空函数进行判断也可以用计数函数是否为零进行判断）

            char top = STTop(&st);                  //储存栈顶元素
            STPop(&st);                             //出栈

            if((*s == ']' && top != '[')
            || (*s == '}' && top != '{')
            || (*s == ')' && top != '('))
            {
                //4、销毁栈
                STDestory(&st);
                return false;
            }
        }

        s++;                                       //不管进入哪个语句都要使得s++以用来进行循环
    }

    if(!STEmpty(&st)){                              //如果以上循环出来就只剩两种可能性--------（1）字符串中只有左括号，不匹配；（2）一一匹配,循环出来时栈为空
    //4、销毁栈
    STDestory(&st);
        return false; 
    }
    //4、销毁栈
    STDestory(&st);
    return true;
    
}

2.循环队列

（1）题目描述

在这里插入图片描述

在这里插入图片描述

（2）解题思路

  • 在循环队列中，当队列为空，可知front=rear；而当所有队列空间全占满时，也有 front=rear。为了区别这两种情况，假设队列使用的数组有 capacity 个存储空间，则此时规定循环队列最多只能有capacity−1 个队列元素，当循环队列中只剩下一个空存储单元时，则表示队列已满。根据以上可知，队列判空的条件是 front=rear，而队列判满的条件是 front(rear+1)modcapacity。对于一个固定大小的数组，只要知道队尾 rear 与队首 front，即可计算出队列当前的长度(rear−front+capacity)modcapacity

循环队列的属性如下:

elements：一个固定大小的数组，用于保存循环队列的元素。
capacity：循环队列的容量，即队列中最多可以容纳的元素数量。
front：队列首元素对应的数组的索引。
rear：队列尾元素对应的索引的下一个索引。

循环队列的接口方法如下：

MyCircularQueue(int k): 初始化队列，同时base 数组的空间初始化大小为 k+1。front,rear 全部初始化为 0。
enQueue(int value)：在队列的尾部插入一个元素，并同时将队尾的索引 rear 更新为 (rear+1)modcapacity。
deQueue()：从队首取出一个元素，并同时将队首的索引 front 更新为 (front+1)modcapacity。
Front()：返回队首的元素，需要检测队列是否为空。
Rear()：返回队尾的元素，需要检测队列是否为空。
isEmpty()：检测队列是否为空，根据之前的定义只需判断 rear 是否等于 front。
isFull()：检测队列是否已满，根据之前的定义只需判断 front 是否等于 (rear+1)modcapacity。

代码实现：

typedef struct {
    int* a;
    int k;
    int front;
    int rear;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {
	MyCircularQueue* ps	= (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	if (ps == NULL) {
		perror("malloc fail");
		return NULL;
	}
	int* ptr = (int*)malloc(sizeof(int) * (k + 1));
	if (ptr == NULL) {
		perror("malloc fail");
		return NULL;
	}
	ps->a = ptr;
	ps->front = ps->rear = 0;
	ps->k = k;
	return ps;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
	return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) {
	return ((obj->rear + 1) % (obj->k + 1)) == obj->front;
}

int myCircularQueueFront(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
	return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) {
    if(myCircularQueueIsEmpty(obj)){
        return -1;
    }
	return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}


void myCircularQueueFree(MyCircularQueue* obj) {
	free(obj->a);
	obj->a = NULL;
	free(obj);
	obj = NULL;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
	if (!myCircularQueueIsFull(obj)) {
		obj->a[obj->rear] = value;
        obj->rear++;
		obj->rear %= (obj->k + 1);
		return true;
	}
	return false;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {
	if (!myCircularQueueIsEmpty(obj)) {
		obj->a[obj->front++] = 0;
		obj->front %= (obj->k + 1);
		return true;
	}
	return false;
}

  • 3.用队列实现栈

（1）题目描述

在这里插入图片描述

在这里插入图片描述

（2）解题思路

  • 为了满足栈的特性，即最后入栈的元素最先出栈，在使用队列实现栈时，应满足队列前端的元素是最后入栈的元素。可以使用两个队列实现栈的操作，其中queue 1​ 用于存储栈内的元素，queue 2 作为入栈操作的辅助队列。
  • 入栈操作时，首先将元素入队到queue 2，然后将 queue 1 的全部元素依次出队并入队到 queue 2 ，此时 queue 2 的前端的元素即为新入栈的元素，再将queue 1 和 queue 2互换，则 queue 1 的元素即为栈内的元素，queue 1的前端和后端分别对应栈顶和栈底。由于每次入栈操作都确保 queue 1 的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue 1 的前端元素并返回即可，获得栈顶元素操作只需要获得queue 1 的前端元素并返回即可（不移除元素）。由于 queue 1 用于存储栈内的元素，判断栈是否为空时，只需要判断 queue 1 是否为空即可。

代码实现：

typedef int QDatatype;
typedef struct QuequeNode {
	QDatatype data;
	struct QuequeNode* next;
}QNode;
typedef struct Queue{
	QNode* head;			//单链表的头指针作为队头
	QNode* tail;			//单链表的尾指针作为队尾
	int size;				//存储队列元素数量
}Que;

//初始化队列
void QInit(Que* ps) {
	assert(ps);
	ps->head = ps->tail = NULL;
	ps->size = 0;
}

//销毁队列
void QDestroy(Que* ps) {
	assert(ps);
	QNode* cur = ps->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	ps->size = 0;
	ps->head = ps->tail = NULL;
}

//插入数据（从队尾）------入队
void QPush(Que* ps, QDatatype x) {
	assert(ps);
	QNode* cur = (QNode*)malloc(sizeof(QNode));
	if (cur == NULL) {
		perror("malloc fail");
		return;
	}
	if (ps->head == NULL) {
		assert(ps->tail == NULL);
		ps->head = ps->tail = cur;
	}
	else {
		ps->tail->next = cur;		//先赋值
		ps->tail = cur;				//再更新尾指针
	}
	cur->next = NULL;
	cur->data = x;
	ps->size++;
}

//判空
bool QEmpty(Que* ps) {
	assert(ps);
	return (ps->size == 0);
}

//删除数据（从对头）------出队
void QPop(Que* ps) {
	assert(ps);
	assert(!QEmpty(ps));
	if (ps->head->next == NULL) {
		free(ps->head);
		ps->head = ps->tail = NULL;
		ps->size = 0;
		return;
	}
	QNode* next = ps->head->next;
	free(ps->head);
	ps->head = next;
	ps->size--;
}

//得出队内元素数量
int QSize(Que* ps) {
	assert(ps);
	return (ps->size);
}

//得到队头元素的数据
QDatatype QFront(Que* ps) {
	assert(ps && !QEmpty(ps));
	return (ps->head->data);
}

//得到队尾元素的数据
QDatatype QBack(Que* ps) {
	assert(ps && !QEmpty(ps));
	return (ps->tail->data);
}

typedef struct {
    Que q1;
    Que q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* ptr = (MyStack*)malloc(sizeof(MyStack));
    if(ptr == NULL){
        perror("malloc fail");
        return NULL;
    }
    QInit(&ptr->q1);
    QInit(&ptr->q2);
    return ptr;
}

void myStackPush(MyStack* obj, int x) {
    if(QEmpty(&obj->q1)){
        QPush(&obj->q2, x);
    }
    else{
        QPush(&obj->q1, x);
    }
}

int myStackPop(MyStack* obj) {
    if(QEmpty(&obj->q1)){
        while(QSize(&obj->q2) > 1){
            QDatatype temp = QFront(&obj->q2);
            QPop(&obj->q2);
            QPush(&obj->q1, temp);
        }
        QDatatype top =  QBack(&obj->q2);
        QPop(&obj->q2);
        return top;
    }
    else{
        while(QSize(&obj->q1) > 1){
            QDatatype temp = QFront(&obj->q1);
            QPop(&obj->q1);
            QPush(&obj->q2, temp);
        }
        QDatatype top =  QBack(&obj->q1);
        QPop(&obj->q1);
        return top;
    }
}

int myStackTop(MyStack* obj) {
    if(QEmpty(&obj->q1)){
        return QBack(&obj->q2);
    }
    return QBack(&obj->q1);
}

bool myStackEmpty(MyStack* obj) {
    return QEmpty(&obj->q1) && QEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) {
    QDestroy(&obj->q1);
    QDestroy(&obj->q2);
    free(obj);
    obj = NULL;
}

4.用两个栈实现队列

（1）题目描述

在这里插入图片描述
在这里插入图片描述

（2）解题思路

  • 将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。
  • 每次pop或peek时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

代码实现：

#define MAXCAPACITY 4

typedef int Datastyle;

typedef struct stack {
	Datastyle* a;               
	int top;
	int capacity;
}ST;

//初始化栈
void STInit(ST* ps) {
	assert(ps);
	Datastyle* temp = (Datastyle*)malloc(MAXCAPACITY * sizeof(Datastyle));
	if (temp == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	ps->a = temp;
	ps->capacity = MAXCAPACITY;
	ps->top = 0;
}

//销毁栈
void  STDestory(ST* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}

//插入数据（从栈顶）----（入栈，压栈）
void STPush(ST* ps, Datastyle x) {
	assert(ps);
	//判断是否满了
	if (ps->top == ps->capacity) {
		Datastyle* temp = (Datastyle*)realloc(ps->a, 2 * ps->capacity * sizeof(Datastyle));				//扩容为当前容量的两倍比较合理
		if (temp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->capacity *= 2;
		ps->a = temp;
	}
	ps->a[ps->top++] = x;
}

//判空
bool STEmpty(ST* ps) {
	return (ps->top == 0);
}

//删除数据（从栈顶）----（出栈）
void STPop(ST* ps) {
	assert(ps && !STEmpty(ps));
	--ps->top;
}

//访问栈顶元素
Datastyle STTop(ST* ps) {
	return ps->a[ps->top - 1];
}

//得出栈的元素个数
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}

typedef struct {
    ST stpush;                 //stpush专门用来存储数据，只有在stpop为空时进行出数据至st2
    ST stpop;                 //stpop专门用来出数据，只有当其为空时从stpush拿出数据进行存储
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* ptr = (MyQueue*) malloc(sizeof(MyQueue));
    if(ptr == NULL){
        perror("malloc fail");
        return NULL;
    }
    STInit(&ptr->stpush);
    STInit(&ptr->stpop);
    return ptr;
}

void myQueuePush(MyQueue* obj, int x) {
    STPush(&obj->stpush, x);
}

int myQueuePop(MyQueue* obj) {
    if(STEmpty(&obj->stpop)){
        while(!STEmpty(&obj->stpush)){
        Datastyle temp = STTop(&obj->stpush);
        STPop(&obj->stpush);
        STPush(&obj->stpop, temp);
        }
    }
    Datastyle top =  STTop(&obj->stpop);
    STPop(&obj->stpop);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->stpop)){
        while(!STEmpty(&obj->stpush)){
        Datastyle temp = STTop(&obj->stpush);
        STPop(&obj->stpush);
        STPush(&obj->stpop, temp);
        }
    }
    return STTop(&obj->stpop);
}

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->stpush) && STEmpty(&obj->stpop);
}

void myQueueFree(MyQueue* obj) {
    STDestory(&obj->stpush);
    STDestory(&obj->stpop);
    free(obj);
    obj = NULL;
}

快乐的时光总是短暂，咱们下篇博文再见啦！！！如果小编的文章会对你有帮助的话不要忘了，记得给小编点赞、收藏支持一下，在此非常感谢！！！


http://www.kler.cn/a/516848.html

相关文章：

  • Git Bash 配置 zsh
  • Linux 常用命令——系统设置篇（保姆级说明）
  • Java学习教程，从入门到精通，JDBC创建数据库语法知识点及案例代码（99）
  • springBoot 整合ModBus TCP
  • Python装饰器的高级用法：动态装饰器与参数传递的深度解析
  • 密码无关认证：金融机构如何解决密码问题
  • 新能源汽车充电桩选型以及安装应用
  • 2025.1.20——四、[强网杯 2019]Upload1 文件上传|反序列化
  • STM32——KEY按键
  • ETLCloud在iPaas中的是关键角色？
  • 若依 v-hasPermi 自定义指令失效场景
  • Java核心技术解析：泛型与类型安全全面指南
  • android wifi AsyncChannel（WifiManager和WifiP2pManager）
  • 【CS61A 2024秋】Python入门课，全过程记录P3（Week5 Sequences开始，更新于2025/1/23）
  • 韩国机场WebGIS可视化集合Google遥感影像分析
  • Java EE 进阶：Spring MVC（1）
  • HarmonyOS快速入门
  • 【YOLOv10改进[Backbone]】使用LSKNet替换Backbone | 用于遥感目标检测的大型选择性核网络
  • 在centos上编译安装opensips【初级-默认安装】
  • Nginx 性能优化技巧与实践（一）
  • PLC通信
  • 2025年最新汽车零部件企业销售项目管理解决方案
  • 解密堡垒机：安全与效率的守护者
  • 2K320Hz显示器哪个好？
  • Vue.js 嵌套路由和动态路由
  • 【问题】Qt c++ 界面 lineEdit、comboBox、tableWidget.... SIGSEGV错误