数据结构基础5：栈和队列的实现。

一.栈的基本概念。

一.基本概念

1.基本概念

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

2.模拟实现

我们之前已经了解过顺序表的静态和动态，单链表——双向带头循环链表。这些线性表结构。我们想一想？如果实现栈使用一个什么样的结构作为我们的基础。

内容特性：
请添加图片描述
缓存利用：
----顺序表请添加图片描述
链表的缓存利用：
请添加图片描述

3.综上所述：

使用一个动态开辟的一个顺序表作为我们的栈的基础结构。
1.顺序表：缓存的利用率高。
2.顺序表尾插尾删的效率都比较高。
结构体定义
请添加图片描述

二.函数接口实现

1.初始化

//初始化
void StInit(struct Stack* ps)
{//不在初始化开辟空间ps->a = NULL;ps->capacity = 0;ps->top = 0;
}

2.销毁

//销毁
void StDestroy(struct Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}

3.入栈

void StPush(struct Stack* ps, Stackinttype x)
{assert(ps != NULL);//容量问题if (ps->top == ps->capacity){//扩容,开始没有进行扩容Stackinttype* tmp = (Stackinttype*)realloc(ps->a, sizeof(Stackinttype) * (ps->capacity>0?(ps->capacity)*2:4));if (tmp == NULL){perror("realloc file\n");exit(-1);}//动态开辟空间ps->a这个空间没有数据，realloc相当于malloc；ps->a = tmp;if (ps->capacity == 0){ps->capacity = 4;}else{ps->capacity = (ps->capacity) * 2;}}ps->a[ps->top] = x;ps->top++;}

4.出栈

void StPop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0assert(ps->top>0);ps->a[((ps->top)-1)] = 0;ps->top--;
}

5.返回栈顶的数据

//返回栈顶的数据
Stackinttype StTop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0,这个时候栈中是没有数据的。assert(ps->top > 0);return (ps->a[(ps->top)-1]);
}

6.返回栈中数据个数

//返回栈中数据个数
int StSize(struct Stack* ps)
{//是0就返回0；assert(ps != NULL);return ps->top;
}

7.检查栈是否为空


//检查栈是否为空
bool StEmpty(struct Stack* ps)
{assert(ps != NULL);if (ps->top == 0){return true;}else{return false;}}

三.整体带码

