文章目录
- 一、栈
- 1. 栈的概念
- 2. 栈的基本功能
- 3. 栈的实现
- 二、 队列
- 1. 队列的概念
- 2. 队列的基本功能
- 3. 队列的实现
一、栈
1. 栈的概念
栈是一种特殊的线性表，限定仅在表尾进行插入和删除的线性表。这一端称之为栈顶，另一端称为栈底。
栈又称为后进先出（Last In First Out）的线性表，简称LIFO结构
2. 栈的基本功能
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
3. 栈的实现
栈的实现一般使用数组或者链表，因为cpu高速缓存的原因，使用数组也非常ok。
创建三个文件
头文件：
Stack.h
源文件：
Stack.c
test.c(测试功能是否能实现)
结构体的定义和函数声明：
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top; // 栈顶
int capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
实现方法：
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->a = NULL;
ps->capacity = 0;
//指向栈顶元素的下一个位置
ps->top = 0;
//top指向栈顶元素
//ps->top = -1;
}
ps->a我们有两种初始化方法，一种是直接malloc一个空间，可以是四个或者八个对象的空间，也可以像我一样，先不开，等会入栈的时候再开。
在进行入栈以前，先把top指向为栈顶的下一个数据，如果指向栈顶数据的话，初始化就不能为0。
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
//扩容
if (ps->capacity == ps->top)
{
//初始化不开空间，当我插入数据时再开
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//用realloc因为在第一个指针为空时，realloc可以实现malloc的功能
STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top] = data;//把数据直接放在top
ps->top++;//top往后走到栈顶下一个数据
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);//只有当栈不为空时才能出栈
ps->top--;
}
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
/ 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top-1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->top;
}
二、 队列
1. 队列的概念
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。
队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
2. 队列的基本功能
//初始化
void QueueInit(Queue* qp);
//销毁
void QueueDestroy(Queue* qp);
//队尾插入
void QueuePush(Queue* qp, QDatatype x);
//对头删除
void QueuePop(Queue* qp);
//取头和尾的数据
QDatatype QueueFront(Queue* qp);
QDatatype QueueBack(Queue* qp);
//获取队列元素个数
int QueueSize(Queue* qp);
//判空
bool QueueEmpty(Queue* qp);
3. 队列的实现
队列的实现用单链表就能很好的解决
创建三个文件
头文件：Queue.h
源文件：
Queue.c
test.c(测试功能是否能实现)
#pragma once
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>
#include <stdlib.h>
typedef int QDatatype;
typedef struct QNode
{
struct Queue* next;
QDatatype val;
}QNode;
typedef struct Queue
{
QNode* phead;
QNode* ptail;
int size;//可以提高效率，删除就减去size，插入就增加size
}Queue;
//初始化Queue
//销毁
void QueueInit(Queue* qp);
void QueueDestroy(Queue* qp);
//void QueuePush(Queue** phead, Queue** ptail， QDatatype x);
//void QueuePop(Queue** phead, Queue** ptail);
//队尾插入和对头删除需要标记节点，还有更简便的方法，再创建一个结构体，名为Queue
//改变结构体的内容只需要传一级指针就行
//队尾插入
void QueuePush(Queue* qp, QDatatype x);
//对头删除
void QueuePop(Queue* qp);
//取头和尾的数据
QDatatype QueueFront(Queue* qp);
QDatatype QueueBack(Queue* qp);
//获取队列元素个数
int QueueSize(Queue* qp);
//判空
bool QueueEmpty(Queue* qp);
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
//初始化
//销毁
void QueueInit(Queue* qp)
{
assert(qp);
qp->phead = NULL;
qp->ptail = NULL;
qp->size = 0;
}
void QueueDestroy(Queue* qp)
{
assert(qp);
QNode* cur = qp->phead;
while (cur)
{
QNode* next = cur->next;
free(cur);
cur = next;
}
//释放完空间后需要把phead和ptail置空，不然就为野指针了
qp->phead = NULL;
qp->ptail = NULL;
qp->size = 0;
}
//队尾插入
void QueuePush(Queue* qp, QDatatype x)
{
assert(qp);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->next = NULL;
newnode->val = x;
//一个节点都没有
if (qp->phead == NULL)
{
qp->phead = qp->ptail = newnode;
}
//有一个节点
else
{
qp->ptail->next = newnode;//newnode成为新的尾
qp->ptail = newnode;
}
qp->size++;
}
//对头删除
void QueuePop(Queue* qp)
{
assert(qp);
assert(qp->size != 0);
if (qp->size == 1)//只剩一个节点
{
free(qp->phead);
qp->phead = qp->ptail = NULL;//避免野指针
}
else//多个节点
{
QNode* next = qp->phead->next;
free(qp->phead);
qp->phead = next;
}
qp->size--;
}
//取头和尾的数据
QDatatype QueueFront(Queue * qp)
{
assert(qp);
return qp->phead->val;
}
QDatatype QueueBack(Queue * qp)
{
assert(qp);
assert(qp->phead);
return qp->ptail->val;
}
int QueueSize(Queue* qp)
{
assert(qp);
assert(qp->ptail);
return qp->size;//因为记录了size，所以直接返回size就行，不用遍历
}
bool QueueEmpty(Queue* qp)
{
assert(qp);
return qp->size == 0;
}
希望这篇博客对你有所帮助！！！
