前言
学了顺序表和链表，咱来拿它们玩儿点别的…
栈和队列
栈
概念
栈，一种线性表，具有 LIFO(Last In First Out) ——后进先出 的特性。
- 只在 栈顶 增删
实现
根据栈 后进先出 的特性，可以知道，只需要进行尾部的增删——数组是不二之选。
定义：
typedef int StackDataType;
typedef struct Stack
{
StackDataType* arr;
int top;
int capacity;
}ST;
- arr：动态开辟的数组
- top：栈顶下标
- capacity：容量
接口：
void StackInit(ST* ps);
void StackDestroy(ST* ps);
void StackPush(ST* ps, StackDataType x);
void StackPop(ST* ps);
StackDataType StackTop(ST* ps);
bool StackEmpty(ST* ps);
int StackSize(ST* ps);
接口实现：
初始化
- 目前有两种实现方案：
- 使用者在局部创建 栈 ，将其作为参数，调用初始化接口
- 初始化接口内部创建栈并返回，使用者接收返回值
- top 也有两种初始化：
- top = 0; 这里的 top 代表的是 栈顶元素的下一位置
- top = -1; 这里的 top 代表的是 栈顶元素
- 本次实现：“局部创建，传参初始化” + “top = 0”
void StackInit(ST* ps)
{
assert(ps);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
销毁
- 栈用realloc开辟的连续数组实现，所以free(ps->arr)可以直接全部释放
void StackDestroy(ST* ps)
{
assert(ps);
free(ps->arr);
ps->arr = NULL;
ps->top = ps->capacity = 0;
}
入栈
- 由于 开辟空间/扩容 的操作 只在这一个地方需要，所以不用专门封装扩容接口
- 栈满扩容
- 入栈，在栈顶操作（在数组尾部操作），由于咱们的 top 是 栈顶元素的下一位置，所以直接 ps->arr[ps->top] = x;
void StackPush(ST* ps, StackDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;
StackDataType* tmp = (StackDataType*)realloc(ps->arr, newCapacity * sizeof(StackDataType));
if (tmp == NULL)
{
perror("StackPush:realloc");
exit(-1);
}
else
{
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
ps->arr[ps->top] = x;
ps->top++;
}
出栈
- 栈空不出
void StackPop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
ps->top--;
}
获取栈顶
- 栈空不取（拿也要合理地拿）
- top 是 栈顶元素的下一位置，所以栈顶元素是 arr[top-1]
StackDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->arr[ps->top-1];
}
判空
- top == 0 代表栈空
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
获取大小
- top 是 栈顶元素的下一位置，同时能表示 栈内元素数量
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
接口测试：
void TestStack()
{
//测试入栈
printf("StackPush&StackTop Testing...\n");
ST st1;
//测试入栈
printf("StackPush&StackTop Testing...\n");
ST st1;
//测试初始化
StackInit(&st1);
StackPush(&st1, 1);
StackPush(&st1, 2);
StackPush(&st1, 3);
StackPush(&st1, 4);
StackPush(&st1, 5);
StackPush(&st1, 6);
StackPush(&st1, 7);
StackPush(&st1, 8);
StackPush(&st1, 9);
while (!StackEmpty(&st1))
{
printf("%d ", StackTop(&st1));
StackPop(&st1);
}
printf("\n");
//测试销毁
StackDestroy(&st1);
//测试出栈
printf("StackPop Testing...\n");
ST st2;
StackInit(&st2);
StackPush(&st2, 1);
StackPush(&st2, 2);
StackPush(&st2, 3);
StackPop(&st2);
StackPop(&st2);
StackPop(&st2);
//StackPop(&st2);
//测试判空
printf("StackEmpty Testing...\n");
printf("IsEmpty:");
if (StackEmpty(&st2))
printf("Yes\n");
else
printf("No\n");
//测试获取栈顶
printf("StackTop Testing...\n");
StackPush(&st2, 1);
StackDataType top = StackTop(&st2);
printf("top: %d\n", top);
//测试获取大小
printf("StackSize Testing...\n");
int size = StackSize(&st2);
printf("size: %d\n", size);
StackDestroy(&st2);
}
int main()
{
TestStack();
return 0;
}
-
测试初始化：
-
-
测试销毁：
-
测试入栈：能否扩容，是否成功入栈？
-
测试出栈：是否成功出栈，空栈接着出会不会报错？
-
测试判空：判断是否正确
-
测试获取栈顶：能否正确获取？
-
测试获取大小：能否正确获取？
队列
概念
队列，一种线性表，具有 FIFO(First In First Out)——先进先出 的特性。
- 头删
- 尾插
实现
根据队列 先进先出 的特性，可以知道，需要头删，尾插。数组头部操作要挪元素，效率低；但单向链表尾部操作效率也不高啊。
数组头部操作的低效率已经没法改变，但链表中可不止单链表，别的结构则能满足头尾操作效率都高的要求。
接下来看看如何用链表实现队列吧：
定义：
队列的定义有两部分：
- 队列结点 QueueNode
- val：元素值
- next：保存下一结点地址
- 队列结构 Queue
- 队列头指针、队列尾指针、队列大小（队列的核心就是头尾，常用则直接封在结构体内）
- head：指向 队列头节点
- tail：指向 队列尾结点
- size：队列中元素的数量（经常使用，所以封装）
- 队列头指针、队列尾指针、队列大小（队列的核心就是头尾，常用则直接封在结构体内）
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType val;
struct QueueNode* next;
}QNode;
typedef struct Queue
{
QNode* head;
QNode* tail;
int size;
}Queue;
解惑：为什么这么封装？
按照链表以往的结构，都只是封装一个 ListNode结构体，但是为什么队列还要封装 Queue 呢？
可以这么理解：
- QueueNode 和 链表 一样，是为了达到 链表结构存储数据 的基本需要
- Queue ，则是队列的 基本框架，囊括了队列的核心——头、尾
- 封装出基本框架，再于基本框架上增删结点，舒服滴很
接口：
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QueueDataType x);
void QueuePop(Queue* pq);
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
接口实现：
初始化
-
定义一个 Queue q，q 内有：
- head
- tail
- size
所以，全部置零值，创建出 队列基本框架
#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* pq)
{
assert(pq);
pq->head = NULL;
pq->tail = NULL;
pq->size = 0;
}
销毁
- 既然是链表，每个结点都单独开辟，自然要遍历释放
void QueueDestroy(Queue* pq)
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
QNode* del = cur;
cur = cur->next;
free(del);
}
pq->head = NULL;
pq->tail = NULL;
}
入队
- 创建结点
- 尾插（队列特性）
void QueuePush(Queue* pq, QueueDataType x)
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror("QueuePush:malloc");
exit(-1);
}
else
{
newnode->val = x;
newnode->next = NULL;
if (pq->head == NULL)
{
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
pq->size++;
}
出队
- 队空不出
- 头删（队列特性）
void QueuePop(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
if (pq->head->next == NULL)
{
pq->head = pq->tail = NULL;
}
else
{
QNode* del = pq->head;
pq->head = pq->head->next;
free(del);
del = NULL;
}
pq->size--;
}
获取队头
- 队不为空（拿也要合理地拿）
QueueDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->val;
}
获取队尾
- 队不为空（拿也要合理地拿）
QueueDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->val;
}
判空
- 根据队列特性判断即可
bool QueueEmpty(Queue* pq)
{
return pq->head == NULL && pq->tail == NULL;
}
获取大小
- 因为常常使用，所以直接封在结构体里了，这边拿到size返回即可
int QueueSize(Queue* pq)
{
assert(pq);
return pq->size;
}
接口测试：
void TestQueue()
{
Queue q;
//测试初始化
QueueInit(&q);
//测试判空
printf("QueueEmpty Testing...\n");
printf("IsEmpty: ");
if (QueueEmpty(&q))
printf("Yes\n");
else
printf("No\n");
//测试入队
printf("QueuePush Testing...\n");
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePush(&q, 5);
QueuePush(&q, 6);
QueuePush(&q, 7);
QueuePush(&q, 8);
QueuePush(&q, 9);
while (!QueueEmpty(&q))
{
printf("%d ", QueueFront(&q));
QueuePop(&q);
}
printf("\n");
//测试出队
printf("QueuePop Testing...\n");
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePop(&q);
QueuePop(&q);
//QueuePop(&q);
printf("IsEmpty: ");
if (QueueEmpty(&q))
printf("Yes\n");
else
printf("No\n");
//测试获取队头
printf("QueueFront Testing...\n");
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
printf("front: %d\n", QueueFront(&q));
//测试获取队尾
printf("QueueBack Testing...\n");
printf("Back: %d\n", QueueBack(&q));
//测试获取队列大小
printf("QueueBack Testing...\n");
printf("Size: %d\n", QueueSize(&q));
//测试销毁
QueueDestroy(&q);
}
-
测试初始化
-
测试销毁
-
测试判空：是否正确判断？
-
测试入队：能否成功扩充，是否完成入队？
-
测试出队：是否完成出队，队空出队会不会断言？
-
测试获取队头：能否正确获取？
-
测试获取队尾：能否正确获取？
-
测试获取队列大小：能否正确获取？
本期的分享就到这啦，不足之处望请斧正！