链栈，顺序栈，单链队列，循环队列，非循环队列的简单实现

马上要开始校招了，这些基本的数据结构很有必要掌握。

自己基本都忘了，所以花点时间自己重新温习下。

#ifndef _HT_STACK_H
#define _HT_STACK_H

#include <stdio.h>

typedef int SElementType;

// 链栈
typedef struct _LinkStackNode
{
    SElementType data;
    struct _LinkStackNode *next;
}LinkStackNode;
void LinkStack_Init(LinkStackNode **top);
bool LinkStack_Empty(LinkStackNode **top);
bool LinkStack_Push(LinkStackNode **top, SElementType element);
bool LinkStack_Pop(LinkStackNode **top, SElementType *getElement);

///////////////////////////////////////////////////

// 顺序栈
#define STACK_INCREMENT        (2)
typedef struct _SequenceStack
{
    SElementType *top;
    SElementType *base;
    int size;
}SequenceStack;
bool SequenceStack_Init(SequenceStack *S, unsigned int size);
bool SequenceStack_Destroy(SequenceStack *S);
bool SequenceStack_Clear(SequenceStack *S);
bool SequenceStack_Empty(SequenceStack *S);
int SequenceStack_Length(SequenceStack *S);
bool SequenceStack_GetTop(SequenceStack *S, SElementType e);
bool SequenceStack_Push(SequenceStack *S, SElementType e);
bool SequenceStack_Pop(SequenceStack *S, SElementType *e);
bool SequenceStack_Traverse(SequenceStack *S, void(*visit)(SElementType));

#endif

#include "HT_Stack.h"
#include <malloc.h>
#include <string.h>

void LinkStack_Init(LinkStackNode **top)
{
}

bool LinkStack_Empty(LinkStackNode **top)
{
    if ((*top) == NULL)
        return true;
    else
        return false;
}

// 指向结构体指针的指针变量
bool LinkStack_Push(LinkStackNode **top, SElementType element)
{
    LinkStackNode *temp;
    temp = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    if (temp == NULL)
        return false;
    temp->data = element;
    temp->next = (*top);
    (*top) = temp;
    return true;
}

bool LinkStack_Pop(LinkStackNode **top, SElementType *getElement)
{
    if (LinkStack_Empty(top))
    {
        return false;
    }
    LinkStackNode *temp;
    temp = (*top);
    *getElement = temp->data;
    (*top) = temp->next;
    free(temp);
    return true;
}

////////////////////////////////////////////////////////////////////

bool SequenceStack_Init(SequenceStack *S, unsigned int size)
{
    if (size <= 0)
        return false;
    if (!(S->base = (SElementType *)malloc(sizeof(SElementType)* size)))
    {
        return false;
    }
    S->top = S->base;
    S->size = size;
    return true;
}

bool SequenceStack_Destroy(SequenceStack *S)
{
    free(S->base);
    S->base = NULL;
    S->top = NULL;
    S->size = 0;
    return true;
}

bool SequenceStack_Clear(SequenceStack *S)
{
    S->top = S->base;
    return true;
}

bool SequenceStack_Empty(SequenceStack *S)
{
    if (S->top == S->base)
        return true;
    else
        return false;
}

int SequenceStack_Length(SequenceStack *S)
{
    return (S->top - S->base);
}

bool SequenceStack_GetTop(SequenceStack *S, SElementType e)
{
    if (S->top > S->base)
    {
        e = *(S->top - 1);
        return true;
    }
    else
        return false;
}

bool SequenceStack_Push(SequenceStack *S, SElementType e)
{
    if ((S->top - S->base) >= S->size)
    {
        //SElementType *base = S->base;
        //// 重新分配
        //S->base = (SElementType *)malloc(sizeof(SElementType)* (S->size + STACK_INCREMENT));
        //if (!S->base)
        //    return false;
        //// 导入之前的数据
        //memcpy(S->base, base, S->size * sizeof(SElementType));
        //free(base);

        S->base = (SElementType *)realloc(S->base, sizeof(SElementType)* (S->size + STACK_INCREMENT));
        if (!S->base)
            return false;
        S->top = S->base + S->size;
        S->size += STACK_INCREMENT;
    }
    *(S->top)++ = e;
    return true;
}