#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"//打印数据
void Stprint(struct Stack* ps)
{assert(ps);//assert(ps->top > 0);for (int i = 0; i < ps->top; i++){printf("%d->", ps->a[i]);}printf("栈顶\n");
}//初始化
void StInit(struct Stack* ps)
{//不在初始化开辟空间ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void StDestroy(struct Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//入栈
void StPush(struct Stack* ps, Stackinttype x)
{assert(ps != NULL);//容量问题if (ps->top == ps->capacity){//扩容,开始没有进行扩容Stackinttype* tmp = (Stackinttype*)realloc(ps->a, sizeof(Stackinttype) * (ps->capacity>0?(ps->capacity)*2:4));if (tmp == NULL){perror("realloc file\n");exit(-1);}//动态开辟空间ps->a这个空间没有数据，realloc相当于malloc；ps->a = tmp;if (ps->capacity == 0){ps->capacity = 4;}else{ps->capacity = (ps->capacity) * 2;}}ps->a[ps->top] = x;ps->top++;}
//出栈
void StPop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0assert(ps->top>0);ps->a[((ps->top)-1)] = 0;ps->top--;
}//返回栈顶的数据
Stackinttype StTop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0,这个时候栈中是没有数据的。assert(ps->top > 0);return (ps->a[(ps->top)-1]);
}//返回栈中数据个数
int StSize(struct Stack* ps)
{//是0就返回0；assert(ps != NULL);return ps->top;
}//检查栈是否为空
bool StEmpty(struct Stack* ps)
{assert(ps != NULL);if (ps->top == 0){return true;}else{return false;}}#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int Stackinttype;typedef struct Stack {Stackinttype* a;int top;int capacity;
}ST;//打印数据
void Stprint(struct Stack* ps);//初始化
void StInit(struct Stack* ps);//销毁
void StDestroy(struct Stack* ps);//入栈
void StPush(struct Stack* ps, Stackinttype x);//出栈
void StPop(struct Stack* ps);//返回栈顶的数据
Stackinttype StTop(struct Stack* ps);//返回栈中数据个数
int StSize(struct Stack* ps);//检查栈是否为空
bool StEmpty(struct Stack* ps);#define _CRT_SECURE_NO_WARNINGS 1#include"Stack.h"void test()
{ST stack;//初始化StInit(&stack);//进入数据StPush(&stack, 1);StPush(&stack, 2);StPush(&stack, 3);StPush(&stack, 4);StPush(&stack, 5);StPush(&stack, 6);Stprint(&stack);StPop(&stack);//5StPop(&stack);//4StPop(&stack);//3Stprint(&stack);//获取栈顶元素int a = StTop(&stack);printf("%d\n", a);StPop(&stack);a = StTop(&stack);printf("%d\n", a);StPush(&stack, 4);StPush(&stack, 5);StPush(&stack, 6);Stprint(&stack);//返回栈的的数据个数int number = StSize(&stack);printf("%d\n", number);//判断栈是否为空StPop(&stack);StPop(&stack);StPop(&stack);StPop(&stack);StPop(&stack);if (StEmpty(&stack)){printf("栈空了！\n");}}
int main()
{//测试test();
}

二.队列基本概念：

一.基本概念

1.基本概念:

只允许在一端进行插人数据,在另一端删除数据,插入数据的一端是队尾,删除数据的一端是队头.队尾入队头出.(first in first out).

2.模拟实现:

这里我们使用链表不去使用顺序表.
1.顺序表的删除数据,移动数据的时间复杂度是O(1).
2.试用带头单链表或者不带头的单链表都可以.
3.正常的单链表也是需要找尾解决这个问题我们需要创建两个结构体一个是节点的结构体,一个是队列的结构体,队列的结构体保存了,一个队列的头和尾的地址.
4.Queue这个结构体只需要创建一次就是一个队列这样我们
请添加图片描述

二.接口实现

所有的接口都需要判断队列这个结构体指针不可以为空。

1.初始化

1.不去多次的malloc节点，只在入队列进行节点的开辟。
2.初始化队列的个数。

//初始化
void QueueInit(Que* ps)
{assert(ps);ps->head = ps->tile = NULL;ps->size = 0;
}

2.判断队列是否为空

1.ps->tile==NULL说明队列中一个数据都没有。
2.返回bool类型的数值。

//判断队列为空
bool QueueEmpty(Que* ps)
{assert(ps);if (ps->tile == NULL){return true;}else{return false;}
}

3入队列

1.进入就要开辟节点判断节点开辟是否成功。
2.第一种情况：当队列中没有数据的时候,ps->head=ps->tile=newnode;
3.第二种情况：当队列中有数据的时候就正常队尾入数据。
4.进入数据需要++；

//入队列
void QueuePush(Que* ps,QueueDatatype x)
{assert(ps);QueN* newnode = (QueN*)malloc(sizeof(QueN));if (newnode == NULL){perror("malloc file\n");exit(-1);}newnode->data = x;newnode->next = NULL;//队列中没有数据if (ps->tile==NULL){ps->head = ps->tile = newnode;}else{ps->tile->next = newnode;ps->tile = newnode;}ps->size++;
}

4出队列

1.出去所以队列中有数据才可以出数据。
2.判断队列是否为空。
3.如果队列中没有数据的时候ps->head=ps->tile=NULL;（ps->tile)产生野指针。
4.队列中还有数据的时候，注意入队列创建节点出队列释放节点，否则会产生内存泄漏。

//出队列
void QueuePop(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));if (ps->head == ps->tile){free(ps->head);ps->head = ps->tile = NULL;}else{QueN* next = ps->head->next;free(ps->head);ps->head = next;}ps->size--;
}

5.获取队头数据

1.断言：队列是否为空
2.return ps->head->data;

//获取队头数据。
QueueDatatype QueueFront(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}

6.获取队尾数据

1.断言：队列是否为空
2.return ps->tile->data;

//获取队尾数据
QueueDatatype QueueBack(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->tile->data;
}

7.队列的销毁

1.遍历释放每一个节点从头开始。
2.是通过cur=ps->head 遍历数据的。
3.cur为空的时候，所有的节点释放完成。
4.这个时候因为我们还没有对ps->tile没有进行处理的所以产生野指针。
5.ps->head=ps->tile = NULL;ps->size = 0;

//销毁
void QueueDestor(Que* ps)
{assert(ps);QueN* cur = ps->head;while (cur){QueN* next = cur->next;free(cur);cur = NULL;cur = next;}//这个时候tile是一个野指针，指向一个已经被释放的空间ps->head=ps->tile = NULL;ps->size = 0;
}

8.获取队列有效数据个数据

1.断言：队列是否为空。
2.return ps->size;

//获取队列有效数据个数
int QueueSize(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->size;
}

