• 【数据结构】栈和队列


    大家好呀!👋这个是付青云同学的博客!😁
    写博客是为了来记录我的学习过程,同时也希望通过博客能够帮助到需要帮助的人。
    如果我的博客可以帮助到你,不妨给我一个关注哦😁

    栈的概念及结构

    :一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
    压栈:栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶
    出栈:栈的删除操作叫做出栈。出数据也在栈顶
    总的来说栈的特点就是:先进后出

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

    栈的实现

    栈可以用链表或者数组实现,但是相对而言数组的结构更好一点,因为栈只在尾上插入,数组在尾上插入数据的代价较小。
    在这里插入图片描述
    在这里插入图片描述

    #include 
    #include 
    #include 
    #include 
    
    
    typedef int STDateType;
    
    typedef struct Stack
    {
    	STDateType* a;
    	//栈顶
    	int top;
    	//容量
    	int capacity;
    }ST;
    
    //初始化栈
    void StackInit(ST* ps);
    
    //销毁栈
    void StackDestroy(ST* ps);
    
    //入栈
    void StackPush(ST* ps,STDateType x);
    
    //出栈
    void StackPop(ST* ps);
    
    //获取栈顶元素
    STDateType StackTop(ST* ps);
    
    //获取栈内元素个数
    int StackSize(ST* ps);
    
    //检测栈是否为空,空则返回非零结果,如果不空则返回0
    bool StackEmpty(ST* ps);
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    #include "stack.h"
    
    void StackInit(ST* ps)
    {
    	assert(ps);
    	ps->capacity = 0;
    	ps->top = 0;//top=-1
    	ps->a = NULL;
    
    }
    
    void StackDestroy(ST* ps)
    {
    	assert(ps);
    
    	free(ps->a);
    	ps->a = NULL;
    	ps->capacity = ps->top = 0;
    
    }
    void StackPush(ST* ps, STDateType x)
    {
    	assert(ps);
    	if (ps->capacity == ps->top)
    	{
    		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    		STDateType* tmp = realloc(ps->a, sizeof(STDateType) * newCapacity);
    		if (tmp == NULL)
    		{
    			printf("realloc fail\n");
    			exit(-1);
    		}
    
    		ps->a = tmp;
    		ps->capacity = newCapacity;
    
    	}
    	ps->a[ps->top] = x;
    	ps->top++;
    }
    
    void StackPop(ST* ps)
    {
    	assert(ps->top > 0);
    	assert(ps);
    
    	ps->top--;
    }
    STDateType StackTop(ST* ps)
    {
    	assert(ps);
    	assert(!StackEmpty(ps));
    
    	return ps->a[ps->top - 1];
    }
    int StackSize(ST* ps)
    {
    	assert(ps);
    
    	return ps->top;
    }
    bool StackEmpty(ST* ps)
    {
    	assert(ps);
    
    	return ps->top == 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67

    队列

    队列的概念及结构

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表。
    入队列:进行插入操作的一端称为队尾
    出队列:进行删除操作的一端称为队头
    总的来说队列的特点就是:先进先出
    在这里插入图片描述

    队列的实现

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

    #include 
    #include 
    #include 
    #include 
    
    typedef int QDataType;
    
    typedef struct QueueNode
    {
    	struct QueueNode* next;
    	QDataType data;
    
    }QNode;
    
    typedef struct Queue
    {
    	QNode* head;
    	QNode* tail;
    
    }Queue;
    
    //初始化队列
    void QueueInit(Queue* pq);
    
    //销毁队列
    void QueueDestroy(Queue* pq);
    
    //队尾入队列
    void QueuePush(Queue* pq, QDataType x);
    
    //队头出队列
    void QueuePop(Queue* pq);
    
    //获取队列头部元素
    QDataType QueueFront(Queue* pq);
    
    //获取队列尾部元素
    QDataType QueueBack(Queue* pq);
    
    //获取队列中有效元素个数
    int QueueSize(Queue* pq);
    
    //检测队列是否为空,如果为空返回非零结果,如果非空返回0
    bool QueueEmpty(Queue* pq);
    
    //打印
    void QueuePrint(Queue* pq);
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    #include "Queue.h"
    
    void QueueInit(Queue* pq)
    {
    	assert(pq);
    
    	pq->head = NULL;
    	pq->tail = NULL;
    }
    
    void QueueDestroy(Queue* pq)
    {
    	assert(pq);
    
    	QNode* cur = pq->head;
    	while (cur != NULL)
    	{
    		QNode* next = cur->next;
    		free(cur);
    		cur = next;
    	}
    
    	pq->head = pq->tail = NULL;
    
    }
    
    void QueuePush(Queue* pq, QDataType x)
    {
    	assert(pq);
    
    	QNode* newnode = (QNode*)malloc(sizeof(QNode));
    	newnode->data = x;
    	newnode->next = NULL;
    
    	if (pq->head == NULL)
    	{
    		pq->head = pq->tail = newnode;
    	}
    	else
    	{
    		pq->tail->next = newnode;
    		pq->tail = newnode;
    	}
    
    }
    
    void QueuePop(Queue* pq)
    {
    	assert(pq);
    	//assert(pq->head);
    	assert(!QueueEmpty(pq));
    	
    	QNode* next = pq->head->next;
    	free(pq->head);
    	pq->head = next;
    	if (pq->head == NULL)
    	{
    		pq->tail=NULL;
    	}
    }
    
    QDataType QueueFront(Queue* pq)
    {
    	assert(pq);
    	assert(!QueueEmpty(pq));
    
    	return pq->head->data;
    }
    
    QDataType QueueBack(Queue* pq)
    {
    	assert(pq);
    	assert(!QueueEmpty(pq));
    
    	return pq->tail->data;
    }
    
    int QueueSize(Queue* pq)
    {
    	assert(pq);
    
    	int n = 0;
    	QNode* cur = pq;
    	while (cur->next)
    	{
    		cur = cur->next;
    		n++;
    	}
    	return n;
    }
    
    bool QueueEmpty(Queue* pq)
    {
    	assert(pq);
    
    	return pq->head == NULL;
    }
    
    void QueuePrint(Queue* pq)
    {
    	assert(pq);
    
    	Queue* cur = pq;
    	while (cur->head!=NULL)
    	{
    		printf("%d ", cur->head->data);
    		cur = cur->head;
    	}
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
  • 相关阅读:
    (Network)IP地址的网络号和广播地址
    Could not load library libcudnn_cnn_train.so.8, 解决类似问题的思路与方法
    桌面宠物 ② 通过js制作属于自己的web网页宠物
    容器数据卷
    pdf转换器哪个软件好用还免费?来这里获得实用技巧!
    linux入门6—日志分析与故障排除
    通过地址和索引实现数组、CPU指令执行过程、内存概述及内存物理结构
    所有社区工作者!能救一个是一个
    redis笔记2
    可变形注意力转换器综述
  • 原文地址:https://blog.csdn.net/qq_62181562/article/details/126207631