【初阶数据结构】5.栈和队列

  • 开发
  • 16

文章目录

1.栈

1.1 概念与结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

在这里插入图片描述

栈底层结构选型

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

1.2 栈的实现

Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//定义栈的结构
typedef int STDataType;
typedef struct Stack {
	STDataType* arr;
	int capacity;//栈的空间大小
	int top;//栈顶
}ST;

//栈的初始化
void STInit(ST* ps);

//栈的销毁
void STDestory(ST* ps);

//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x);
//出数据
void StackPop(ST* ps);

//取栈顶元素
STDataType StackTop(ST* ps);

//获取栈中有效元素个数
int STSize(ST* ps);

//判断栈是否为空
bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

//栈的初始化
void STInit(ST* ps) {
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

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

//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {
	assert(ps);
	//1.判断空间是否足够
	if (ps->capacity == ps->top) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL) {
			perror("relloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//出数据
void StackPop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));//栈为空报错
	--ps->top;
}

//判断栈是否为空
bool StackEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

//获取栈中有效元素个数
int STSize(ST* ps){
	assert(ps);
	return ps->top;
}

//取栈顶元素
STDataType StackTop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"

void STTest() {
	ST st;
	STInit(&st);
	//
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st, 4);
	printf("size: %d\n", STSize(&st));

	//循环出栈，直到栈为空
	while (!StackEmpty(&st)) {
		STDataType data = StackTop(&st);
		printf("%d ", data);
		//出栈
		StackPop(&st);
	}
	printf("size: %d\n", STSize(&st));

	//
	//STDestory(&st);
}

int main() {
	STTest();
	return 0;
}

2.队列

2.1 概念与结构

概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

在这里插入图片描述

队列底层结构选型

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.2 队列的实现

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//定义队列结构
typedef int QDataType;

typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue {
	QueueNode* phead;//队头：删
	QueueNode* ptail;//队尾：插
	int size;//保存队列有效数据个数
}Queue;

//初始化队列
void QueueInit(Queue* pq);

// 入队列，队尾
void QueuePush(Queue* pq, QDataType x);

// 出队列，队头
void QueuePop(Queue* pq);

//队列判空
bool QueueEmpty(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);

//取队尾数据
QDataType QueueBack(Queue* pq);

//队列有效元素个数
int QueueSize(Queue* pq);

//销毁队列
void QueueDestroy(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"

//初始化队列
void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// 入队列，队尾
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	//申请新结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	
	if (pq->phead == NULL) {//判断队列是否为空
		pq->phead = pq->ptail = newnode;
	}
	else {
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;//入一次，size++ 一次
}

//队列判空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return (pq->phead == NULL) && (pq->ptail == NULL);
}

// 出队列，队头
void QueuePop(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		//删除队头元素
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;//出一次，size-- 一次
}

//取队头数据
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列不为空
	
	return pq->phead->data;
}

//取队尾数据
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列不为空

	return pq->ptail->data;
}

//队列有效元素个数
int QueueSize(Queue* pq) {
	assert(pq);
	/*int size = 0;
	QueueNode* pcur = pq->phead;
	while (pcur) {
		size++;
		pcur = pcur->next;//复杂度O(n)
	}*/
	return pq->size;//复杂度O(1)
}

