数据结构：详解【栈和队列】的实现

目录 1. 栈1.1 栈的概念及结构1.2 栈的实现1.3 栈的功能1.4 栈的功能的实现1.5 完整代码 2. 队列2.1 队列的概念及结构2.2 队列的实现2.3 队列的功能2.4 队列的功能的实现2.5 完整代码

1. 栈 1.1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈。入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾插和头删的实际复杂度为O(1)，是非常合适的。

1.3 栈的功能 初始化栈销毁栈入栈出栈获取栈顶元素获取栈内有效元素的个数判断栈内是否为空，如果为空返回非0结果，不为空返回0 1.4 栈的功能的实现

（1）定义一个动态增长的栈

typedef int STDataType; typedef struct Stack { STDataType* a; STDataType top;//定义栈顶 size_t capacity;//栈的容量 }ST;

（2）初始化栈

void StackInit(ST* ps) { //初始化空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail!\n"); return; } ps->top = 0; ps->capacity = 4;//初始化4个空间 }

（3）销毁栈

void StackDestory(ST* ps) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; }

（4）入栈（相当于顺序表的尾插）

void StackPush(ST* ps, STDataType x) { //插入数据之前判断是否增容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2); if (tmp == NULL) { printf("realloc fail!\n"); return; } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; }

（5）出栈（相当于顺序表的头删）

void StackPop(ST* ps) { assert(ps);//断言，栈内为空则终止程序 ps->top--; }

（6）获取栈顶元素

STDataType StackTop(ST* ps) { assert(ps);//断言，栈内为空则终止程序 assert(ps->top > 0); return ps->a[ps->top - 1]; }

（7）获取栈内有效元素的个数

int StackSize(ST* ps) { assert(ps); return ps->top; }

（8）判断栈内是否为空，如果为空返回非0结果，不为空返回0

bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; } 1.5 完整代码

Stack.h

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int STDataType; typedef struct Stack { STDataType* a; STDataType top;//定义栈顶 size_t capacity;//栈的容量 }ST; //初始化栈 void StackInit(ST* ps); //销毁栈 void StackDestory(ST* ps); //从栈顶插入数据 void StackPush(ST* ps, STDataType x); //从栈顶删除数据 void StackPop(ST* ps); //获取栈顶元素 STDataType StackTop(ST* ps); //获取栈内有效元素个数 int StackSize(ST* ps); //判断栈内是否为空，如果为空返回非0结果，不为空返回0 bool StackEmpty(ST* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" void StackInit(ST* ps) { //初始化空间 ps->a = (STDataType*)malloc(sizeof(STDataType) * 4); if (ps->a == NULL) { printf("malloc fail!\n"); return; } ps->top = 0; ps->capacity = 4;//初始化4个空间 } void StackDestory(ST* ps) { free(ps->a); ps->a = NULL; ps->capacity = 0; ps->top = 0; } void StackPush(ST* ps, STDataType x) { //插入数据之前判断是否增容 if (ps->top == ps->capacity) { STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * sizeof(STDataType) * 2); if (tmp == NULL) { printf("realloc fail!\n"); return; } else { ps->a = tmp; ps->capacity *= 2; } } ps->a[ps->top] = x; ps->top++; } void StackPop(ST* ps) { assert(ps);//断言，栈内为空则终止程序 ps->top--; } STDataType StackTop(ST* ps) { assert(ps);//断言，栈内为空则终止程序 assert(ps->top > 0); return ps->a[ps->top - 1]; } int StackSize(ST* ps) { assert(ps); return ps->top; } bool StackEmpty(ST* ps) { assert(ps); return ps->top == 0; }

Test.c

#define _CRT_SECURE_NO_WARNINGS #include "Stack.h" void StackTest() { ST st; StackInit(&st); StackPush(&st, 1); StackPush(&st, 2); StackPush(&st, 3); StackPush(&st, 4); //打印栈内的数据，由于不能破坏栈的特性，所以不能遍历 while (!StackEmpty(&st)) { printf("%d ", StackTop(&st)); StackPop(&st); } StackDestory(&st); } int main() { StackTest(); return 0; } 2. 队列 2.1 队列的概念及结构

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

2.2 队列的实现

队列也可以数组和链表的结构实现，使用单链表的结构实现更优一些。 因为如果使用数组的结构，出队列在数组头上出数据，这时需要挪动数据，时间复杂度为O(n)，效率会比较低。 而单链表的尾插和头删的时间复杂度为O（1），十分合适。

2.3 队列的功能 初始化队列销毁队列入队列出队列获取队列头部元素获取队列尾部元素获取队列中有效元素的个数判断队列是否为空，为空返回非0，不为空返回0 2.4 队列的功能的实现

（1）定义一个队列

typedef int QTDataType; typedef struct QNode { struct QNode* next; QTDataType data; }QNode; typedef struct Queue { struct QNode* tail; struct QNode* head; }Queue;

（2）初始化队列

void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; }

（3）销毁队列

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

（4）入队列(相当于单链表的尾插）

void QueuePush(Queue* pq, QTDataType x) { assert(pq); QNode* newnode = (QTDataType*)malloc(sizeof(QTDataType)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; //第一个结点 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } //多个节点 else { pq->tail->next = newnode; pq->tail = newnode; } }

（5）出队列（相当于单链表的头删）

void QueuePop(Queue* pq) { assert(pq); assert(pq->head); //只有一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { //保存下一个节点的地址 QNode* next = pq->head->next; free(pq->head); pq->head = next; } }

（6）获取队列头部元素

QTDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; }

（7）获取队列尾部元素

QTDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; }

（8）获取队列中有效元素的个数

int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }

（9）判断队列是否为空，为空返回非0，不为空返回0

int QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } 2.5 完整代码

Queue.h

#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int QTDataType; typedef struct QNode { struct QNode* next; QTDataType data; }QNode; typedef struct Queue { struct QNode* tail; struct QNode* head; }Queue; //初始化队列 void QueueInit(Queue* pq); //销毁队列 void QueueDestory(Queue* pq); //队尾入队列 void QueuePush(Queue* pq, QTDataType x); //队头出队列 void QueuePop(Queue* pq); //获取队列头部元素 QTDataType QueueFront(Queue* pq); //获取队列尾部元素 QTDataType QueueBack(Queue* pq); //判断队列是否为空，为空返回非0，不为空返回0 int QueueEmpty(Queue* pq); //获取队列中有效元素的个数 int QueueSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" void QueueInit(Queue* pq) { assert(pq); pq->head = pq->tail = NULL; } void QueueDestory(Queue* pq) { assert(pq); QNode* cur = pq->head; while (cur) { cur = cur->next; free(cur); } pq->head = pq->tail = NULL; } void QueuePush(Queue* pq, QTDataType x) { assert(pq); QNode* newnode = (QTDataType*)malloc(sizeof(QTDataType)); if (newnode == NULL) { printf("malloc fail!\n"); return; } newnode->data = x; newnode->next = NULL; //第一个结点 if (pq->tail == NULL) { pq->head = pq->tail = newnode; } //多个节点 else { pq->tail->next = newnode; pq->tail = newnode; } } void QueuePop(Queue* pq) { assert(pq); assert(pq->head); //只有一个节点 if (pq->head->next == NULL) { free(pq->head); pq->head = pq->tail = NULL; } else { //保存下一个节点的地址 QNode* next = pq->head->next; free(pq->head); pq->head = next; } } int QueueEmpty(Queue* pq) { assert(pq); return pq->head == NULL; } QTDataType QueueFront(Queue* pq) { assert(pq); assert(pq->head); return pq->head->data; } QTDataType QueueBack(Queue* pq) { assert(pq); assert(pq->head); return pq->tail->data; } int QueueSize(Queue* pq) { assert(pq); int size = 0; QNode* cur = pq->head; while (cur) { size++; cur = cur->next; } return size; }

Test.c

#define _CRT_SECURE_NO_WARNINGS #include "Queue.h" void QueueTest() { Queue q; QueueInit(&q); QueuePush(&st, 1); QueuePush(&st, 2); QueuePush(&st, 3); QueuePush(&st, 4); //打印队列内的数据，由于不能破坏队列的特性，所以不能遍历 while (!QueueEmpty(&st)) { printf("%d ", QueueFront(&st)); QueuePop(&st); } QueueDestory(&q); } int main() { QueueTest(); return 0; }