數據結構就是定義出某種結構：像數組結構、鏈表結構、樹形結構等，實現數據結構就是我們主動去管理增刪查改的實現函數

棧的概念及實現

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作，入數據在棧頂，出數據也在棧頂

在編程實現之前，我們先看下棧入數據在棧頂，出數據也在棧頂的圖形界面

下面編程實現數組棧的使用，在頭文件 Stack.h 進行聲明，在 Stack.c 當中進行具體的函數定義，在 test.c 當中的做具體的測試實現

先來了解一下頭文件 Stack.h?當中接口

#pragma once//防止重復使用
#include<stdio.h>
#include<stdlib.h>//開內存需要頭文件
#include<stdbool.h>//bool判斷
#include<assert.h>//斷言頭文件

//typedef 下方指針申請類型，之后想換可以將int改成double、char等
typedef int STDateType;

typedef struct Stack
{
 STDateType* a;//指向動態開辟的數組
 int top;//棧頂的位置
 int capacity;//記錄存儲空間容量
}Stack;

//函數聲明 
void StackInit(Stack* ps);//初始化
void StackDestroy(Stack* ps);//置空函數，釋放空間
void StackPush(Stack* ps, STDateType x);//棧頂插入
void StackPop(Stack*);//棧頂刪除數據
bool StackEmpty(Stack*);//判斷棧是否為空
int StackSize(Stack*);//棧的數據大小
STDateType StackTop(Stack* ps);//取棧頂數據

我們知道，函數的定義方法是非常重要的，也是我們需要深入理解的，下面我們詳細學習在 Stack.c 當中具體的函數實現

初始化函數定義

void StackInit(Stack* ps)//初始化
{
assert(ps);
ps->a = NULL;
ps->top = 0;//給0是top指向棧頂數據的下一個
//ps->top = -1; 給-1是top指向棧頂數據
ps->capacity = 0;
}

置空函數定義

置空函數一般會放在我們進行插入或刪除的函數最后，釋放我們在堆上申請的空間，將其還給操作系統，另外也會相應的進行檢查越界等問題

void StackDestroy(Stack* ps)
{
//開辟空間需要置空，使用該函數
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}

棧頂插入函數

void StackPush(Stack* ps, STDateType x)//入棧函數
 //想清楚在前面初始化中top標識的是什么
{
 assert(ps);
 //滿了擴容
if (ps->top == ps->capacity)
{
 int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
 STDateType* tmp = 
 (STDateType*)realloc(ps->a, newcapacity * sizeof(STDateType));
if (tmp == NULL)
{
 printf("realloc fial\n");
 exit(-1);//異常退出，直接終止
}
 //到這里開空間成功
 ps->a = tmp;//把空間給a
 ps->capacity = newcapacity;//空間容量更新
}	
 ps->a[ps->top] = x;//先將數據放到top位置
 ps->top++;
} 

判斷數據為空函數

bool StackEmpty(Stack* ps)//判斷棧是否為空
{
assert(ps);
return ps->top == 0;
//注意top的初始化
}

棧頂刪除函數

void StackPop(Stack* ps)//刪除數據
{
assert(ps);
assert(!StackEmpty(ps));//判斷不為空
//assert(ps->top > 0);//判斷不為空
ps->top--;
}

棧的數據大小

//棧的數據大小 棧頂的下一個就是size 
//top就是
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}

取棧頂數據

STDateType StackTop(Stack* ps)//取棧頂數據
{
assert(ps);
assert(!StackEmpty(ps));//判斷不為空
//assert(ps->top > 0);//判斷不為空
return ps->a[ps->top - 1];
}

我們用上面接口實現一個在 test.c 當中的測試案例?TestStack 1

void TestStack1()//后進先出
{
 Stack st;
 StackInit(&st);
 StackPush(&st, 1);//入棧 1 2 3 
 StackPush(&st, 2);
 StackPush(&st, 3);

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

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

 printf("<-出3 2\n");
 StackPush(&st, 4);//在有1的基礎上入4 5 6
 StackPush(&st, 5);
 StackPush(&st, 6);
	
 //注意不能隨便遍歷 要保證后進先出
 while(!StackEmpty(&st))
 {
  printf("%d ", StackTop(&st));//此時打印6 5 4 1
  StackPop(&st);
 }
 printf("\n");

 StackDestroy(&st);//置空函數，放在最后
}
int main()
{
 TestStack1();
 return 0;
}

隊列的概念及實現

隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊尾入數據，隊頭出數據