//销毁队列
void QueueDestroy(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列不为空,空队列不需要销毁

	QueueNode* pcur = pq->phead;
	while (pcur) {
		QueueNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"


void QueueTest01() {
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	//QueuePop(&q);
	printf("head:%d\n", QueueFront(&q));
	printf("tail:%d\n", QueueBack(&q));
	printf("size:%d\n", QueueSize(&q));

	QueueDestroy(&q);

	//QueuePop(&q);
	//QueuePop(&q);
	//QueuePop(&q);
	//QueuePop(&q);
	QueuePop(&q);
}

int main() {
	QueueTest01();
	return 0;
}

3.栈和队列算法题

3.1 有效的括号

点击链接答题

在这里插入图片描述

思路：

定义一个指针ps遍历字符串

若ps遍历到的字符为左括号，入栈

若ps遍历到的字符为右括号，取栈顶元素与ps进行比较，

  1. 栈顶元素 匹配 *ps，出栈，ps++
  2. 栈顶元素 不匹配 *ps，返回false

代码：

//定义栈的结构
typedef char STDataType;
typedef struct Stack {
	STDataType* arr;
	int capacity;//栈的空间大小
	int top;//栈顶
}ST;

//栈的初始化
void STInit(ST* ps) {
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

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

//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {
	assert(ps);
	//1.判断空间是否足够
	if (ps->capacity == ps->top) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL) {
			perror("relloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

//出数据
void StackPop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));//栈为空报错
	--ps->top;
}

//获取栈中有效元素个数
int STSize(ST* ps){
	assert(ps);
	return ps->top;
}

//取栈顶元素
STDataType StackTop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

bool isValid(char* s) {
    ST st;
    //初始化
    STInit(&st);
    //遍历字符串s
    char* ps = s;
    while(*ps != '\0'){
        //左括号，入栈
        if(*ps == '(' || *ps == '[' || *ps == '{'){
            StackPush(&st, *ps);
        }
        else{//右括号，和栈顶元素比较是否匹配
        //栈为空，直接返回false
        if(StackEmpty(&st)){
            return false;
        }
        //栈不为空才能取栈顶元素
            char ch = StackTop(&st);
            if((*ps == ')' && ch == '(')
            || (*ps == ']' && ch == '[')
            || (*ps == '}' && ch == '{') ){
                StackPop(&st);
            } 
            else{
                //不匹配
                STDestory(&st);
                return false;
            }
        }
        ps++;

    }
    bool ret = StackEmpty(&st) == true;//如果为空，返回true
    //销毁
    STDestory(&st);
    return ret;
}

3.2 用队列实现栈

点击链接答题

在这里插入图片描述

思路：

出栈：找不为空的队列，将size-1个数据导入到另一个队列中。

入栈：往不为空队列里面插入数据

取栈顶元素：

例如：

两个队列：

  1. Q1：1 2 3
  2. Q2：NULL

如果是栈的话：

  1. 插入1 2 3
  2. 出栈一次
  3. 插入4
  4. 全部出栈

得到：3 4 2 1

将Q1里面的1 2出栈到Q2，把3取出来，此时Q1为NULL

取出了3

往Q2里面插入4，此时Q2为1 2 4

将Q2里面的1 2出栈到Q1，此时Q2为4，把4取出来，此时Q2为NULL

取出了3 4

将Q1里面的1出栈到Q2，把2取出来 ，此时Q1为NULL

取出了3 4 2

将Q2里面的1取出来

取出了3 4 2 1

代码：

//定义队列结构
typedef int QDataType;

typedef struct QueueNode {
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue {
	QueueNode* phead;//队头：删
	QueueNode* ptail;//队尾：插
	int size;//保存队列有效数据个数
}Queue;

//初始化队列
void QueueInit(Queue* pq) {
	assert(pq);
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

// 入队列，队尾
void QueuePush(Queue* pq, QDataType x) {
	assert(pq);
	//申请新结点
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	
	if (pq->phead == NULL) {//判断队列是否为空
		pq->phead = pq->ptail = newnode;
	}
	else {
		//队列不为空
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	pq->size++;//入一次，size++ 一次
}

//队列判空
bool QueueEmpty(Queue* pq) {
	assert(pq);
	return (pq->phead == NULL) && (pq->ptail == NULL);
}

// 出队列，队头
void QueuePop(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	//只有一个结点的情况，避免ptail变成野指针
	if (pq->ptail == pq->phead) {
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else {
		//删除队头元素
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
	--pq->size;//出一次，size-- 一次
}

//取队头数据
QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列不为空
	
	return pq->phead->data;
}

//取队尾数据
QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));//判断队列不为空

	return pq->ptail->data;
}

//队列有效元素个数
int QueueSize(Queue* pq) {
	assert(pq);
	return pq->size;//复杂度O(1)
}

//销毁队列
void QueueDestroy(Queue* pq) {
	assert(pq);
    //这里允许pq为空
	// assert(!QueueEmpty(pq));//判断队列不为空,空队列不需要销毁

	QueueNode* pcur = pq->phead;
	while (pcur) {
		QueueNode* Next = pcur->next;
		free(pcur);
		pcur = Next;
	}
	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}



//两个队列来实现栈
typedef struct {
    Queue q1;//队列1
    Queue q2;//队列2
} MyStack;

//STInit
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);

    return pst;
}

//Push入栈
void myStackPush(MyStack* obj, int x) {
    //往不为空的队列中插入数据
    if(!QueueEmpty(&obj->q1)){//如果q1不为空，执行这个
        QueuePush(&obj->q1,x);//往队列q1里面插入x
    }
    else{//如果q2不为空，执行这个
        QueuePush(&obj->q2,x);//往队列q2里面插入x
    }
}

//Pop出栈
int myStackPop(MyStack* obj) {
    //找不为空的队列
    Queue* empQ = &obj->q1;//定义q1为空
    Queue* noneQ = &obj->q2;//定义q2为非空
    if(!QueueEmpty(&obj->q1)){//如果q1不为空，执行这个
        noneQ = &obj->q1;//q1是非空队列
        empQ = &obj->q2;//q2是空队列
    }
    //将不为空队列中size-1个数据导入到空队列中
    while(QueueSize(noneQ) > 1){//循环结束的判断，是只剩下一个数据
        int front = QueueFront(noneQ);//取队头数据
        QueuePush(empQ,front);//往空队列q2里面插入队头元素
        QueuePop(noneQ);//把非空队列q1里面的队头元素拿出来，这样下次循环出来的队头元素就不会重复了
    }
    //非空队列中只剩下一个数据------要出栈的数据
    int pop = QueueFront(noneQ);//把要取出的数据存起来
    QueuePop(noneQ);//将数据出队列，让q1变成空队列
    return pop;//返回要取出的数据
}