bool SequenceStack_Pop(SequenceStack *S, SElementType *e)
{
    if (S->top == S->base)
        return false;
    *e = *(--S->top);
    return true;
}

bool SequenceStack_Traverse(SequenceStack *S, void(*visit)(SElementType))
{
    SElementType *top = S->top;
    SElementType *base = S->base;
    while (top > base)
    {
        // 函数指针
        visit(*base++);
    }
    return true;
}

// 在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作
#ifndef _HT_QUEUE_H
#define _HT_QUEUE_H

#include <stdio.h>

typedef int QElementType;

// 单链队列 （队列的链式存储结构）
typedef struct _QueueNode
{
    QElementType data;
    struct _QueueNode *next;
}QueueNode;
typedef struct _LinkQueue
{
    QueueNode *front;
    QueueNode *rear;
}LinkQueue;
bool LinkQueue_Init(LinkQueue *Q);
bool LinkQueue_Destroy(LinkQueue *Q);
bool LinkQueue_Clear(LinkQueue *Q);
bool LinkQueue_Empty(LinkQueue *Q);
int LinkQueue_Length(LinkQueue *Q);
bool LinkQueue_GetHead(LinkQueue *Q, QElementType *e);
bool LinkQueue_Add(LinkQueue *Q, QElementType e);
bool LinkQueue_Delete(LinkQueue *Q, QElementType *e);
bool LinkQueue_Traverse(LinkQueue *Q, void(*visit)(QElementType));

/////////////////////////////

//（队列的顺序存储结构）
#define MAX_Q_SIZE        (30)
typedef struct _SequenceQueue
{
    QElementType *base;
    int front;
    int rear;
}SequenceQueue;

// 非循环队列 
bool SequenceQueue_Init(SequenceQueue *Q);
bool SequenceQueue_Destroy(SequenceQueue *Q);
bool SequenceQueue_Clear(SequenceQueue *Q);
bool SequenceQueue_Empty(SequenceQueue *Q);
int SequenceQueue_Length(SequenceQueue *Q);
bool SequenceQueue_GetHead(SequenceQueue *Q, QElementType *e);
bool SequenceQueue_Add(SequenceQueue *Q, QElementType e);
bool SequenceQueue_Delete(SequenceQueue *Q, QElementType *e);
bool SequenceQueue_Traverse(SequenceQueue *Q, void(*visit)(QElementType));

// Circle 循环队列
bool CircleSequenceQueue_Init(SequenceQueue *Q);
bool CircleSequenceQueue_Destroy(SequenceQueue *Q);
bool CircleSequenceQueue_Clear(SequenceQueue *Q);
bool CircleSequenceQueue_Empty(SequenceQueue *Q);
int CircleSequenceQueue_Length(SequenceQueue *Q);
bool CircleSequenceQueue_GetHead(SequenceQueue *Q, QElementType *e);
bool CircleSequenceQueue_Add(SequenceQueue *Q, QElementType e);
bool CircleSequenceQueue_Delete(SequenceQueue *Q, QElementType *e);
bool CircleSequenceQueue_Traverse(SequenceQueue *Q, void(*visit)(QElementType));

#endif

#include "HT_Queue.h"
#include <malloc.h>
#include <string.h>


// 单链队列
////////// 9 个操作

bool LinkQueue_Init(LinkQueue *Q)
{
    if (!(Q->front = Q->rear = (QueueNode *)malloc(sizeof(QueueNode))))
    {
        return false;
    }
    Q->front->next = NULL;
    return true;
}

