【数据结构-C】栈 && 队列

🔎栈介绍

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

压栈：向栈中插入元素为压栈 。

出栈：拿出栈中元素为出栈。

🔎栈的实现方式

顺序栈和链栈

顺序栈（数组结构）：利用一组连续地址的存储单元依次存放自栈底到栈顶的数据元素

🍍使用一个数组来存栈中的元素，以数组中首地址做为栈底（base指针），以数组中最后一个元素的下一个位置作为栈顶（top指针）

链栈（链表结构）：利用链表的形式存放栈底到栈顶中的元素

🍍采用链式存储，压栈使用头插，出栈使用头删。

🔎顺序栈的基本操作及图解分析

🍉栈的表示

结构体表示栈

typedef struct SeqStack
{
    ElemType *base;//表示栈底
    ElemType *top;//表示栈顶
    int stackSize;//表示栈的容量
}SeqStack;

🍉初始化栈

void StackInit(SeqStack * ps)
{
    //分配空间
    ps->base=(ElemType *)malloc(sizeof((ElymType)*STACK_INIT_SIZE);
    assert(ps->base);
    
    //初始化栈顶
    ps->top=ps->base;
    //初始化栈大小
    ps->stackSize=STACK_INIT_SIZE;
}

🍉销毁栈

void StackDestroy(SeqStack *ps)
{
    
    free(ps->base);
    ps->base=NULL;
    ps->top=NULL;

}

🍉检查栈是否为空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps)
{

    if(ps->base == ps->top)
    {
        return -1;
    }
    else
    {
        return 0;
    }

}

🍉入栈

void StackPush(SeqStack *ps, ElemType x)
{
    //判断空间是否充足,不足扩容
    if(ps->top-ps->base >= ps->stackSize)
    {
        ElemType *temp=(ElemType *)realloc(ps->base,sizeof(ElemType)*ps->stackSize*2);
        if(temp ==NULL)
        {
            printf("realloc is fail\n");
            exit(-1);
        }
        else
        {
            ps->base=temp;
            ps->stackSize+=ps->stackSize;
        }
    }
    
    //栈顶插入元素
    *(ps->top)=x;
    //栈顶移到下一位
    ps->top++;

}

🍉出栈

void StackPop(SeqStack* ps)
{
    assert(ps);
    
    if(ps->top == ps->base)
    {
        return;
    }
    else
    {
        ps->top--;
        return;
    }

}

🍉获取栈顶元素

ElemType StackTop(SeqStack* ps)
{
    assert(ps);
    if(ps->top != ps->base)
    {
        return *(ps->top-1);
    }
    else
    {
        return;
    }

}

🔎队列介绍

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

🔎队列的实现方式

顺序队列和链式队列

顺序队列：顺序队列使用数组结构存储队列中的元素。

链式队列：链式队列使用链表结构储存队列中的元素

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

🔎链式队列的基本操作及图解分析

🍉队列的表示形式

//表示队列中的结点
typedef struct QNode
{
    ElemType e;
    QNode* next;
}QNode;

//保存队列的对头队尾
typedef struct Queue
{
    QNode* front;
    QNode* rear;
}Queue;

🍉队列初始化

初始状态时队列中元素为空，所以队头队尾指向NULL

void QueueInit(Queue* pq)
{
    assert(pq);

    //队头队尾指向NULL
    pq->front = NULL;
    pq->rear = NULL;

    return;
}

🍉队尾入队列（尾插）

特殊情况：当队列中为空时，入队既要改变队列的队头，也要改变队列的队尾。

void QueuePush(Queue* pq, ElemType x)
{
    assert(pq);
    QNode* newNode = (QNode*)malloc(sizeof(QNode));

    newNode->e = x;
    newNode->next = NULL;
    
    //特殊情况:队列为空
    if (pq->front == NULL)
    {
        pq->front = newNode;
        pq->rear = newNode;
        return;
    }
    //尾插
    pq->rear->next = newNode;
    //移动队尾
    pq->rear = newNode;
}

🍉队头出队列（头删）

特殊情况：当队列中只有一个元素时，出队，队头队尾都要指向NULL。

void QueuePop(Queue* pq)
{    
    assert(pq);
    队头等于队尾,都指向NULL
    if (pq->front == pq->rear)
    {
        pq->front = NULL;
        pq->rear = NULL;
        return;
    }

    //头删
    QNode* next = pq->front->next;
    free(pq->front);
    pq->front = next;
}

🍉获取队列队头元素

ElemType QueueFront(Queue* pq)
{
    if (pq->front == NULL)
    {
        return;
    }
    return pq->front->e;
}

🍉获取队列长度

int QueueSize(Queue* pq)
{
    if (pq->front == NULL)
    {
        return 0;
    }
    else
    {
        int size = 0;
        QNode* cur = pq->front;
        while (cur != NULL)
        {
            size++;
            cur = cur->next;
        }
        return size;
    }
}

🍉检查队列是否为空

int QueueEmpty(Queue* pq)//返回-1为空，返回0非空
{
    assert(pq);
    if (pq->front == NULL)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}

🍉销毁队列

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->front;
    while (cur !=NULL)
    {
        pq->front = cur->next;
        free(cur);
        cur = pq->front;
    }
    pq->rear = NULL;
}

🔎总结

栈：栈是一端受限，一段允许进行操作的线性表，就像你往一个盒子中放书，你先放进去的，你要想把它拿出来，需要先把这本书上面的所以书拿出来，你才能拿出这本书。

队列：在我们生活中排队买饭，先排就先吃饭，走只能从队头走，排只能从队尾排（不会有人想插队吧😂）。

感谢大家的阅读，希望有所收获，有错之处还请指点指点🈯。

祝大家：心想事成，才高八斗。