• 数据结构——栈和队列

    了解并实现栈和队列-----C语言版

    目录：

    数据结构好难啊，要多学几遍，博客才能下得去笔。加油！

    一、栈

    栈:一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

    1.1栈的定义

    进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO (Last In FirstOut)的原则。

    压栈：栈的插入操作叫做压栈/入栈/进栈。入数据在栈顶。
    出栈：栈的删除操作叫做出栈。出数据也在栈顶。

    在这里插入图片描述

    1.2栈的实现

    栈一般都是用数组和链表的方法去实现得，用数组去实现栈的方法更优一点，因为数组的尾删尾插更方便一点。

    1.2.1 栈的相关接口

    // 初始化栈
    void StackInit(Stack* ps);
    //扩容
    void Stackcapa(Stack* ps);
    // 入栈
    void StackPush(Stack* ps, STDataType data);
    // 出栈
    void StackPop(Stack* ps);
    // 获取栈顶元素
    STDataType StackTop(Stack* ps);
    // 获取栈中有效元素个数
    int StackSize(Stack* ps);
    // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
    int StackEmpty(Stack* ps);
    // 销毁栈
    void StackDestroy(Stack* ps);

    1.2.2栈结构的定义声明和栈的初始化

    栈结构的声明：

    typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    栈的实现是和顺序表有点像，因为顺序表一般也是用数组来实现的。我们这里采用动态顺序表的实现方式，实现动态栈。当栈中空间不够时，可申请动态内存空间进行增容。

    栈的初始化:

    void StackInit(Stack* ps)
{ 
    ps->a = NULL;
    ps-> top =0 ;		// 栈顶
    ps->capacity=0;  // 容量 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    1.2.3栈数据的处理

    1.入栈

    void  StackPush(Stack* ps, STDataType data)
{
    assert(ps);
 if (ps->top == ps->capacity)//相等就扩容
{
Stackcapa(ps);//扩容
}
    ps->a[ps->top] = data;//先赋值，在加加
    ps->top++;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    扩容的函数

    void Stackcapa(Stack* ps)//扩容
{
        int n = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* top = (STDataType*)realloc(ps->a, sizeof(STDataType) * n);
        if (top == NULL)//判断是否为空
        {
            perror("realloc fail");
            exit(-1);
        }
        ps->a = top;
        ps->capacity = n; 
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    入栈就是尾插数据，也就是按顺序插入数据。因为刚才说了top是指向栈顶元素下一个位置，初始化top为0表示的是空栈，但是数组索引从0开始，因此先插入数据，然后top自增，这样做的另一个好处就是top就是栈中元素个数。

    2.出栈

    获取栈顶元素

    STDataType StackTop(Stack* ps)
{
    assert(ps);//判断栈是否为空
    assert(!StackEmpty(ps));
    return ps->a[ps->top-1];
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    因为top是指向栈顶元素下一个位置的，所以栈顶元素应该是top-1。还有一点，当栈为空时，就不能获取元素，所以要断言一下。

    出栈

    void StackPop(Stack* ps)
{
    assert(ps);//判断栈是否为空
    assert(ps->top>0);
    --ps->top;//栈减一个就是出栈
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    出栈就相当于尾删，然后top(栈顶）往下降一个单位。但是，出栈肯定是要得到某个数据，就是将栈中的数据弹出来，然后栈顶往下降。因此还需要个函数来获取栈顶的元素。

    1.2.4 栈判空和获取栈中元素个数以及栈销毁

    1.栈判空

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

    • 1
    • 2
    • 3
    • 4
    • 5

    栈判空非常简单，top为0就是空栈。如果top大于0就不是空栈。

    2.获取栈中元素个数

    int StackSize(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top;
}

    • 1
    • 2
    • 3
    • 4
    • 5

    数组是从0开始的，而top又是指向栈顶元素下一个位置的，刚好top就是栈元素个数，top的值就是栈中元素个数。

    3.栈销毁

    void StackDestroy(Stack* ps)
{
    assert(ps);//判断栈是否为空
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    销毁栈还是和销毁动态顺序表一样，用free释放掉申请的动态内存空间即可，释放掉空间后，该置空的置空，该置0的置0。

    1.2.5 栈的代码实现

    用C语言实现一个支持动态增长的栈
    .h头文件

    #pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
typedef int STDataType;
typedef struct Stack
{
	STDataType* a;
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

// 初始化栈 
void StackInit(Stack* ps);
//扩容
void Stackcapa(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* 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

    .c源文件

    #pragma once
#include "stack.h"

// 初始化栈 
void StackInit(Stack* ps)
{ 
    ps->a = NULL;
    ps-> top =0 ;		// 栈顶
    ps->capacity=0;  // 容量 
}
void Stackcapa(Stack* ps)//扩容
{
        int n = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* top = (STDataType*)realloc(ps->a, sizeof(STDataType) * n);
        if (top == NULL)//判断是否为空
        {
            perror("realloc fail");
            exit(-1);
        }
        ps->a = top;
        ps->capacity = n; 
}
//入栈
void  StackPush(Stack* ps, STDataType data)
{
    assert(ps);
 if (ps->top == ps->capacity)//相等就扩容
{
Stackcapa(ps);//扩容
}
    ps->a[ps->top] = data;//先赋值，在加加
    ps->top++;
}
// 出栈 
void StackPop(Stack* ps)
{
    assert(ps);//判断栈是否为空
    assert(ps->top>0);
    --ps->top;//栈减一个就是出栈
}
// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
    assert(ps);//判断栈是否为空
assert(!StackEmpty(ps));
    return ps->a[ps->top-1];
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top == 0;
}
// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
    assert(ps);//判断栈是否为空
    return ps->top;
}
// 销毁栈 
void StackDestroy(Stack* ps)
{
    assert(ps);//判断栈是否为空
    free(ps->a);
    ps->a = NULL;
    ps->top = ps->capacity = 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

    .c源文件

    #pragma once
#include "stack.h"
void test_1()
{
    Stack ps;//定义一个栈
    // 初始化栈 
    StackInit( &ps);
    // 入栈 
    StackPush( &ps, 4);
    // 入栈 
    StackPush(&ps, 5);
    // 入栈 
    StackPush(&ps, 6);
    printf("栈中有效元素个数：%d\n", StackSize(&ps));
    // 获取栈顶元素 
    while (!StackEmpty(&ps))
    {
        printf("%d ", StackTop(&ps));
        // 出栈 
        StackPop(&ps);
    }
    printf("\n");
    StackDestroy(&ps);
 
}
int main()
{
    test_1();
    return 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

    二、队列

    队列:只允许在一端进行插入数据操作，另一端进行刪除数据操作的特殊线性表。

    2.1队列的定义

    进行数据插入操作的一端叫做入队，进行数据删除操作的一端叫做出队，队列中的数据遵循先进先出FIFO（First In First Out）的原则。

    入队列:进行数据插入操作的一端称为队尾。
    出从列:进行数据刪除操作的一端称为队头。

    在这里插入图片描述

    2.2队列的实现

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

    2.2.1 队列的相关接口

    // 初始化队列
    void QueueInit(Queue* q);
    // 队尾入队列
    void QueuePush(Queue* q, QDataType data);
    // 队头出队列
    void QueuePop(Queue* q);
    // 获取队列头部元素
    QDataType QueueFront(Queue* q);
    // 获取队列队尾元素
    QDataType QueueBack(Queue* q);
    // 获取队列中有效元素个数
    int QueueSize(Queue* q);
    // 检测队列是否为空，如果为空返回非零结果，如果非空返回0
    bool QueueEmpty(Queue* q);
    // 销毁队列
    void QueueDestroy(Queue* q);

    2.2.2 队列结构的定义声明和队列初始化

    队列结构的声明：

    typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;//用来存入队的数据
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;//队头
	QNode* rear;//队尾
	QDataType size;//用来记录元素个数
}Queue;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    这里用到了两个结构体，因为我们不仅要有链式的结构，还要标识队列的头和尾，这样方便我们进行头删和尾插，至于size则是用来记录队列中的元素个数的。

    队列初始化：

    void QueueInit( Queue* q)
{
    assert(q);
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    首先判断是否为空，然后把size置为0，头和尾都置成空。

    2.2.3队列数据的处理

    1.入队

    // 队尾入队列 
void QueuePush(Queue* q, QDataType x)
{
    assert(q);
    QNode* NewNode = (QNode*)malloc(sizeof(QNode));//新建一个节点
    if (NewNode == NULL)
    {
        perror("NewNode");
        exit(-1);
    }
    NewNode->data = x;
    NewNode->next = NULL;
    if (q->rear == NULL)//如果是空队列
    {
        q->front = q->rear = NewNode;
    }
    else//不是空队列
    {
        q->rear->next = NewNode;//尾插
        q->rear = NewNode;
    }
    q->size++;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    首先肯定是要申请节点，然后进行插入 ，但是插入也分两种情况。
    第一种情况：一个数据都没有，front和rear同时指向空；第二种情况：已经有数据了直接在rear后面链接就行了。

    获取队列尾部元素

    QDataType Queueback(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->rear->data;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    先判空，队列不能为空，返回队尾数据。

    2.出队

    // 队头出队列 
void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    if(q->front->next==NULL)
    {
        free(q->front);
        q->front = q->rear = NULL;
    }
    else
    {
        QNode* pwd = q->front->next;//把头指针指向的位置先存起来
           free(q->front);
        q->front = pwd;
    }
    q->size--;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    这里的删除也是要判断是只有一个结点还是有多个结点的情况
    只有一个结点或者删到只有一个结点，就要把头free掉并且头指针和尾都要置成空；有多个节点，创建一个指针，存放pwd的下一个结点，接着free掉头指针，然后更新一下头指针。

    获取队列头部元素

    QDataType QueueFront(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->front->data;

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    先判空，队列不能为空，返回队头数据。

    2.2.4队列判空和获取队列中元素的个数以及队列的销毁

    1.队列判空

    // 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
    assert(q);
    return q->front == NULL;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    如果队列头指针为空就是空队列，头指针不为空，就不是空队列。

    2.获取队列中元素的个数

    // 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    结构体Queue中成员size记录的是元素个数

    3.队列的销毁

    // 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* pwd = q->front;//指向头指针 
    while (pwd)//不是空指针就循环
    {
        QNode* next = pwd->next;
        free(pwd);
        pwd = next;
    }

    q->front = q->rear = NULL;
    q->size = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    有多少个malloc函数开辟空间就要有多少个free函数释放空间，释放掉空间后，该置空的置空，该置0的置0。

    2.2.5队列代码的实现。

    用c语言实现一个由链表结构实现的队列

    .h头文件

    #pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* front;
	QNode* rear;
	QDataType size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

    • 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

    .c源文件

    #include "queue.h" 
// 初始化队列 
void QueueInit( Queue* q)
{
    assert(q);
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType x)
{
    assert(q);
    QNode* NewNode = (QNode*)malloc(sizeof(QNode));//新建一个节点
    if (NewNode == NULL)
    {
        perror("NewNode");
        exit(-1);
    }
    NewNode->data = x;
    NewNode->next = NULL;
    if (q->rear == NULL)//如果是空队列
    {
        q->front = q->rear = NewNode;
    }
    else//不是空队列
    {
        q->rear->next = NewNode;//尾插
        q->rear = NewNode;
    }
    q->size++;
}

// 队头出队列 
void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    if(q->front->next==NULL)
    {
        free(q->front);
        q->front = q->rear = NULL;
    }
    else
    {
        QNode* pwd = q->front->next;//把头指针指向的位置先存起来
           free(q->front);
        q->front = pwd;
    }
    q->size--;
}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->front->data;

}
// 获取队列尾部元素 
QDataType Queueback(Queue* q)
{
    //判断为不为NULL
    assert(q);
    assert(!QueueEmpty(q));
    return q->rear->data;

}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* q)
{
    assert(q);
    return q->front == NULL;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
    assert(q);
    QNode* pwd = q->front;//指向头指针 
    while (pwd)//不是空指针就循环
    {
        QNode* next = pwd->next;
        free(pwd);
        pwd = next;
    }

    q->front = q->rear = NULL;
    q->size = 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
    • 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

    .c源文件

    #include "queue.h" 
void test_1()
{
//定义一个指向队列的指针
    Queue q;
    // 初始化队列 
    QueueInit(&q);
    // 队尾入队列 
    QueuePush(&q, 2);
    // 队尾入队列 
    QueuePush(&q, 3);
    // 队尾入队列 
    QueuePush(&q, 4);
    // 队尾入队列 
    QueuePush(&q, 5);
    // 队尾入队列 
    QueuePush(&q, 6);
    // 获取队列中有效元素个数 
    printf("有效元素个数：%d\n", QueueSize(&q)) ;

    while (!QueueEmpty(&q))
    {
        // 获取队列头部元素 
        printf("%d ", QueueFront(&q));
        // 队头出队列 
        QueuePop(&q);
    }
   //  销毁队列 
   QueueDestroy(&q);
}
int main()
{
    test_1();
    return 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
  • 相关阅读:
    MMCV学习——基础篇2（Runner）| 九千字：含示例代码教程
    软件测试用例
    【JavaWeb】Servlet系列——session会话机制
    day50：QTday3，对话框补充、事件处理机制
    NEFU计算机网络实验一常见网络命令的使用
    设置float浮动
    centos7.6安装jdk1.8
    Linux C程序编译链接的过程，gcc/g++，动态库/静态库
    Bridge 2024 新版本 Bridge 2024 mac软件特色和功能
    Mybatis的事务管理机制。
  • 原文地址：https://blog.csdn.net/plj521/article/details/133932344