bool LinkQueue_Destroy(LinkQueue *Q)
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return true;
}

bool LinkQueue_Clear(LinkQueue *Q)
{
    Q->rear = Q->front;
    QueueNode *p = Q->front->next;
    Q->front->next = NULL;
    QueueNode *q;
    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }
    return true;
}

bool LinkQueue_Empty(LinkQueue *Q)
{
    if (Q->front == Q->rear)
        return true;
    else
        return false;
}

int LinkQueue_Length(LinkQueue *Q)
{
    int len = 0;
    QueueNode *p;
    p = Q->front;
    while (p != Q->rear)
    {
        ++len;
        p = p->next;
    }
    return len;
}

bool LinkQueue_GetHead(LinkQueue *Q, QElementType *e)
{
    if (Q->front == Q->rear)
        return false;
    QueueNode *p = Q->front->next;
    *e = p->data;
    return true;
}

bool LinkQueue_Add(LinkQueue *Q, QElementType e)
{
    QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
    if (!p)
        return false;
    p->data = e;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return true;
}

bool LinkQueue_Delete(LinkQueue *Q, QElementType *e)
{
    if (Q->front == Q->rear)
        return false;
    QueueNode *p;
    p = Q->front->next;
    *e = p->data;
    Q->front->next = p->next;
    if (p == Q->rear)
    {
        Q->rear = Q->front;
    }
    free(p);
    return true;
}

bool LinkQueue_Traverse(LinkQueue *Q, void(*visit)(QElementType))
{
    QueueNode *p;
    p = Q->front->next;
    while (p)
    {
        visit(p->data);
        p = p->next;
    }
    return true;
}

/////////////////////////////////////////////////

// 非循环队列

bool SequenceQueue_Init(SequenceQueue *Q)
{
    Q->base = (QElementType *)malloc(sizeof(QElementType)* MAX_Q_SIZE);
    if (!Q->base)
        return false;
    Q->front = Q->rear = 0;
    return true;
}

bool SequenceQueue_Destroy(SequenceQueue *Q)
{
    if (Q->base)
        free(Q->base);
    Q->base = NULL;
    Q->front = Q->rear = 0;
    return true;
}

bool SequenceQueue_Clear(SequenceQueue *Q)
{
    Q->front = Q->rear = 0;
    return true;
}

bool SequenceQueue_Empty(SequenceQueue *Q)
{
    if (Q->front == Q->rear)
        return true;
    else
        return false;
}

int SequenceQueue_Length(SequenceQueue *Q)
{
    return (Q->rear - Q->front);
}

bool SequenceQueue_GetHead(SequenceQueue *Q, QElementType *e)
{
    if (Q->front == Q->rear)
        return false;
    *e = *(Q->base + Q->front);
    return true;
}

bool SequenceQueue_Add(SequenceQueue *Q, QElementType e)
{
    if (Q->rear >= MAX_Q_SIZE)
    {
        Q->base = (QElementType *)realloc(Q->base, sizeof(QElementType)*(Q->rear + 1));
        if (!Q->base)
            return false;
    }
    *(Q->base + Q->rear) = e;
    ++Q->rear;
    return true;
}

bool SequenceQueue_Delete(SequenceQueue *Q, QElementType *e)
{
    if (Q->front == Q->rear)
        return false;
    *e = *(Q->base + Q->front);
    Q->front += 1;
    return true;
}

bool SequenceQueue_Traverse(SequenceQueue *Q, void(*visit)(QElementType))
{
    int i = 0;
    i = Q->front;
    while (i != Q->rear)
    {
        visit(*(Q->base + i));
        ++i;
    }
    return true;
}

/////////////////////////////////////////////////

// 循环队列

bool CircleSequenceQueue_Init(SequenceQueue *Q)
{
    Q->base = (QElementType *)malloc(sizeof(QElementType)* MAX_Q_SIZE);
    if (!Q->base)
        return false;
    Q->front = Q->rear = 0;
    return true;
}