三.整体代码和测试用例

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QueueDatatype;typedef struct QueueNode {QueueDatatype data;struct QueueNode* next;
}QueN;typedef struct Queue {QueN* head;QueN* tile;//队列中元素个数int size;
}Que;//队列打印
void QueuePrint(Que* ps);
//初始化
void QueueInit(Que* ps);
//销毁
void QueueDestor(Que* ps);
//入队列
void QueuePush(Que* ps,QueueDatatype x);
//出队列
void QueuePop(Que* ps);
//判断队列为空
bool QueueEmpty(Que* ps);
//获取队头数据。
QueueDatatype QueueFront(Que* ps);
//获取队尾数据
QueueDatatype QueueBack(Que* ps);
//获取队列有效数据个数
int QueueSize(Que* ps);#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"
//初始化
void QueueInit(Que* ps)
{assert(ps);ps->head = ps->tile = NULL;ps->size = 0;
}
//销毁
void QueueDestor(Que* ps)
{assert(ps);QueN* cur = ps->head;while (cur){QueN* next = cur->next;free(cur);cur = NULL;cur = next;}//这个时候tile是一个野指针，指向一个已经被释放的空间ps->head=ps->tile = NULL;ps->size = 0;
}//判断队列为空
bool QueueEmpty(Que* ps)
{assert(ps);if (ps->tile == NULL){return true;}else{return false;}
}//入队列
void QueuePush(Que* ps,QueueDatatype x)
{assert(ps);QueN* newnode = (QueN*)malloc(sizeof(QueN));if (newnode == NULL){perror("malloc file\n");exit(-1);}newnode->data = x;newnode->next = NULL;//队列中没有数据if (ps->tile==NULL){ps->head = ps->tile = newnode;}else{ps->tile->next = newnode;ps->tile = newnode;}ps->size++;
}
//出队列
void QueuePop(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));if (ps->head == ps->tile){free(ps->head);ps->head = ps->tile = NULL;}else{QueN* next = ps->head->next;free(ps->head);ps->head = next;}ps->size--;
}
//获取队头数据。
QueueDatatype QueueFront(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}
//获取队尾数据
QueueDatatype QueueBack(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->tile->data;
}//获取队列有效数据个数
int QueueSize(Que* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->size;
}

满足队列的特性:
1.队尾入数据.
2.队头出数据并且打印队头的数据.
3.在打印函数传参需要判断队列是否为空.

#define _CRT_SECURE_NO_WARNINGS 1#include"Queue.h"void test()
{Que st;//初始化QueueInit(&st);//入队列QueuePush(&st, 1);QueuePush(&st, 2);QueuePush(&st, 3);QueuePush(&st, 4);QueuePush(&st, 5);while (!QueueEmpty(&st)){printf("%d->", QueueFront(&st));QueuePop(&st);}QueueDestor(&st);}
int main()
{test();return 0;
}

三.栈和队列的一些面试题目：

题目一：

请添加图片描述
题目链接

主要思路：

1.上面实现的栈可以直接拿过来使用，修改int为char
2.根据栈后进先出的性质。
3.遍历字符串‘{’ ‘[’ ‘(’ 入栈。
4.进行匹配的对应，‘}’ ‘]’ ‘)’ 就应该进行判断，判断获取栈顶元素，判断是否匹配。如果不匹配就返回false。匹配之后删除栈顶元素。
5.只有一个类似‘}’右边的，应该在判断‘}’ ‘]’ ‘)’ 的部分里去判断栈中是否有数据如果没有数据那么有右没有左直接return true）
6.这个字符串到\0结束，如果栈中没有数据。说明这个字符串的符号是匹配的。
代码实现：