下面編程實現鏈式隊列的使用，在頭文件 Queue.h 進行聲明，在 Queue.c 當中進行具體的函數定義，在 test.c 當中的做具體的測試實現

在編程實現之前，我們要先理解下隊列，隊尾入，隊頭出的圖形界面

先來了解一下頭文件 Queue.h?當中接口

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

//鏈式實現隊列

typedef int QDataType;

typedef struct QueueNode//定義節點 
{
 struct QueueNode* next;
 QDataType data;
}QueueNode;

//不帶頭 
typedef struct Queue
{
 QueueNode* head;//定義頭指針
 QueueNode* tail;//定義尾指針
}Queue;

//函數聲明
void QueueInit(Queue* ps);//初始化 
void QueueDestroy(Queue* ps);//置空函數 
void QueuePush(Queue* ps,QDataType x);//隊尾入數據
void QueuePop(Queue* ps);//隊頭出數據 刪除數據 鏈表頭刪
QDataType QueueFront(Queue* ps);//取隊頭數據
QDataType QueueBack(Queue* ps); //取隊尾數據
int QueueSize(Queue* ps); //數據的個數
bool QueueEmpty(Queue* ps);//判斷是否為空

下面接著詳細學習在 Queue.c 當中具體的函數實現

初始化函數定義

void QueueInit(Queue* ps)//初始化
{
//不帶頭
assert(ps);
ps->head = NULL;
ps->tail = NULL;
}

置空函數定義

置空函數一般會放在我們進行插入或刪除的函數最后，釋放我們在堆上申請的空間，將其還給操作系統，另外也會相應的進行檢查越界等問題

void QueueDestroy(Queue* ps)//置空函數
{
assert(ps);
QueueNode* cur = ps->head;
while (cur != NULL)//等于空就結束
 {
 //刪除當前位置，先保存下一個
 QueueNode* next = cur->next;
 free(cur);
 cur = next;
 }
 ps->head = ps->tail = NULL;
}

隊尾入數據

void QueuePush(Queue* ps, QDataType x)//隊尾入數據
{
assert(ps);
QueueNode* newnode =(QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
 {
  printf("malloc fail\n");
  exit(-1);
 }
 newnode->data = x;
 newnode->next = NULL;

if (ps->tail == NULL)
 {
  ps->head = ps->tail = newnode;
 }
else
 {
  ps->tail->next = newnode;
  ps->tail = newnode;
 }	
}

判斷是否為空

bool QueueEmpty(Queue* ps)//判斷是否為空
{
assert(ps);	
return ps->head = NULL;
}

隊頭出數據

//注意head指向空了但是tail是野指針的問題 
void QueuePop(Queue* ps)//隊頭出數據 刪除數據
{
assert(ps);
assert(!QueueEmpty(ps));
if (ps->head->next == NULL)
 {
  free(ps->head);
  ps->head = ps->tail=NULL;
 }
else
 {
  QueueNode* next = ps->head->next;
  free(ps->head);
  ps->head = next;
 }	
}

取隊頭數據函數定義

QDataType QueueFront(Queue* ps)//取隊頭數據
{
 assert(ps);
 // assert(ps->head);
 assert(!QueueEmpty(ps));
 return ps->head->data;
}

取隊尾數據函數定義

QDataType QueueBack(Queue* ps) //取隊尾數據
{
 assert(ps);
 assert(!QueueEmpty(ps));
 return ps->tail->data;
}

數據的個數函數定義

int QueueSize(Queue* ps)//數據的個數
{
assert(ps);
int n = 0;
QueueNode* cur = ps->head;
while (cur)
{
 ++n;
 cur = cur->next;
}
 return n;
}

我們用上面接口實現一個在 test.c 當中的測試案例?TestQueue1?

void TestQueue1()
{
 Queue q;
 QueueInit(&q);
 QueuePush(&q, 1);
 QueuePush(&q, 2);
 QueuePush(&q, 3);
 QueuePush(&q, 4);
 //先進先出
 while (!QueueEmpty(&q))
 {
   QDataType front = QueueFront(&q);
   printf("%d ", front);
   QueuePop(&q);
 }
  printf("\n");
  QueueDestroy(&q);//置空函數放在最后
}

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

在Java和C++的學習當中，前期學習數據結構當中的順序表、鏈表、棧和隊列等便于我們后面更好的學習容器，后面會繼續分享二叉樹和算法的實現

希望這篇文章大家有所收獲，我們下篇見