bool CircleSequenceQueue_Destroy(SequenceQueue *Q)
{
    if (Q->base)
        free(Q->base);
    Q->base = NULL;
    Q->front = Q->rear = 0;
    return true;
}

bool CircleSequenceQueue_Clear(SequenceQueue *Q)
{
    Q->front = Q->rear = 0;
    return true;
}

bool CircleSequenceQueue_Empty(SequenceQueue *Q)
{
    if (Q->front == Q->rear)
        return true;
    else
        return false;
}

int CircleSequenceQueue_Length(SequenceQueue *Q)
{
    return ((Q->rear - Q->front + MAX_Q_SIZE) % MAX_Q_SIZE);
}

bool CircleSequenceQueue_GetHead(SequenceQueue *Q, QElementType *e)
{
    if (Q->front == Q->rear)
        return false;
    *e = *(Q->base + Q->front);
    return true;
}

bool CircleSequenceQueue_Add(SequenceQueue *Q, QElementType e)
{
    // 循环队列最多只能有 MaxSize - 1 个队列元素
    // 队列满
    if (((Q->rear + 1) % MAX_Q_SIZE) == Q->front)
        return false;
    *(Q->base + Q->rear) = e;
    Q->rear = (Q->rear + 1) % MAX_Q_SIZE;
    return true;
}

bool CircleSequenceQueue_Delete(SequenceQueue *Q, QElementType *e)
{
    if (Q->front == Q->rear)
        return false;
    *e = *(Q->base + Q->front);
    Q->front = (Q->front + 1) % MAX_Q_SIZE;
    return true;
}

