[数据结构与算法]练就基本功之栈与队列【数据结构】【C语言实现】

0.前言🐕

hello 大家好啊，今天学习的是栈和队列。

🐱🐱🐱

话不多说，直接进入正题。

1.栈🐱

栈（Stack）：是只允许在一端进行插入或删除的线性表。栈是一种线性表，但限定这种线性表只能在某一端进行插入和删除操作。

遵循LIFO原则。（Last In First Out）

注意先入后出是相对而言的。
举个例子

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（C）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

数据插入和删除的一端称为栈顶。

2.栈的实现鬼

实现方式

数组

单链表

单链表去要找尾就不太方便，因此考虑让单链表的头充当栈顶，单链表的尾充当栈底比较方便。

双向带头循环链表

实现栈时比单链表方便，但实现双向带头循环链表实现也麻烦。

综上，使用数组实现更好。

3.栈的代码实现😳

3.1栈的定义

struct Stack
{
	STDataType* a;
	int top;//栈顶
	int capacity;//容量,方便增容
};

3.2初始化&销毁

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

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

3.2Push&Pop

考虑清楚top表示的含义

1. top初始化为0
   top就是当前元素的下一个位置。
   需要先放数据再++
2. top初始化为-1
   top指向的就是当前元素。
   需要先++再放数据。

// 性质决定了只能在栈顶出入数据
// 选top一开始指向0的方式
void StackPush(Stack *pSt, STDataType x)
{
    assert(pSt);
    // 满了要扩容，
    if (pSt->top == pSt->capacity)
    {
        int newCapacity = pSt->capacity == 0 ? 4 : pSt->capacity * 2;
        // realloc传的新空间的整体大小，如果pSt->a 为空，那么realloc等价于malloc
        pSt->a = (STDataType *)realloc(pSt->a, newCapacity * sizeof(STDataType));
        if (pSt->a == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        pSt->capacity = newCapacity;
    }
    pSt->a[pSt->top++] = x;
}
void StackPop(Stack *pSt)
{
    assert(pSt);
    assert(pSt->top > 0); // 有数据才能pop
    --pSt->top;
    //只需--top即可，无需将要删除元素置0等无谓操作，只要读取不到就认为删除了。
}

注意:

一开始栈为空，newCapacity会被赋值为4，pSt->a 为空，realloc等价于malloc。

👉戳我查看realloc

void StackPop(Stack *pSt)
{
    assert(pSt);
    assert(pSt->top > 0); // 有数据才能pop
    --pSt->top;
    //只需--top即可，无需将要删除元素置0等无谓操作，只要读取不到就认为删除了。
}

3.3判空

bool StackEmpty(Stack *pSt)
{
    assert(pSt);
    return pSt->top == 0;
}

3.4求大小

由于我们让top是指向元素的下一个位置，因此top的大小恰好就是栈元素的大小。

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

3.5取栈顶元素

// 访问栈顶数据
STDataType StackTop(Stack *pSt)
{
    assert(pSt);
    assert(pSt->top > 0); // 防止top为0时越界访问
    return pSt->a[pSt->top - 1];
}

4.源代码😋

4.1Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int STDataType;
typedef struct Stack
{
    STDataType *a;
    int top;      //栈顶
    int capacity; //容量,方便增容
} Stack;

void StackInit(Stack *pSt);
void StackDestroy(Stack *pSt);
// 性质决定了只能在栈顶出入数据
void StackPush(Stack *pSt, STDataType x);
void StackPop(Stack *pSt);
// 访问栈顶数据
STDataType StackTop(Stack *pSt);
bool StackEmpty(Stack *pSt);
int StackSize(Stack *pSt);

4.2Stack.cpp

#include "Stack.h"

void StackInit(Stack *pSt)
{
    assert(pSt);
    pSt->a = NULL;
    pSt->capacity = pSt->top = 0;
}
void StackDestroy(Stack *pSt)
{
    assert(pSt);
    free(pSt->a);
    pSt->a = NULL;
    pSt->capacity = pSt->top = 0;
}
// 性质决定了只能在栈顶出入数据
// 选top一开始指向0的方式
void StackPush(Stack *pSt, STDataType x)
{
    assert(pSt);
    // 满了要扩容，
    if (pSt->top == pSt->capacity)
    {
        int newCapacity = pSt->capacity == 0 ? 4 : pSt->capacity * 2;
        // realloc传的新空间的整体大小，如果pSt->a 为空，那么realloc等价于malloc
        pSt->a = (STDataType *)realloc(pSt->a, newCapacity * sizeof(STDataType));
        if (pSt->a == NULL)
        {
            printf("realloc fail\n");
            exit(-1);
        }
        pSt->capacity = newCapacity;
    }
    pSt->a[pSt->top++] = x;
}
void StackPop(Stack *pSt)
{
    assert(pSt);
    assert(pSt->top > 0); // 有数据才能pop
    --pSt->top;
    //只需--top即可，无需将要删除元素置0等无谓操作，只要读取不到就认为删除了。
}
// 访问栈顶数据
STDataType StackTop(Stack *pSt)
{
    assert(pSt);
    assert(pSt->top > 0);
    return pSt->a[pSt->top - 1];
}
bool StackEmpty(Stack *pSt)
{
    assert(pSt);
    return pSt->top == 0;
}
int StackSize(Stack *pSt)
{
    assert(pSt);
    return pSt->top;
}

4.3Test.cpp

#include "Stack.h"

void Test()
{
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);

    StackPush(&st, 3);
    StackPush(&st, 4);
    // 1 2 3 4 top指向的是4的下一个位置
    // 栈是先进后出，不能直接按顺序读取，不然就变成先进先出了。
    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st); //为了访问下一个元素，必须删掉当前的，让top移动
    }
    StackDestroy(&st);
}
void Test2()
{
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);
    // 入了2个就出1个，顺序就变了。
    printf("%d ", StackTop(&st));
    StackPop(&st); //为了访问下一个元素，必须删掉当前的，让top移动
    StackPush(&st, 3);
    StackPush(&st, 4);
    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st); //为了访问下一个元素，必须删掉当前的，让top移动
    }
    StackDestroy(&st);
    // 打印结果2 4 3 1
}
int main(int argc, char const *argv[])
{
    Test();
    system("pause");
    return 0;
}

