数据结构——栈和队列

文章目录

• 一.栈
• • 1.栈介绍
  • 2.栈的定义
  • 3.栈的各种操作
  • • (1)”InitStack”初始化栈
    • (2)”PushTop”从栈顶插入数据
    • (3)”PopTop”弹出栈顶数据
    • (4)”ReadTop”读取栈顶数据
    • (5)”PopTop”弹出栈顶数据
    • “test”测试以上代码
    • (6)”ReadBack”读取栈底数据
    • (7)”IsFullStack”判断栈是否已满
    • (8)”DestroyStack”销毁栈
• 二.队列
• • 1.队列介绍
  • 2.队列的定义
  • 3.队列需实现的接口
  • • （1）”test”传参与测试
    • （2）”InitQueue”初始化
    • （3）”PushQueue”入队
    • （4）”Destroy”销毁队列
    • （5）”PopQueue”弹出队头数据
    • （6）”IsEmptyQueue”判断队列是否为空
    • （7）”FrontQueue”获取队头元素
    • （8）”BackQueue”获取队尾元素
  • 4.循环队列
• 三.总结
• • 游戏开发中数据结构的应用

一.栈

1.栈介绍

在计算机这个学科中有两个栈，一个是软件层面的栈，一个是硬件层面的栈

软件的栈是指一种“后入先出(Last In First Out)”数据结构，用于在内存中存储、管理数据
硬件的栈是指,在计算机硬件中，由CPU管理的一块特殊的内存区域，用于支持程序的执行

学习栈和队列需要用到顺序表和链表，不熟悉的可以在这篇文章里看一看
链表与顺序表

本篇文章介绍的是数据结构中的栈，并非硬件的栈
栈底层由顺序表或链表实现，栈分为栈顶和栈底，栈顶用于插入数据和弹出数据，栈底没啥用(也许唯一的作用就是读取一下栈底的数据了)
从栈顶插入数据被称为压栈或入栈或进栈
从栈顶删除(也叫弹出)数据被称为出栈或弹栈
这个栈你可以把它想象成一个瓶子,咱们向瓶子里放东西不都是从瓶口向里面放,然后再从瓶口向外拿嘛,
咱从瓶子里拿东西的时候得先拿 后进去的东西吧,如果你不把这些后进的拿走,那怎么可能拿得到 先进瓶子的东西呢,先进的东西 被 后进的压在下面呀

出数据的顺序应为4 3 2 1
从栈里面拿数据一定得注意顺序!!!,你要满足后进先出的规则(可以进一个出一个)
来看道题

现有一栈,入数据的顺序为5 6 7 8,那么出数据时不可能的顺序是 ( )
A.8 7 6 5
B.5 6 7 8
C.7 8 5 6
D.6 5 8 7

答案是C

试想一下如果使用顺序表来实现栈，那么我们应该使用顺序表的哪一端用来充当栈顶呢？

从效率上来讲，更推荐使用顺序表的尾来充当栈顶，因为顺序表尾插的效率很高，而头插效率就很低了.用链表实现也是一样的道理，哪里效率高就用哪里充当栈顶。

2.栈的定义