typedef char Stackinttype;typedef struct Stack {Stackinttype* a;int top;int capacity;
}ST;
//初始化
void StInit(struct Stack* ps)
{//不在初始化开辟空间ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//销毁
void StDestroy(struct Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void StPush(struct Stack* ps, Stackinttype x)
{assert(ps != NULL);//容量问题if (ps->top == ps->capacity){//扩容,开始没有进行扩容Stackinttype* tmp = (Stackinttype*)realloc(ps->a, sizeof(Stackinttype) * (ps->capacity>0?(ps->capacity)*2:4));if (tmp == NULL){perror("realloc file\n");exit(-1);}//动态开辟空间ps->a这个空间没有数据，realloc相当于malloc；ps->a = tmp;if (ps->capacity == 0){ps->capacity = 4;}else{ps->capacity = (ps->capacity) * 2;}}ps->a[ps->top] = x;ps->top++;}
//出栈
void StPop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0assert(ps->top>0);ps->a[((ps->top)-1)] = 0;ps->top--;
}//返回栈顶的数据
Stackinttype StTop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0,这个时候栈中是没有数据的。assert(ps->top > 0);return (ps->a[(ps->top)-1]);
}//返回栈中数据个数
int StSize(struct Stack* ps)
{//是0就返回0；assert(ps != NULL);return ps->top;
}//检查栈是否为空
bool StEmpty(struct Stack* ps)
{assert(ps != NULL);if (ps->top == 0){return true;}else{return false;}
}
bool isValid(char * s){ST stack;//初始化StInit(&stack);//入栈char* cur=s;while(*cur){char cmp=(*cur);if((cmp=='[')||(cmp=='{')||(cmp=='(')){StPush(&stack,cmp);}//栈中没有数据，一个右的可以进入的。else if((cmp=='}')||(cmp==']')||(cmp==')')){//判断栈为空的情况if(StEmpty(&stack)){return false;}//获取栈顶的数据char tmp = StTop(&stack);if ((((cmp == '}') && (tmp != '{'))) ||(((cmp == ']') && (tmp != '['))) ||(((cmp == ')') && (tmp != '(')))){return false;}//出栈 StPop(&stack);}cur++;}//假设只有一个左边的{}，[],().int number=StSize(&stack);if(number==0){return true;}else{return false;}
}

题目二:

请添加图片描述

主要思路：

请添加图片描述
题目链接

typedef int QueueDatatype;//每一个节点
typedef struct QueueNode {QueueDatatype data;struct QueueNode* next;
}QueN;//队列结构体类型
typedef struct Queue {QueN* head;QueN* tile;int size;
}QU;//初始化
void QueueInit(QU* ps);
//判断队列是否为空
bool QueueEmpty(QU* ps);
//队尾进入
void QueuePush(QU* ps, QueueDatatype x);
//队头出数据
void QueuePop(QU* ps);
//获取队头数据
QueueDatatype QueueFront(QU* ps);
//获取队尾数据
QueueDatatype QueueBack(QU* ps);
//获取有效数据个数
int Queuesize(QU* ps);
//销毁队列
void QueueDestory(QU* ps);//初始化
void QueueInit(QU* ps)
{//给空指针不开辟新的节点assert(ps);ps->head = ps->tile = NULL;ps->size = 0;
}//判断队列是否为空
bool QueueEmpty(QU* ps)
{return ps->head==NULL;
}//队尾进入
void QueuePush(QU* ps, QueueDatatype x)
{assert(ps);//1.进入一定需要开辟节点的。QueN* newnode = (QueN*)malloc(sizeof(QueN));if (newnode == NULL){perror("malloc file\n");exit(-1);}newnode->next = NULL;newnode->data = x;if (ps->tile==NULL){ps->head = ps->tile = newnode;}else{ps->tile->next = newnode;ps->tile = newnode;}ps->size++;
}
//队头出数据
void QueuePop(QU* ps)
{assert(ps);assert(!QueueEmpty(ps));if(ps->head==ps->tile){free(ps->head);ps->head=ps->tile=NULL;}else{QueN* next=ps->head->next;free(ps->head);ps->head=next;}ps->size--;
}
//获取队头数据
QueueDatatype QueueFront(QU* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->head->data;
}
//获取队尾数据
QueueDatatype QueueBack(QU* ps)
{assert(ps);assert(!QueueEmpty(ps));return ps->tile->data;
}
//获取有效数据个数
int Queuesize(QU* ps)
{assert(ps);return ps->size;
}
//销毁队列
void QueueDestory(QU* ps)
{assert(ps);QueN* cur = ps->head;while (cur){QueN* next = cur->next;free(cur);cur = NULL;cur = next;}//容易产生野指针ps->head = ps->tile = NULL;ps->size=0;
}typedef struct {QU s1;QU s2;
} MyStack;MyStack* myStackCreate() {MyStack* pst=(MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->s1);QueueInit(&pst->s2);return pst;
}void myStackPush(MyStack* obj, int x) {//1.两个都为空，有一个为空，一个不为空。if(!QueueEmpty(&obj->s1)){QueuePush(&obj->s1,x);}else{QueuePush(&obj->s2,x);}
}int myStackPop(MyStack* obj) {//1.假设有和没有数据的队列,确定有和没有。QU* have=&obj->s1;QU* nonhave=&obj->s2;if(QueueEmpty(&obj->s1)){have=&obj->s2;nonhave=&obj->s1;}//2.倒数据while(Queuesize(have)>1){//1.获取数据int k = QueueFront(have);//2.pop数据QueuePop(have);//2.进入另一个队列QueuePush(nonhave,k);}//1.获取数据int k = QueueFront(have);//2.pop数据QueuePop(have);return k;
}int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->s1)){return QueueBack(&obj->s1);}else{return QueueBack(&obj->s2);}
}bool myStackEmpty(MyStack* obj) {return ((QueueEmpty(&obj->s1))&&(QueueEmpty(&obj->s2)));
}void myStackFree(MyStack* obj) {QueueDestory(&obj->s1);QueueDestory(&obj->s2);free(obj);
}