5.队列🦌

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出

FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

入队顺序：A B C D

出队顺序：A B C D

6.队列的实现🍎

我们需要在队尾插入，队头删除。

如果使用数组的结构，出队列在数组头上出数据，需要挪动数据，效率会比较低。

因此用单链表更合适。

单链表的头删是非常高效。

由于需要频繁的尾插，因此我们可以记录一个尾指针。

这里需不需要带上哨兵位呢？可以，但没必要。带上哨兵位了，只是少了一些判空的处理。

7.队列的代码实现😀

7.1队列的定义

前面提到我们要用链表实现队列，而且是要记录一个尾指针来方便尾插。

因此先定义一个链表节点，再定义2个指向节点的指针就是队列啦。

// 定义队列节点
typedef struct QueueNode
{
    struct QueueNode *next;
    QDataType data;
} QueueNode;

// 定义队列
typedef struct Queue
{
    QueueNode *head;
    QueueNode *tail;
} Queue;

7.2初始化&销毁

void QueueInit(Queue *pq)
{
    // 队列可以为空，但结构体指针不能为空
    assert(pq);
    pq->head = pq->tail = NULL;
}

销毁也就是把开辟出来的每一个节点都free掉。

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

7.3Push&Pop

Push时注意考虑队列为空的情况。

Pop时要注意考虑删得只剩一个节点的情况，此时tail还没置空。

// 其实就是尾插
// 注意考虑队列为空
void QueuePush(Queue *pq, QDataType x)
{
    assert(pq);
    // 这里只有push需要创建节点，因此没必要单独写一个创建节点的函数
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    assert(newNode); // 暴力检查开辟失败的情况
    newNode->data = x;
    newNode->next = NULL;
    // 考虑队列为空的情况插入
    if (pq->tail == NULL)
    {
        assert(pq->head == NULL); // 保证不可能出现tail为空，head不为空
        pq->head = pq->tail = newNode;
    }
    else
    {
        pq->tail->next = newNode;
        // 注意更新tail
        pq->tail = newNode;
    }
}