//取栈顶元素：找不为空的队列，取队尾元素
//不出栈
int myStackTop(MyStack* obj) {
    if(!QueueEmpty(&obj->q1)){
        //q1不为空
        return QueueBack(&obj->q1);//取队尾数据
    }
    else{
        //q2不为空
        return QueueBack(&obj->q2);//取队尾数据
    }
}

//判断栈是否为空
//也就是判断两个队列是否为空
bool myStackEmpty(MyStack* obj) {//栈是空的，返回 true ；否则，返回 false 。
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

//栈的销毁
//也就是判断两个队列的销毁
void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);//销毁q1
    QueueDestroy(&obj->q2);//销毁q2
    //因为MyStack* myStackCreate()里面有个指针pst，所以我们还要销毁指针obj
    free(obj);//销毁指向栈的指针
    obj = NULL;
}

/**
 * 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.3 用栈实现队列

点击链接答题

在这里插入图片描述

思路：

定义两个栈：pushST（入数据）和popST（出数据）

假设我们要在队列里放123，出队列123

我们先在pushST里面放进去1 2 3

然后把pushST里面的数据拿到popST里面，依次是3 2 1

然后把1提取出来，把2提取出来，把3提取出来.

如果我们先在pushST里面放进去1 2 3

然后把pushST里面的数据拿到popST里面，依次是3 2 1

然后在pushST里面放进去4

然后把popST里面的1提取出来，把2提取出来，把3提取出来.

然后把pushST里面的数据4拿到popST里面

然后把4提取出来

入队：往pushST中插入数据

出队：判断popST是否为空，不为空直接pop，为空的话将pushST导入到popST中再pop

取队头：跟出队一样，但这里只取数据，不pop数据

代码：

//定义栈的结构
typedef char STDataType;
typedef struct Stack {
	STDataType* arr;
	int capacity;//栈的空间大小
	int top;//栈顶
}ST;

//栈的初始化
void STInit(ST* ps) {
	assert(ps);
	ps->arr = NULL;
	ps->capacity = ps->top = 0;
}

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

//栈顶---入数据，出数据
//入数据
void StackPush(ST* ps, STDataType x) {
	assert(ps);
	//1.判断空间是否足够
	if (ps->capacity == ps->top) {
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL) {
			perror("relloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//判断栈是否为空
bool StackEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

//出数据
void StackPop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));//栈为空报错
	--ps->top;
}

//获取栈中有效元素个数
int STSize(ST* ps){
	assert(ps);
	return ps->top;
}

//取栈顶元素
STDataType StackTop(ST* ps) {
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}



//
typedef struct {
    ST pushST;
    ST popST;
} MyQueue;

//队列的初始化
MyQueue* myQueueCreate() {
    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pst->pushST);
    STInit(&pst->popST);

    return pst;
}

//往pushST中插入数据
void myQueuePush(MyQueue* obj, int x) {
    StackPush(&obj->pushST,x);
}

//删除数据
//1.检查popST是否为空，不为空直接出，为空pushST导入到popST，再出数据
int myQueuePop(MyQueue* obj) {
    if(StackEmpty(&obj->popST)){
        //如果popST为空
        //导数据
        while(!StackEmpty(&obj->pushST)){
            //如果pushST非空
            StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进popST
            StackPop(&obj->pushST);
        }
    }
    //取栈顶，删除栈顶元素并返回栈顶数据
    int top = StackTop(&obj->popST);//储存删除的栈顶元素
    StackPop(&obj->popST);
    return top;//返回删除的栈顶元素
}

//取队头元素
int myQueuePeek(MyQueue* obj) {
    if(StackEmpty(&obj->popST)){
        //如果popST为空
        //导数据
        while(!StackEmpty(&obj->pushST)){
            //如果pushST非空
            StackPush(&obj->popST, StackTop(&obj->pushST));//把取到的栈顶元素导入进pushST
            StackPop(&obj->pushST);
        }
    }
    //取栈顶，删除栈顶元素并返回栈顶数据
    return StackTop(&obj->popST);//返回删除的栈顶元素
    
}

//判断队列是否为空
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

//队列的销毁
//就是两个栈的销毁
void myQueueFree(MyQueue* obj) {
    STDestory(&obj->pushST);
    STDestory(&obj->popST);
    free(obj);
    obj = NULL;
}

/**
 * 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.4 设计循环队列

点击链接答题

在这里插入图片描述

思路：

循环队列，空间固定。

这里我们可以用数组来实现循环队列。

如何判断队列是否为满？

多申请一块空间

(rear+1)%(k+1) == front

如何判断队列是否为空？

rear == front

代码：

//定义循环队列的结构
typedef struct {
    int* arr;//定义数组
    int front;//定义头
    int rear;//定义尾
    int capacity;//定义一个变量保存数组空间大小
} MyCircularQueue;

//循环队列的初始化
MyCircularQueue* myCircularQueueCreate(int k) {
    //定义一个指针，动态申请一块空间，指向循环队列
    MyCircularQueue* pst = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    //底层数组申请k+1个整型空间
    pst->arr = (int*)malloc(sizeof(int)*(k+1));

    pst->front = pst->rear = 0;
    pst->capacity = k;//把k保存起来
    return pst;//返回指向循环队列的指针
}

//判断队列是否满了
bool myCircularQueueIsFull(MyCircularQueue* obj) {
    //(rear+1)%(k+1) == front  就满了
    return (obj->rear+1)%(obj->capacity+1) == obj->front;
}

//入队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {
    //队列满了就不能插入数据
    if(myCircularQueueIsFull(obj)){
        return false;//说明插入失败
    }
    //队列没满，可以插入数据
    obj->arr[obj->rear++] = value;//插入一个数据rear++
    obj->rear %= obj->capacity + 1;//如果rear跑到队尾了，就通过取余回到队头

    return true;//说明插入成功
}

//判断队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {
    return obj->rear == obj->front;
}

//出队列
bool myCircularQueueDeQueue(MyCircularQueue* obj) {
    //队列为空
    if(myCircularQueueIsEmpty(obj)){
        return false;//表示删除失败
    }
    //队列不为空
    obj->front++;
    obj->front %= obj->capacity + 1;//如果front跑到队尾了，就通过取余回到队头
    return true;//表示删除成功
}

//取队头元素
int myCircularQueueFront(MyCircularQueue* obj) {
    //如果队列为空
    if(myCircularQueueIsEmpty(obj)){
        return -1;//如果队列为空，返回 -1 
    }
    //如果队列不为空
    return obj->arr[obj->front];
}

//取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) {
    //如果队列为空
    if(myCircularQueueIsEmpty(obj)){
        return -1;//如果队列为空，返回 -1 
    }
    //如果队列不为空
    int prev = obj->rear-1;//prev是rear前一个位置
    if(obj->rear == 0){
        prev = obj->capacity;//如果rear是处在arr[0]，那么prev在arr[k]
    }
    return obj->arr[prev];
}

//循环队列的销毁
//就是顺序表的销毁
void myCircularQueueFree(MyCircularQueue* obj) {
    free(obj->arr);
    free(obj);
    obj = NULL;
}

/**
 * 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);
*/