题目三:

请添加图片描述
题目链接

主要思路：

请添加图片描述

1.使用队列实现栈是需要来回倒数据获取最后一个。
2.我们使用栈实现队列你需要规定哪一个是用来进入数据的push栈，和用来出数据的pop栈。
3.只有当Pop栈数据为空的时候才可以把push栈的数据倒到pop栈里面。
4.peek和pop两个函数的区别，一个删除队头一个不删除队头，如果上来使用peek那么peek函数是需要倒数据这个操作，如果没有这个操作我们获取不到正确的队头数据的。！！！！

typedef int Stackinttype;typedef struct Stack {Stackinttype* a;int top;int capacity;
}ST;
//初始化
void StInit(struct Stack* ps);//销毁
void StDestroy(struct Stack* ps);//入栈
void StPush(struct Stack* ps, Stackinttype x);//出栈
void StPop(struct Stack* ps);//返回栈顶的数据
Stackinttype StTop(struct Stack* ps);//返回栈中数据个数
int StSize(struct Stack* ps);//检查栈是否为空
bool StEmpty(struct Stack* ps);//初始化
void StInit(struct Stack* ps)
{//不在初始化开辟空间ps->a = NULL;ps->capacity = 0;ps->top = 0;
}//销毁
void StDestroy(struct Stack* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}
//入栈
void StPush(struct Stack* ps, Stackinttype x)
{assert(ps != NULL);//容量问题if (ps->top == ps->capacity){//扩容,开始没有进行扩容Stackinttype* tmp = (Stackinttype*)realloc(ps->a, sizeof(Stackinttype) * (ps->capacity>0?(ps->capacity)*2:4));if (tmp == NULL){perror("realloc file\n");exit(-1);}//动态开辟空间ps->a这个空间没有数据，realloc相当于malloc；ps->a = tmp;if (ps->capacity == 0){ps->capacity = 4;}else{ps->capacity = (ps->capacity) * 2;}}ps->a[ps->top] = x;ps->top++;}
//出栈
void StPop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0assert(ps->top>0);ps->a[((ps->top)-1)] = 0;ps->top--;
}//返回栈顶的数据
Stackinttype StTop(struct Stack* ps)
{assert(ps != NULL);//访问数组空间下标至少是0,这个时候栈中是没有数据的。assert(ps->top > 0);return (ps->a[(ps->top)-1]);
}//返回栈中数据个数
int StSize(struct Stack* ps)
{//是0就返回0；assert(ps != NULL);return ps->top;
}//检查栈是否为空
bool StEmpty(struct Stack* ps)
{assert(ps != NULL);if (ps->top == 0){return true;}else{return false;}}typedef struct {ST Pushst;ST Popst;
} MyQueue;MyQueue* myQueueCreate() {MyQueue* pq=(MyQueue*)malloc(sizeof(MyQueue));if(pq==NULL){perror("malloc file\n");exit(-1);}StInit(&pq->Pushst);StInit(&pq->Popst);return pq;
}void myQueuePush(MyQueue* obj, int x) {assert(obj);StPush(&obj->Pushst,x);
}int myQueuePop(MyQueue* obj) {assert(obj);if(StEmpty(&obj->Popst)){//3.倒一下顺序int sz=StSize(&obj->Pushst);while(sz--){int x=StTop(&obj->Pushst);StPop(&obj->Pushst);StPush(&obj->Popst,x);}}int x=StTop(&obj->Popst);StPop(&obj->Popst);return x;
}int myQueuePeek(MyQueue* obj) {assert(obj);if(StEmpty(&obj->Popst)){//3.倒一下顺序int sz=StSize(&obj->Pushst);while(sz--){int x=StTop(&obj->Pushst);StPop(&obj->Pushst);StPush(&obj->Popst,x);}}return StTop(&obj->Popst); 
}bool myQueueEmpty(MyQueue* obj) {return (StEmpty(&obj->Pushst) && StEmpty(&obj->Popst));
}void myQueueFree(MyQueue* obj) {StDestroy(&obj->Pushst);StDestroy(&obj->Popst);free(obj);
}

题目四:

请添加图片描述
题目链接

主要思路一：

请添加图片描述

//节点的结构体
typedef struct list{struct list* next;struct list* prev;int data;
}Li;//队列的结构体
typedef struct {Li* head;Li* tile;int size;int capcity;
} MyCircularQueue;//自己的初始化函数需要构建+连接
void CirQueuInit(MyCircularQueue* pst,int k)
{assert(pst);//多一个节点：int n=k+1;Li* newnode=(Li*)malloc(sizeof(Li));newnode->prev=NULL;newnode->next=NULL;newnode->data=0;//节点的默认处理：if(pst->head==pst->tile){pst->head=pst->tile=newnode;}//前面这个部分构建我们的第一个节点，第一个节点head和tile在同一个位置。while(k--)//k个节点的构建：{Li* newnode=(Li*)malloc(sizeof(Li));newnode->prev=NULL;newnode->next=NULL;newnode->data=0;//数据的前后连接+tile的移动。pst->tile->next=newnode;newnode->prev=pst->tile;pst->tile=newnode;}//结尾的时候，tile到了k+1个节点和头的前后连接。pst->tile->next=pst->head;pst->head->prev=pst->tile;pst->tile=pst->head;//初始化队列的数据pst->capcity=n-1;pst->size=0;
}MyCircularQueue* myCircularQueueCreate(int k) {
MyCircularQueue* pst=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//初始化一下这个队列。CirQueuInit(pst,k);return pst;
}//判断空和满对于队头插数据和队尾删数据是比较重要的。
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {//使用头尾节点的位置和有效数据个数比较判断的结果是相同的。if((obj->head==obj->tile)&&(obj->size==0)){return true;}else{return false;}
}bool myCircularQueueIsFull(MyCircularQueue* obj) {//两个判断条件可以任意出现一个也可以同时出现。if((obj->head->prev==obj->tile)&&(obj->size==obj->capcity)){return true;}else{return false;}
}
//添加函数
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if(myCircularQueueIsFull(obj))return false;obj->tile->data=value;obj->tile=obj->tile->next;obj->size++;return true;
}
//删除函数
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))return false;obj->head->data=0;obj->head=obj->head->next;obj->size--;return true;
}//取队头数据
int myCircularQueueFront(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return obj->head->data;
}
//取队尾数据，使用双向循环。
int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj)){return -1;}return ((obj->tile)->prev)->data;
}//有节点的初始化就有节点的销毁防止内存泄漏
void CirQueuDestory(MyCircularQueue* pst)
{Li* cur=pst->head;int n=pst->capcity;while(n--){Li* next=cur->next;free(cur);cur=next;}pst->size=0;
}
//释放队列：
void myCircularQueueFree(MyCircularQueue* obj) {//释放内部节点CirQueuDestory(obj);//释放外部队列。free(obj);
}