// 其实就是头删，保存好下一个节点
void QueuePop(Queue *pq)
{
    assert(pq);
    assert(pq->head && pq->tail); // 头尾不能为空
    //考虑删到只剩一个节点的情况，尾和头都要置空
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QueueNode *next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

7.4取队头队尾元素

//取队头数据
QDataType QueueFront(Queue *pq)
{
    assert(pq);
    assert(pq->head); // 保证头也不能为空
    return pq->head->data;
}

//取队尾数据
QDataType QueueBack(Queue *pq)
{
    assert(pq);
    assert(pq->head); // 保证头也不能为空
    return pq->tail->data;
}

7.5判空

bool QueueEmpty(Queue *pq)
{
    assert(pq);
    return pq->head == NULL && pq->tail == NULL;
    // return pq->head == NULL; // 只判断一个也行
}

7.6求元素个数

// 队列效率最低的接口就是求size
size_t QueueSize(Queue *pq)
{
    assert(pq);
    QueueNode *cur = pq->head;
    size_t size = 0;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
    // size每次计算都要遍历一遍链表。
    // 如果不想遍历，可以在结构体定义时增加一个size计数，每次插入++size，每次删除--size
}

8.源代码🤭

8.1Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int QDataType;
// 定义队列节点
typedef struct QueueNode
{
    struct QueueNode *next;
    QDataType data;
} QueueNode;

// 定义队列
typedef struct Queue
{
    QueueNode *head;
    QueueNode *tail;
} Queue;

// pq表示pointer 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);
bool QueueEmpty(Queue *pq);
size_t QueueSize(Queue *pq);

8.2Queue.cpp

#include "Queue.h"

void QueueInit(Queue *pq)
{
    // 队列可以为空，但结构体指针不能为空
    assert(pq);
    pq->head = pq->tail = NULL;
}

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

// 其实就是尾插
// 注意考虑队列为空
void QueuePush(Queue *pq, QDataType x)
{
    assert(pq);
    // 这里只有push需要创建节点，因此没必要单独写一个创建节点的函数
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    assert(newNode); // 暴力检查开辟失败的情况
    newNode->data = x;
    newNode->next = NULL;
    // 考虑队列为空的情况插入
    if (pq->tail == NULL)
    {
        assert(pq->head == NULL); // 保证不可能出现tail为空，head不为空
        pq->head = pq->tail = newNode;
    }
    else
    {
        pq->tail->next = newNode;
        // 注意更新tail
        pq->tail = newNode;
    }
}

// 其实就是头删，保存好下一个节点
void QueuePop(Queue *pq)
{
    assert(pq);
    assert(pq->head && pq->tail); // 头尾不能为空
    //考虑删到只剩一个节点的情况，尾和头都要置空
    if (pq->head->next == NULL)
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else
    {
        QueueNode *next = pq->head->next;
        free(pq->head);
        pq->head = next;
    }
}

bool QueueEmpty(Queue *pq)
{
    assert(pq);
    return pq->head == NULL && pq->tail == NULL;
    // return pq->head == NULL; // 只判断一个也行
}

// 队列效率最低的接口就是求size
size_t QueueSize(Queue *pq)
{
    assert(pq);
    QueueNode *cur = pq->head;
    size_t size = 0;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
    // size每次计算都要遍历一遍链表。
    // 如果不想遍历，可以在结构体定义时增加一个size计数，每次插入++size，每次删除--size
}

//取队头数据
QDataType QueueFront(Queue *pq)
{
    assert(pq);
    assert(pq->head); // 保证头也不能为空
    return pq->head->data;
}
//取队尾数据
QDataType QueueBack(Queue *pq)
{
    assert(pq);
    assert(pq->head); // 保证头也不能为空
    return pq->tail->data;
}

8.3Test.cpp

#include "Queue.h"
void Test1()
{
    Queue q;
    QueueInit(&q); // 要改变结构体内容，要传结构体指针
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    while (!QueueEmpty(&q))
    {
        //只能出队头
        printf("%d ", QueueFront(&q));
        QueuePop(&q); // pop掉之后才能取下一个
    }
    printf("\n");
}
int main(int argc, char const *argv[])
{
    Test1();
    system("pause");
    return 0;
}

9.尾声😁

🌹🌹🌹

写文不易，如果有帮助烦请点个赞~ 👍👍👍

Thanks?(･ω･)ﾉ🌹🌹🌹

😘😘😘

👀👀由于笔者水平有限，在今后的博文中难免会出现错误之处，本人非常希望您如果发现错误，恳请留言批评斧正，希望和大家一起学习，一起进步ヽ(￣ω￣(￣ω￣〃)ゝ，期待您的留言评论。
附GitHub仓库链接

附联系方式(2076188013)(QQ)