bool CircleSequenceQueue_Traverse(SequenceQueue *Q, void(*visit)(QElementType))
{
    int i = 0;
    i = Q->front;
    while (i != Q->rear)
    {
        visit(*(Q->base + i));
        i = (i + 1) % MAX_Q_SIZE;
    }
    return true;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "HT_Stack.h"
#include "HT_Queue.h"

void Final_Fun()
{
    printf("exit!
");
}

void Test()
{
    // atexit or oneexit
    atexit(Final_Fun);

    // len  8
    char *str = "huangtao";
    char *str_temp;
    printf("%d
", str);
    for (str_temp = str; *str_temp != ''; str_temp++)
    {
        printf("%d
", str_temp);
    }
    printf("len: %d
", (str_temp - str));

    // strcpy
    printf("src:  %s
", str);
    int len = 12;
    char *dest = (char *)malloc(len * sizeof(char));
    char *dest_temp = dest;
    memset(dest, 97, len * sizeof(char));
    str_temp = str;

    while ((*dest_temp++ = *str_temp++) != '')
    {
    }
    *(dest_temp - 1) = 'Y';
    *(dest_temp + 2) = '';
    printf("src:  %s
", str);
    printf("dest: %s
", dest);
    for (int i = 0; i < len; i++)
    {
        printf("%d
", *(dest + i));
    }
    free(dest);

    // [] *
    char a1[] = "hello world !";
    //char *a2 = a1;
    char *a2 = &a1[0];
    printf("sizeof []: %d
", sizeof(a1));
    printf("sizeof * : %d
", sizeof(a2));
    printf("%c  %c
", *(a1 + 0), *(a2 + 0));
    // i[chArray] == *(chArray+i)
    printf("%c  %c
", 0[a1], *(a2 + 0));
    printf("%s  %s
", a1, a2);

    // const
    const char *p1;
    char const *p2 = NULL;
    p1 = a1;
    p1 = a2;
    //*(p1) = 'a'; error
    char * const p3 = a1;
    *(p3) = 'a';
    //p3 = a2; error    
    const char * const p4 = a1;
    //*(p4) = 'a'; error
    //p4 = a2; error
}

void visit_S(SElementType e)
{
    printf("%d ", e);
}
void visit_Q(QElementType e)
{
    printf("%d ", e);
}

// test stack, queue
int main()
{
    LinkStackNode *top = (LinkStackNode *)malloc(sizeof(LinkStackNode));
    top->data = 0;
    top->next = NULL;
    for (int i = 1; i < 30; i++)
    {
        LinkStack_Push(&top, i);
    }    
    while (!LinkStack_Empty(&top))
    {
        int showNode;
        LinkStack_Pop(&top, &showNode);
        printf("%d ", showNode);
    }
    printf("
---

");
    

    SequenceStack *S = (SequenceStack *)malloc(sizeof(SequenceStack));
    if (!S)
        return -1;
    SequenceStack_Init(S, 20);
    for (int i = 0; i < 30; i++)
    {
        SequenceStack_Push(S, i);
    }
    SequenceStack_Traverse(S, visit_S);
    printf("
");
    SequenceStack_Traverse(S, visit_S);
    printf("
");
    while (!SequenceStack_Empty(S))
    {
        int showNode;
        SequenceStack_Pop(S, &showNode);
        printf("%d ", showNode);
    }
    printf("
---

");


    LinkQueue *Q = (LinkQueue *)malloc(sizeof(LinkQueue));
    if (!Q)
        return -1;
    LinkQueue_Init(Q);
    for (int i = 0; i < 30; i++)
    {
        LinkQueue_Add(Q, i);
    }
    LinkQueue_Traverse(Q, visit_Q);
    printf("
");
    LinkQueue_Traverse(Q, visit_Q);
    printf("
");
    while (!LinkQueue_Empty(Q))
    {
        int showNode;
        LinkQueue_Delete(Q, &showNode);
        printf("%d ", showNode);
    }
    printf("
---

");


    SequenceQueue *SQ = (SequenceQueue *)malloc(sizeof(SequenceQueue));
    if (!SQ)
        return -1;
    if (!SequenceQueue_Init(SQ))
        return -1;
    for (int i = 0; i < 30; i++)
    {
        SequenceQueue_Add(SQ, i);
    }
    SequenceQueue_Traverse(SQ, visit_Q);
    printf("
");
    SequenceQueue_Traverse(SQ, visit_Q);
    printf("
");
    while (!SequenceQueue_Empty(SQ))
    {
        int showNode;
        SequenceQueue_Delete(SQ, &showNode);
        printf("%d ", showNode);
    }
    printf("
---

");


    SequenceQueue *CSQ = (SequenceQueue *)malloc(sizeof(SequenceQueue));
    if (!CSQ)
        return -1;
    if (!CircleSequenceQueue_Init(CSQ))
        return -1;
    for (int i = 0; i < 30; i++)
    {
        CircleSequenceQueue_Add(CSQ, i);
    }
    CircleSequenceQueue_Traverse(CSQ, visit_Q);
    printf("
");
    CircleSequenceQueue_Traverse(CSQ, visit_Q);
    printf("
");
    while (!CircleSequenceQueue_Empty(CSQ))
    {
        int showNode;
        CircleSequenceQueue_Delete(CSQ, &showNode);
        printf("%d ", showNode);
    }
    printf("
");
    for (int i = 0; i < 20; i++)
    {
        CircleSequenceQueue_Add(CSQ, i);
    }
    CircleSequenceQueue_Traverse(CSQ, visit_Q);
    printf("
");
    int temp;
    for (int i = 0; i < 5; i++)
        CircleSequenceQueue_Delete(CSQ, &temp);
    CircleSequenceQueue_Traverse(CSQ, visit_Q);
    printf("
");
    for (int i = 0; i < 20; i++)
    {
        CircleSequenceQueue_Add(CSQ, i);
    }
    CircleSequenceQueue_Traverse(CSQ, visit_Q);
    printf("
");
    printf("
---

");

    return 0;
}