在这里插入图片描述

文章目录

🔒栈区

👉什么是栈

🪐栈的接口函数
- 👉栈的建立与初始化

🔒队列区

👉什么是队列

🪐队列的接口函数

👉小结

🎬功能动画演示区

- 👉栈功能动画演示
- 👉队列功能动画演示

🔒源文件区

- 👉栈实现的源文件
- 👉队列实现的源文件

🔑栈区

👉什么是栈

栈的概念及结构

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

🌟重点：后进先出

栈就好比叠书本，第一本书叠到最低，后续把书叠在第一本书的上面，最后叠的那一本是最容易拿的，而第一本书只能把上面叠的书拿完才能拿

🪐栈的接口函数

👉栈的建立与初始化

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

链表形式(比较麻烦，不建议使用)

我们栈的实现比较优的做法都是顺序表实现

栈的建立有两种方式：一种是静态栈，容量固定，不建议使用。另一种是动态栈，容量可以动态变化，比较灵活（本文使用的方式）

不管是动态栈还是静态栈，都需要一个变量top用来指向栈顶

两种栈的实现方式如下

//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
 STDataType _a[N];
 int _top; // 栈顶
}Stack;


//动态栈！！！！！
typedef int STDataType;  //方便后续可能要存储其他类型的数据

typedef struct Stack
{
    STDataType* a;  //用来指向顺序表
    int  top; //栈顶
    int  capacity; //容量
}Stack;

初始化栈：把指向顺序表的指针置空，把栈顶和容量值零