主要思路二：

优化部分：
1.单链表这个结构体的双向循环构建和销毁是比较麻烦的。
2.开辟的空间比较多，单链表的效率比顺序表要底。
3.尝试使用顺序表解决这个循环队列的问题。
4.判断空和满的时候的计算不要改变原来的数值。
5.获取数据使用的判断空和满的函数使用需要细心。

请添加图片描述
请添加图片描述

typedef struct {int* queu;//存下表的。int head;int tile;int k;
} MyCircularQueue;MyCircularQueue* myCircularQueueCreate(int k) {//创建一个节点：MyCircularQueue* obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));int* newhead=(int*)malloc(sizeof(int)*(k+1));if(newhead==NULL){perror("malloc file\n");exit(-1);}//一个顺序表obj->queu=newhead;//其他值的初始化obj->head=0;obj->tile=0;obj->k=k;return obj;
}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {assert(obj);if(obj->head==obj->tile){return true;}else{return false;}
}bool myCircularQueueIsFull(MyCircularQueue* obj) {assert(obj);//作为判断使用不应该改变数值的。int k=(((obj->tile)+1)%((obj->k)+1));if(obj->head==k){return true;}else{return false;}
}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {assert(obj);if(myCircularQueueIsFull(obj))return false;else{(obj->tile)%=((obj->k)+1);obj->queu[obj->tile]=value;obj->tile++;(obj->head)%=((obj->k)+1);}return true;  
}bool myCircularQueueDeQueue(MyCircularQueue* obj) {assert(obj);if(myCircularQueueIsEmpty(obj))return false;else{(obj->head)%=((obj->k)+1);obj->head++;(obj->head)%=((obj->k)+1);}  return true;
}int myCircularQueueFront(MyCircularQueue* obj) {assert(obj);//队列为空才会返回-1if(myCircularQueueIsEmpty(obj))return -1;else{return obj->queu[obj->head];}
}int myCircularQueueRear(MyCircularQueue* obj) {assert(obj);//队列为空才会返回-1.if(myCircularQueueIsEmpty(obj))return -1;else{return obj->queu[((obj->tile)-1)];}
}void myCircularQueueFree(MyCircularQueue* obj) {assert(obj);free(obj->queu);obj->head=0;obj->tile=0;obj->k=0;free(obj);
}