struct Stack{inta;//数据int size;//有效数据个数int capacity;//容量};

为了方便使用给他重命名一下

typedef int SDataType;typedef struct Stack{SDataType* a;//数据int size;//有效数据个数int capacity;//容量}Stack;

3.栈的各种操作

栈是用于存储数据的,所以他的各种接口与链表的各种接口也大差不差

void InitStack(Stack* stack);//初始化栈void PushTop(Stack* stack, SDataType x);//从栈顶插入数据void PopTop(Stack* stack);//从栈底删除数据SDataType ReadTop(Stack* stack);//读取栈顶数据SDataType ReadBack(Stack* stack);//读取栈底数据bool IsEmptyStack(Stack* stack);//判断栈是否为空bool IsFullStack(Stack* stack);//判断栈是否已满void DestroyStack(Stack* stack);//销毁栈

(1)”InitStack”初始化栈

void InitStack(Stack* stack){//与链表一样，你连个栈类型的变量都没有还谈什么初始化assert(stack);stack->a = NULL;stack->capacity = stack->size = 0;}

(2)”PushTop”从栈顶插入数据

void PushTop(Stack* stack, SDataType x){//与链表一样，你连个栈类型的变量都没有还谈什么插入数据assert(stack);//防止扩容失败，原数据被覆盖if (stack->size == stack->capacity)//这个判断一定要加，否则你每调用一次Pushcapacity就会扩大一次{int newcapacity = stack->capacity == 0 " />4 : stack->capacity * 2;SDataType* tmp = (SDataType*)realloc(stack->a, sizeof(SDataType) * newcapacity);if (tmp == NULL){perror("PushTop :: realloc : fail");return;}stack->capacity = newcapacity;stack->a = tmp;}stack->a[stack->size] = x;//从栈顶插入数据stack->size++;}

(3)”PopTop”弹出栈顶数据

bool IsEmptyStack(Stack* stack){assert(stack);return stack->size == 0;//为NULL就返回真，不为空返回假}

(4)”ReadTop”读取栈顶数据

SDataType ReadTop(Stack* stack){assert(stack);//要返回栈顶数据这个栈首先得不为空if (!IsEmptyStack(stack)){//我们说了，顺序表尾部是栈顶return stack->a[stack->size - 1];//返回栈顶数据}return -1;//栈中无数据}

(5)”PopTop”弹出栈顶数据

//从栈顶删除(也叫弹出)数据被称为 出栈或弹栈void PopTop(Stack* stack){assert(stack);//要删除数据首先栈中得有数据if (!IsEmptyStack(stack)){stack->size--;}else{printf("栈已为空\n");}}

“test”测试以上代码

void test(){Stack s;InitStack(&s);PushTop(&s, 1);PushTop(&s, 2);PushTop(&s, 3);PushTop(&s, 4);PushTop(&s, 5);//看看扩容是否正确PushTop(&s, 6);PushTop(&s, 7);PushTop(&s, 8);PushTop(&s, 9);//读取栈，你可以把这个操作封装成函数，我这里就不搞了//有多少个数据读多少次while (s.size){printf("%d ", ReadTop(&s));PopTop(&s);//从这个栈中读取数据很特殊，// 因为每读一个数据都需要把这个数据从栈顶弹出才能读取下一个// 所以每次从栈顶读完数据都需要Pop一下把栈顶数据删除}}

我非常建议写完一段代码就写几个测试检查一下写的对不对！！！不要全都写完了才检查，到时候一测试，代码崩溃了你也崩溃了！！！
测试时要尽量想一些极端情况，例如边界处理
对于所有的插入和删除操作最好都测试一下为空的情况

(6)”ReadBack”读取栈底数据

SDataType ReadBack(Stack* stack){assert(stack);if (!IsEmptyStack(stack)){return stack->a[0];//顺序表头就是栈底}else{printf("栈中无数据\n");return -1;}}

(7)”IsFullStack”判断栈是否已满

bool IsFullStack(Stack* stack){assert(stack);//有效数据个数和数组空间大小相同就代表满了return stack->size == stack->capacity;//满了返回真，不满返回假}

(8)”DestroyStack”销毁栈

void DestroyStack(Stack* stack){assert(stack);free(stack->a);stack->a = NULL;stack->capacity = stack->size = 0;}

二.队列

1.队列介绍

队列也是一种数据结构，它与栈正好相反，它是一种先进先出(First In First Out)的数据结构.
队列分为队头和队尾
向队尾插入数据称为入队
从队头出数据成为出队
这个队列顾名思义,就像排队一样,如果有新的人来了,那他就得在队尾,你不能让他去队伍中间或队头吧,那叫插队.
如果有人要离开就得从队头离开(但你硬要从队尾离开也没办法,挺合理的,对吧?)

队列也可用顺序表或链表实现,这里队列用链表,上面的栈使用顺序表
那么使用链表的队列应该从哪端入,哪端出效率高呢” />

2.队列的定义

//队列与栈一样可以选择数组、双向链表、单链表实现// 另外还可以用栈实现队列，栈也可以用队列实现，但效率都很低// 证明栈和队列是相同的// //此次选则单链表实现typedef int QDataType;typedef struct QueueNode{QDataType val;struct QueueNode* next;}QN;//队列//把指向队列头和尾的指针封装成了一个结构体typedef struct QHT{struct QueueNode* head;//指向队列头int size;//记录当前数据总数struct QueueNode* tail;//指向队列尾}QHT;

3.队列需实现的接口

void InitQueue(QHT* point);//初始化void Destroy(QHT* queue);//销毁//void PushQueue(QN* queue, QN* tail,QDataType x);//队列要先进先出，尾进头出，所以要有一个指向尾的指针，否则时间复杂度为O(N)//这里传两个指针看着很怪,所以用一个结构体把头和尾封装起来void PushQueue(QHT*, QDataType x);//队尾入队列void PopQueue(QHT* queue);//队头出队列bool IsEmptyQueue(QHT* queue);//判断队列是否为NULLQDataType BackQueue(QHT* queue);//获取队列尾部元素QDataType FrontQueue(QHT* queue);//获取队列头部元素

这边的传参为什么不是下面这个QN类型而是QHT类型呢？这QN类型明明才是是对队列的定义。

typedef struct QueueNode{QDataType val;struct QueueNode* next;}QN;//队列

还记不记得单链表，在对单链表传参的时候是不是需要定义一个链表结构类型的指针，然后传递这个指针的地址，像这样

void test(){ListNode* list = NULL;//定义链表类型的指针PushList(&list,1);//插入节点}

在队列中不传递QN的队列类型的原因跟这个是一样的，在这个链表中，需要一个指针来标记链表头的位置，所以需要在函数外定义一个指向链表头的指针。
而在上面定义的QHT结构中，它的成员变量是QN类型的，所以我们只需要传递QHT类型的参数就可以使他的成员指向链表头，这样就有了指向链表头的指针，而因为我们需要一个指向队头一个指向队尾两个指针，所以才会把它封装成一个结构体，若不想用结构体那下面这个方法与它也是等价的

void test1(){QN* head = NULL;//指向队头QN* tail = NULL;//指向队尾PushQueue(&head, &tail, 1);//在队列中插入数据}

（1）”test”传参与测试

这个测试是极简版，你们最好多测点，这里主要还是解释传参的问题

void test(){QHT ht;//定义指向链表头和尾的指针//创建变量编译器会自动为其成员开辟适当空间。若创建指针需手动开辟InitQueue(&ht);PushQueue(&ht, 1);PushQueue(&ht, 2);PushQueue(&ht, 3);PushQueue(&ht, 4);}

（2）”InitQueue”初始化

void InitQueue(QHT* point)//初始化
{
assert(point);
point->head = NULL;
point->tail = NULL;
point->size = 0;
}

（3）”PushQueue”入队

void PushQueue(QHT* ht, QDataType x){assert(ht);QN* tmp = (QN*)malloc(sizeof(QN));if (tmp == NULL){perror("PushQueue :: malloc\n");return;}tmp->val = x;tmp->next = NULL;if (ht->head == NULL){ht->head = tmp;ht->tail = tmp;}else{ht->tail->next = tmp;ht->tail = tmp;}ht->size++;}

（4）”Destroy”销毁队列

void Destroy(QHT* ht)//销毁{assert(ht);QN* del = ht->head;while (del){ht->head = ht->head->next;free(del);del = ht->head;}InitQueue(ht);}

（5）”PopQueue”弹出队头数据

void PopQueue(QHT* ht){assert(ht && ht->head);//无节点QN* del = ht->head;ht->head = ht->head->next;//head指向下一个节点free(del);if (ht->head == NULL)//若head前进后等于NULL，证明只有一个节点{ht->tail = NULL;}ht->size--;}

（6）”IsEmptyQueue”判断队列是否为空

bool IsEmptyQueue(QHT* ht){assert(ht);return ht->head == NULL;//没数据返回真,有数据返回假}

（7）”FrontQueue”获取队头元素

QDataType FrontQueue(QHT* queue)//获取队列头部元素{assert(queue && queue->head);return queue->head->val;}

（8）”BackQueue”获取队尾元素

QDataType BackQueue(QHT* queue)//获取队列尾部元素{assert(queue && queue->tail);return queue->tail->val;}

4.循环队列

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

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

在力扣上有关于循环队列的题和官方讲解，感兴趣的可以去看看
力扣：循环队列
顺带说一句官方题解中的mod是取模(%)的意思，也就是取余数
例如：

根据以上可知，队列判空的条件是 front == rear, 而队列的判满条件是
(rear +1) mod capacity == front

这里他加上一个取模是为了防止越界的情况出现，如果不取模可以这样写

// //队列是否已满// if((rear+1) % (capacuty) == front)// {// return true;//满就返回true// }//rear指向队列最后一个有效元素的下一个位置，队列的空间个数也始终比有效元素个数多一个if(rear+1>= capacity)//出现这种情况就证明队列尾已经超出数组长度了，//这时候如果要判满，那就得看队列头是否在数组头的位置，在数组头那就是满了{if(0 == obj->front){return true;}}else if(obj->tail + 1 == obj->front){return true;}return false;

三.总结

队列和栈都是比较简单的数据结构，他们的主要目的还是为了存储数据
队列是先进先出，队列适宜使用链表
栈是先进后出,栈适宜使用顺序表
从队尾插入数据叫入队
从栈顶插入数据叫入栈、进栈、压栈
从栈顶弹出数据叫 出栈、弹栈
从队头删除数据叫出队

游戏开发中数据结构的应用

抖音视频：数据结构在游戏开发中的应用