void StackInit(Stack* ps)
{
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

👉入栈与出栈

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

入栈前的工作就是判断是否有容量可以存放，没有就增容（realloc这个函数可以增容，也可以像malloc函数一种开辟空间，之前的顺序表有详解）

而且要注意的就是入栈只能是从尾入

void StackPush(Stack* ps, STDataType x)
{
    assert(ps);  //判空，ps不能为空，不然下面的操作会导致程序崩溃
    if (ps->capacity == ps->top)
    {
        //如果栈的容量为零，就赋值4个空间给它，如果不为零就2倍扩容
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        Stack* tem = (Stack*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tem == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tem;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

出栈就跟顺序表尾删一样，直接把top下标减一即可

要注意的是要出栈要判断栈中是否有数据可出

void StackPop(Stack* ps)
{
    assert(ps);
    //栈不为空才能出栈
    assert(ps->top > 0);
    
    ps->top--;
}

👉获取栈顶元素

获取之前也是需要判断栈是否有数据

有数据就直接返回栈顶数据即可

STDataType StackTop(Stack* ps)
{
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

👉获取栈的有效个数

栈的有效个数就是top的下标，直接返回top即可。

int StackSize(Stack* ps)
{
    return ps->top;
}

👉检测栈是否为空

判断栈是否为空，其实就是判断有效个数top是否为零

要注意返回要求：检测栈是否为空，如果为空返回非零结果，如果不为空返回0

版本1.0的判断方式可以直接由版本2.0的一句表达式搞定，如果不理解就版本1.0

//版本1.0
int StackEmpty(Stack* ps)
{
    if(ps->top>0)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}

//版本2.0
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
    return ps->top == 0;
}

👉销毁栈

销毁要注意的是记得把销毁后的变量置空即可。

void StackDestroy(Stack* ps)
{
    free(ps->a);
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

🔑队列区

在这里插入图片描述

👉什么是队列

队列的概念及结构

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

🌟重点：先进先出

队列就好比去排队做核酸，肯定是先来先做嘛！！！跟排队一个道理。

🪐队列的接口函数

👉队列的建立和初始化

那队列也面临一个问题，那就是用顺序表呢？还是链表实现呢？

其实从队列的先进先出性质就可以知道顺序表是不太好的，因为如果你要顺序表的话，把头元素出列后，为了保持顺序表的结构，其他元素是要向移动一位的，而我们知道顺序表移动数据的时间复杂度为O(N),效率比较低。

所以队列使用的是链表结构

队列的建立需要注意的是：与单链表相比要多定义一个尾指针tail，方便数据入队列，不用每次都找尾。

这里可能有人会问，那为什么实现单链表的时候不加一个尾指针嘞？

其实单链表加尾指针作用不大，因为你尾删的时候，不也还需要遍历链表找尾的前一个节点吗！

那为了避免函数传参的时候要多传一个尾指针，可以把头和尾指针定义在结构体中，减少传参个数

typedef int QDataType;
//队列节点
typedef struct Qnode
{
    QDataType date;
    struct Qnode* next;
}Qnode;
//头指针和尾指针
typedef struct Queue
{
    Qnode * head;
    Qnode* tail;
}Queue;

初始化也是常规置空了

void QueueInit(Queue* q)
{
    assert(q);
    q->head = q->tail = NULL;
}

👉入队列与出队列

🌟重点：先进先出

入队列前嘛，要注意的是要判断第一次入列的时候是直接把新节点的值赋给头和尾指针的

后续入列就直接尾插即可

void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    Qnode* newNode = (Qnode*)malloc(sizeof(Qnode));
    newNode->date = data;
    newNode->next = NULL;

    if (q->head == NULL)
    {
        q->head = q->tail = newNode;
    }
    else
    {
        q->tail->next = newNode;
        q->tail = q->tail->next;
    }
}

出列是跟单链表头删一样的操作，先记录头结点的下一个节点地址，然后释放头结点，重新连接新的头

void QueuePop(Queue* q)
{
    assert(q);
    assert(q->head);
    if(q->head->next==NULL)//删最后一个元素
    {
        free(q->head);
        q->tail=q->head=NULL;
    }
    else
    {
    Qnode* next = q->head->next;
    free(q->head);
    q->head = next;
    }

}

👉获取队列头部元素与队列尾部元素

获取头部元素就比较简单了，返回头指针指向的值前只需判断一下头有没有空即可，没有空就直接返回头指针指向的数据

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(q->head);
    return q->head->date;
}

获取尾部元素也是一样的操作

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(q->tail);
    return q->tail->date;
}

👉获取队列中有效元素个数

获取队列有效元素，就普普通通的遍历链表即可

定义一个变量count用来记录元素个数

int QueueSize(Queue* q)
{
    assert(q);
    Qnode* cur = q->head;
    //记录元素个数
    int count = 0;
    while (cur)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

👉检测队列是否为空

还是注意返回要求：检测队列是否为空，如果为空返回非零结果，如果非空返回0

跟上面栈的判定一样，也有两个版本，我就给一个较优的

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

👉销毁队列

销毁也跟单链表一样的操作，记录后一个节点，释放前一个节点，迭代往后遍历链表，最后把头和尾指针置空

要注意什么时候都要养成free掉节点后把对应指针置空，不然容易出bug！！！

void QueueDestroy(Queue* q)
{
    assert(q);
    Qnode* cur = q->head;
    while (cur)
    {
        Qnode* next = cur->next;
        free(cur);
        cur=next;
    }
    q->tail=q->head = NULL;

}

👉小结

看到这里你已经基本理解栈和队列的操作了，如果自己可以动手实操了，那么恭喜你已经掌握了栈和队列的基本操作。其实学了顺序表和单链表的操作之后，栈和队列对于那么在座的各位来说是真的小菜一碟！

👉栈功能的动画演示

在这里插入图片描述

下面就分享一下我的源代码给大家玩玩

👉栈实现的源文件

text.c

#define _CRT_SECURE_NO_WARNINGS   //vs编译器需要这个

#include"Stack.h"

void menu()
{

        printf("*******************************\n");
        printf("       1.入栈   2.出栈         \n");
        printf("       3.获取栈顶元素          \n");
        printf("       4.获取栈中有效元素个数  \n");
        printf("       5.检测栈  6.打印栈数据   \n");
        printf("       -1.退出                 \n");
        printf("*******************************\n");
        printf(" 请选择>:   \n");

}
void textMenu()
{
    Stack stack;
    StackInit(&stack);
    int input = 0;
    STDataType x1 = 0;
    int  ret = 0;
    while (input != -1)
    {
        menu();
        scanf("%d", &input);
        switch (input)
        {
        case 1:
            printf("输入你要入栈的值，以-1为结束\n");
            scanf("%d", &x1);
            while (x1 != -1)
            {
                StackPush(&stack, x1);
                scanf("%d", &x1);
            }
            break;
        case 2:
            StackPop(&stack);
            printf("出栈成功\n");
            break;
        case 3:
            printf("栈顶元素为：%d \n", StackTop(&stack));
            break;
        case 4:
            printf("有效个数有：%d \n", StackSize(&stack));
            break;
        case 5:
            ret = StackEmpty(&stack);
            if (ret == 0)
            {
                printf("栈非空\n");
            }
            else
            {
                printf("栈为空\n");
            }
            break;
        case 6:        
            //栈不为空一直打印
            while (!StackEmpty(&stack))
            {
                printf("%d ", StackTop(&stack));
                //打印一个Pop一个
                StackPop(&stack);
            }printf("\n");
            break;
        case -1:
            printf("退出成功\n");
            break;
        default:
            printf("无此选项，请重新输入\n");
            break;
        }
    }
    StackDestroy(&stack);
}
int main()
{
    textMenu();

    return 0;
}

Stack.c

#define _CRT_SECURE_NO_WARNINGS

#include"Stack.h"

void StackInit(Stack* ps)
{
    ps->a = NULL;
    ps->capacity = ps->top = 0;
}

void StackPush(Stack* ps, STDataType x)
{
    assert(ps);
    if (ps->capacity == ps->top)
    {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        STDataType* tem = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
        if (tem == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        ps->a = tem;
        ps->capacity = newCapacity;
    }
    ps->a[ps->top] = x;
    ps->top++;
}

void StackPop(Stack* ps)
{
    assert(ps);
    assert(ps->top > 0);
    
    ps->top--;
}

STDataType StackTop(Stack* ps)
{
    assert(ps->top > 0);
    return ps->a[ps->top - 1];
}

int StackSize(Stack* ps)
{
    return ps->top;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{
    return ps->top == 0;
}

void StackDestroy(Stack* ps)
{
    free(ps->a);
    ps->a = NULL;
    free(ps);
    ps->capacity = ps->top = 0;
}

Stack.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int STDataType;

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

// 初始化栈
void StackInit(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);

👉队列功能的动画演示

在这里插入图片描述

👉队列实现的源文件

text.c

#define _CRT_SECURE_NO_WARNINGS  //vs编译器需要这个

#include"Queue.h"

void menu()
{

        printf("*******************************\n");
        printf("       1.入列   2.出列         \n");
        printf("       3.获取队列头元素        \n");
        printf("       4.获取队列队尾元素      \n");
        printf("       5.获取队列中有效元素个数\n");
        printf("       6.检测队列  7.打印队列  \n");
        printf("       -1.退出                 \n");
        printf("*******************************\n");
        printf(" 请选择>:   \n");


}
void textMenu()
{
    Queue queue;
    QueueInit(&queue);
    int input = 0;
    QDataType x1 = 0;
    int  ret = 0;
    while (input != -1)
    {
            menu();
            scanf("%d", &input);
            switch (input)
            {
                case 1:
                    printf("输入你要入列的值，以-1为结束\n");
                    scanf("%d", &x1);
                    while (x1 != -1)
                    {
                        QueuePush(&queue, x1);
                        scanf("%d", &x1);
                    }
                    break;
                case 2:
                    QueuePop(&queue);
                    printf("出列成功\n");
                    break;
                case 3:
                    printf("头部元素为：%d \n", QueueFront(&queue));
                    break;
                case 4:
                    printf("尾部元素为：%d \n", QueueBack(&queue));
                    break;
                case 5:
                    printf("有效个数有：%d \n", QueueSize(&queue));
                    break;
                case 6:
                      ret = QueueEmpty(&queue);
                    if (ret == 0)
                    {
                        printf("队列非空\n");
                    }
                    else
                    {
                        printf("队列为空\n");
                    }
                    break;
                case 7:
                    //队列不为空一直打印
                    while (!QueueEmpty(&queue))
                    {
                        printf("%d ", QueueFront(&queue));
                        //打印一个Pop一个
                        QueuePop(&queue);
                    }printf("\n");
                    break;

                case -1:
                    printf("退出成功\n");
                    break;
                default:
                    printf("无此选项，请重新输入\n");
                    break;
            }
    }
    QueueDestroy(&queue);
}

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

Queue.c

#define _CRT_SECURE_NO_WARNINGS

#include"Queue.h"

void QueueInit(Queue* q)
{
    assert(q);
    q->head = q->tail = NULL;
}

void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    Qnode* newNode = (Qnode*)malloc(sizeof(Qnode));
    newNode->date = data;
    newNode->next = NULL;

    if (q->head == NULL)
    {
        q->head = q->tail = newNode;
    }
    else
    {
        q->tail->next = newNode;
        q->tail = q->tail->next;
    }
}

void QueuePop(Queue* q)
{
    assert(q);
    assert(q->head);
    if(q->head->next==NULL)//删最后一个元素
    {
        free(q->head);
        q->tail=q->head=NULL;
    }
    else
    {
    Qnode* next = q->head->next;
    free(q->head);
    q->head = next;
    }

}

QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(q->head);
    return q->head->date;
}

QDataType QueueBack(Queue* q)
{
    assert(q);
    assert(q->tail);
    return q->tail->date;
}

int QueueSize(Queue* q)
{
    assert(q);
    Qnode* cur = q->head;
    int count = 0;
    while (cur)
    {
        count++;
        cur = cur->next;
    }
    return count;
}

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

void QueueDestroy(Queue* q)
{
    assert(q);
    while (q->head)
    {
        Qnode* cur = q->head->next;
        free(q->head);
        q->head = cur;
    }
    q->tail = NULL;
    free(q);
    q = NULL;
}

Queue.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int QDataType;

typedef struct Qnode
{
    QDataType date;
    struct Qnode* next;
}Qnode;

typedef struct Queue
{
    Qnode * head;
    Qnode* tail;
}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 
int QueueEmpty(Queue* q);

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

【学完线性表不学栈和队列是真的可惜】栈和队列实质性操作

文章目录

🔒栈区

🔒队列区

🎬功能动画演示区

🔒源文件区

🔑栈区

🪐栈的接口函数

🔑队列区

🪐队列的接口函数

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【学完线性表不学栈和队列是真的可惜】栈和队列实质性操作

文章目录

🔒栈区

🔒队列区

🎬功能动画演示区

🔒源文件区

🔑栈区

🪐栈的接口函数

🔑队列区

🪐队列的接口函数

热门文章

最新文章

相关课程

相关电子书