数据结构：栈和队列的实现

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//用数组来实现

//静态的数组
//#define N 10
//struct Stack
//{
//    int _a[N];
//    int _top;
//};

//动态的数组
typedef int STDataType;
typedef struct Stack 
{
    STDataType* _a;
    int _top;//栈顶下标
    int _capacity;
}Stack;

//初始化
void StackInit(Stack* pst);

//销毁
void StackDestory(Stack* pst);

//入栈
void StackPush(Stack* pst, STDataType x);

//出栈
void StackPop(Stack* pst);

//获取数据个数
int StackSize(Stack* pst);

//返回1是空，返回0是非空
int StackEmpty(Stack* pst);

//获取栈顶的数据
STDataType StackTop(Stack* pst);

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
//初始化
void StackInit(Stack* pst)
{
    assert(pst);

    //pst->_a = NULL;
    //pst->_top = 0;
    //pst->_capacity = 0;
    pst->_a = (STDataType*)malloc(sizeof(STDataType) * 4);
    pst->_top = 0;
    pst->_capacity = 4;
}

//销毁
void StackDestory(Stack* pst)
{
    assert(pst);
    free(pst->_a);
    pst->_a = NULL;
    pst->_top = 0;
    pst->_capacity = 0;
}

//入栈
void StackPush(Stack* pst, STDataType x)
{
    assert(pst);
    if (pst->_top == pst->_capacity)//满了需要增容
    {
        pst->_capacity *= 2;
        STDataType* tmp = (STDataType*)realloc(pst->_a, pst->_capacity*sizeof(STDataType) );
        if (tmp == NULL)//增容失败
        {
            printf("增容失败\n");
            exit(-1);
        }
        else//将tmp给pst->_a,指向它
        {
            pst->_a = tmp;
        }
    }
    pst->_a[pst->_top] = x;
    pst->_top++;
}

//出栈
void StackPop(Stack* pst)
{
    assert(pst);
    assert(pst->_top > 0);
    --pst->_top;
}

//获取数据个数
int StackSize(Stack* pst)
{
    assert(pst);
    return pst->_top;
}

//返回1是空，返回0是非空
int StackEmpty(Stack* pst)
{
    assert(pst);
    return pst->_top == 0 ? 1 : 0;
}

//获取栈顶的数据
STDataType StackTop(Stack* pst)
{
    assert(pst);
    assert(pst->_top > 0);
    return pst->_a[pst->_top - 1];//pst->_top是元素的个数
}

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//链表实现
typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* _next;
    QDataType _data;
}QueueNode;

typedef struct Queue
{
    QueueNode* _head;
    QueueNode* _tail;
}Queue;

void QueueInit(Queue* pq);

void QueueDestory(Queue* pq);

void QueuePush(Queue* pq, QDataType x);

void QueuePop(Queue* pq);

QDataType QueueFront(Queue* pq);

QDataType QueueBack(Queue* pq);

//返回1是空，返回0是非空
int QueueEmpty(Queue* pq);

int QueueSize(Queue* pq);

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
    assert(pq);
    pq->_head = NULL;
    pq->_tail = NULL;
}

void QueueDestory(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);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL)
    {
        printf("内存不足\n");
        exit(-1);
    }
    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);
    QueueNode* next = pq->_head->_next;
    free(pq->_head);
    pq->_head = next;
    if (pq->_head == NULL)
    {
        pq->_tail = NULL;
    }
}

QDataType QueueFront(Queue* pq)//取队头数据
{
    assert(pq);
    assert(pq->_head);
    return pq->_head->_data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(pq->_tail);
    return pq->_tail->_data;
}

//返回1是空，返回0是非空
int QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->_head == NULL ? 1 : 0;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->_head;
    int sz = 0;
    while (cur)
    {
        sz++;
        cur = cur->_next;
    }
    return sz;
}

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
#include "Queue.h"

//栈的作用
//1.如果有后进先出需求的地方，比如迷宫问题
//2.递归改成非递归
//

void TestStack()
{
    //后进先出是相对入的时候在栈里面的数据
    Stack st;
    StackInit(&st);
    StackPush(&st, 1);
    StackPush(&st, 2);

    printf("%d ", StackTop(&st));
    StackPop(&st);

    StackPush(&st, 3);
    StackPush(&st, 4);

    while (!StackEmpty(&st))
    {
        printf("%d ", StackTop(&st));
        StackPop(&st);
    }
    printf("\n");
    StackDestory(&st);
}

//队的作用
//1.先进先出的场景，比如要保持序列公平，排队抽号

void TestQueue()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    printf("%d ", QueueFront(&q));//取队头数据
    QueuePop(&q);

    QueuePush(&q, 3);
    QueuePush(&q, 4);

    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));//取队头数据
        QueuePop(&q);
    }
    printf("\n");
    QueueDestory(&q);
}

int main()
{
    //TestStack();
    TestQueue();
    return 0;
}