希望文章可以帮助到大家！！

我会继续写出更加优质的文章的

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/86903.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

案例13 Spring MVC参数传递案例

案例13 Spring MVC参数传递案例

基于Spring MVC实现HttpServletRequest、基本数据类型、Java Bean、数组、List、Map、JSON方式的参数传递。 1. 创建项目 选择Maven快速构建web项目&#xff0c;项目名称为case13-springmvc02。 2. 配置Maven依赖 <?xml version"1.0" encoding"UTF-8&quo…
阅读更多...
分布式Redis详解

分布式Redis详解

目录 前言安装redis的俩种方法Redis 与 MySQL的区别Redis可以实现那些功能Redis常用的数据类型有序列表的底层是如何实现的?什么是跳跃表 Redis在Spring中的使用Redis 中为什么单线程比多线程快Redis的分布式锁如何实现Redis 分布式锁可能出现的问题Redis保持数据不丢失的方式…
阅读更多...
【LeetCode-简单】剑指 Offer 29. 顺时针打印矩阵（详解）

【LeetCode-简单】剑指 Offer 29. 顺时针打印矩阵（详解）

题目 输入一个矩阵&#xff0c;按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 1&#xff1a; 输入&#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]] 输出&#xff1a;[1,2,3,6,9,8,7,4,5]示例 2&#xff1a; 输入&#xff1a;matrix [[1,2,3,4],[5,6,7,8],[9,10,1…
阅读更多...
CentOS虚拟机 NAT模式连网

CentOS虚拟机 NAT模式连网

1、查看本地VMnet8的网络信息 cmd ipconfig2、编辑VMware虚拟网络编辑器 &#xff08;1&#xff09;打开网络编辑器 &#xff08;2&#xff09;打开NET设置 &#xff08;3&#xff09;修改网络配置 修改子网ip和windows查到的ip的最后一位不一样就行和子网掩码照抄 3、在VMw…
阅读更多...
SQL | 计算字段

SQL | 计算字段

7-创建计算字段 7.1-计算字段 存储在数据库中的数据一般不是我们所需要的字段格式&#xff0c; 需要公司名称&#xff0c;同时也需要公司地址&#xff0c;但是这两个数据存储在不同的列中。 省&#xff0c;市&#xff0c;县和邮政编码存储在不同的列中&#xff0c;但是当我们…
阅读更多...
keil下载程序具体过程：概述

keil下载程序具体过程：概述

一、前言 keil下载程序具体过程将由一系列的博客组成&#xff0c;将深入探讨keil这种IDE下载镜像文件时具体做了哪些事情。我们平常下载镜像的时候&#xff0c;只是点击了一下Download按钮&#xff0c;剩下的都由keil替代我们完成了。本系列博客将揭示这一过程&#xff0c;keil…
阅读更多...
事件循环原理

事件循环原理

事件循环 浏览器的进程模型 何为进程&#xff1f; 程序运行需要有它自己专属的内存空间&#xff0c;可以把这块内存空间简单的理解为进程 每个应用至少有一个进程&#xff0c;进程之间相互独立&#xff0c;即使要通信&#xff0c;也需要双方同意。 何为线程&#xff1f; 有…
阅读更多...
【Kafka】1.Kafka简介及安装

【Kafka】1.Kafka简介及安装

目 录 1. Kafka的简介1.1 使用场景1.2 基本概念 2. Kafka的安装2.1 下载Kafka的压缩包2.2 解压Kafka的压缩包2.3 启动Kafka服务 1. Kafka的简介 Kafka 是一个分布式、支持分区&#xff08;partition&#xff09;、多副本&#xff08;replica&#xff09;、基于 zookeeper 协调…
阅读更多...
【图像恢复】基于交替乘子方法(ADMM)图像恢复算法研究[固定点收敛和应用]（Matlab代码实现）

【图像恢复】基于交替乘子方法(ADMM)图像恢复算法研究[固定点收敛和应用]（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
HarmonyOS/OpenHarmony应用开发-ArkTS语言渲染控制概述

HarmonyOS/OpenHarmony应用开发-ArkTS语言渲染控制概述

ArkUI通过自定义组件的build()函数和builder装饰器中的声明式UI描述语句构建相应的UI。 在声明式描述语句中开发者除了使用系统组件外&#xff0c;还可以使用渲染控制语句来辅助UI的构建&#xff0c;这些渲染控制语句包括控制组件是否显示的条件渲染语句&#xff0c;基于数组数…
阅读更多...
Xcode 基座打包