循环队列的概念与结构

实际中还有一种特殊的队列叫循环队列，环形队列首尾相连成环，环形队列可以使用数组实现，也可以使用循环链表实现

在这里插入图片描述

思考：队列满的情况下，为什么 Q.rear 不存储数据？

为了能使用 Q.rear = Q.front 来区别是队空还是队满，我们常常认为出现左图时的情况即为队满的情况

此时： rear+1=front

阅读全部

相关推荐

  10. 数据结构---栈和队列

    2024-07-22 03:46:02       54 阅读

最近更新

  3. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 03:46:02       52 阅读

  4. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 03:46:02       54 阅读

  9. 在Django里面运行非项目文件

    2024-07-22 03:46:02       45 阅读

  19. Python语言-面向对象

    2024-07-22 03:46:02       55 阅读

  20. 如何分清楚常见的 Git 分支管理策略Git Flow、GitHub Flow 和 GitLab Flow

    2024-07-22 03:46:02       50 阅读

热门阅读

  1. 【渗透入门】反序列化

    2024-07-22 03:46:02       14 阅读

  2. Windows图形界面(GUI)-DLG-C/C++ - 月历控件(MonthCalendar)

    2024-07-22 03:46:02       17 阅读

  3. Dijkstra

    2024-07-22 03:46:02       15 阅读

  7. B树：高效的数据存储结构

    2024-07-22 03:46:02       15 阅读

  10. newton算法实现的div的verilog

    2024-07-22 03:46:02       12 阅读

  15. Servlet会话跟踪基础

    2024-07-22 03:46:02       14 阅读

  19. 实变函数精解【6】

    2024-07-22 03:46:02       15 阅读

  21. springSecurity学习之springSecurity流程

    2024-07-22 03:46:02       14 阅读

  28. Symfony表单系统详解：构建强大且灵活的表单

    2024-07-22 03:46:02       15 阅读