Xcode 基座打包

Xcode基座打包-APP更新版本内容无效 问题&#xff1a;解决&#xff1a; 问题&#xff1a; 使用xcode基座打包之后&#xff0c;上传到appstore进行提审发布。 用户在appstore商城进行更新下载&#xff0c;打开更新后的APP发现版本号是最新的&#xff0c;APP里面的其他内容还是上…
阅读更多...
linux环形缓冲区kfifo实践2：配合等待队列使用

linux环形缓冲区kfifo实践2：配合等待队列使用

基础 struct __wait_queue_head {spinlock_t lock;struct list_head task_list; }; typedef struct __wait_queue_head wait_queue_head_t; 初始化等待队列&#xff1a;init_waitqueue_head 深挖init_waitqueue_head宏的定义可知&#xff0c;传递给它的参数q是一个wait_queu…
阅读更多...
docker删除容器时报错：Error response from daemon: reference does not exist

docker删除容器时报错：Error response from daemon: reference does not exist

前言 之前使用的docker版本太低了&#xff0c;升级高版本docker之后的错误。 低版本docker&#xff08;1.30.1&#xff09;中的镜像有&#xff1a;golang、mysql&#xff0c;将docker升级为24.0.5并新拉取mysql最新版本之后&#xff0c;执行docker images命令&#xff0c;发现…
阅读更多...
【面试专题】Java核心基础篇①

【面试专题】Java核心基础篇①

&#x1f4c3;个人主页&#xff1a;个人主页 &#x1f525;系列专栏&#xff1a;Java面试专题 目录 1.面向对象的三大特性&#xff1f;分别解释下&#xff1f; 2.介绍一下Java的数据类型 3.说一说重写与重载的区别 4.说一说你对static关键字的理解 5.static修饰的类能不能…
阅读更多...
neo4j查询语言Cypher详解(二)--Pattern和类型

neo4j查询语言Cypher详解(二)--Pattern和类型

Patterns 图形模式匹配是Cypher的核心。它是一种用于通过应用声明性模式从图中导航、描述和提取数据的机制。在MATCH子句中&#xff0c;可以使用图模式定义要搜索的数据和要返回的数据。图模式匹配也可以在不使用MATCH子句的情况下在EXISTS、COUNT和COLLECT子查询中使用。 图…
阅读更多...
百川智能发布首个530亿参数闭源大模型，今年追上GPT-3.5

百川智能发布首个530亿参数闭源大模型，今年追上GPT-3.5

4月官宣创业&#xff0c;6月15日发布第一款7B开源模型&#xff0c;7月11日发布第二款13B、130亿参数开源模型。 平均保持2个月一个版本发布速度&#xff0c;8月8日&#xff0c;百川智能发布了创业以来的首个530亿参数闭源大模型——Baichuan-53B&#xff08;以下简称“53B”&a…
阅读更多...
（十五）大数据实战——hive的安装部署

（十五）大数据实战——hive的安装部署

前言 Hive是由Facebook开源&#xff0c;基于Hadoop的一个数据仓库工具&#xff0c;可以将结构化的数据文件映射为一张表&#xff0c;并提供类SQL查询功能。本节内容我们主要介绍一下hive的安装与部署的相关内容。 正文 上传hive安装包到hadoop101服务器/opt/software目录 解…
阅读更多...
承接各种设计

承接各种设计

小弟985研究生毕业&#xff0c;目前攻读读博士&#xff0c;可做各种设计&#xff0c;包括但不限于Matlab 电力电子/电气工程&#xff0c;matlab/simulink 电气专业仿真MATLAB 电气工程专业&#xff0c;matlab建模 电力电子&#xff0c;电气工程&#xff0c;电力系统&#xff0c…
阅读更多...
一文读懂什么是Byzer

一文读懂什么是Byzer

目录 一、什么是Byzer? 二、Byzer特性 2.1 语法特性 2.2 数据的管理特性 2.3 支持自定义函数拓展Byzer语法 三、Byzer有哪些功能&#xff1f; 3.1 Byzer-Lang语言特性 3.1.1强大的数据处理能力 3.1.2内置机器学习算法 3.2 Byzer-Lang支持权限控制 3.3 Byzer-LLM拓展…
阅读更多...
Stable Diffusion AI绘图教学

Stable Diffusion AI绘图教学

课程介绍下载 这门课程将教授学生使用Stable Diffusion AI绘图工具进行数据可视化和图形设计。学生将学习基本的绘图原理、数据分析技巧&#xff0c;以及如何使用Stable Diffusion AI创建高质量的图表和可视化作品。通过实践项目和案例研究&#xff0c;学生将提升绘图技能&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023