文章目录
前言
栈：一种特殊的线性结构，其只允许在一端进行插入，删除数据。允许操作数据的一端被称为栈顶，另一端被称为栈底。
本篇博客将要实现的是数组栈。
一、栈的实现思路
对于栈的特殊性，用数组(在数组尾部插入删除数据) 和 链表(头插头删数据)实现栈的时间复杂度都是O(1)，难度不大。
数组栈的优劣
优
- 数组支持随机访问(用下标访问数据)，许多算法需要随机访问的支持，如二分法…
- 缓存利用率高
劣
- 空间不够时要扩容
- 有时会造成空间浪费
1. 结构的定义
栈的结构非常简单
一个指向动态开辟空间的指针，一个记录实际空间大小的变量，一个记录栈顶元素的下标即可。
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top;//栈顶下标
int capacity;//空间大小
}Stack;
2. 初始化栈(StackInit)
data指针指向动态开辟的空间，capacity记录此时空间大小，top置为0。
- top 置0，表示栈顶数据将要插入的位置。
- top 置-1，表示此时栈顶数据的位置。
这里，采用top 置0。
//初始化栈
#define SIZE 4
void StackInit(Stack* ps)
{
assert(ps);
ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);
if (ps->data == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
ps->capacity = SIZE;
}
3. 入栈(StackPush)
因为top初始化为0，所以直接在top下标处入数据即可。但要注意，在入数据前要检查容量，如果top == capacity 要扩容。
- 此处检查容量的操作，可以封装成一个函数，但没必要，因为栈的操作只有入栈要检查容量，其它的操作并不需要检查容量，封装成一个函数反而效率减低了(函数的调用要形成函数栈帧)。
//入栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->data = tmp;
ps->capacity *= 2;
}
ps->data[ps->top] = x;
ps->top++;
}
4. 出栈(StackPop)
top 表示的是栈顶数据将要入栈的位置，那么出栈操作，只需要让top 减 1即可。(下次入栈数据会直接覆盖)
但要注意，top = 0 时，表示栈内没有数据，不能进行出栈操作。
- 出栈操作不能获取数据
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top != 0);
ps->top--;
}
5. 获取栈顶元素(StackTop)
top 指向的是数据将要入栈的位置，也就是栈顶数据的下一个位置。
那么要获取栈顶数据，只需要读取top - 1处即可。但要注意，如果top = 0，那么top - 1 = -1，会越界访问，所以top = 0 时，不能获取栈顶元素。
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->data[ps->top - 1];
}
6. 检查栈是否为空(StackEmpty)
top 指向的是数据将要入栈的位置，其数值也表示栈内数据个数。
所以我们只需要进行 top == 0 的判断，即可知道栈是否为空。
//检查栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
7. 销毁栈(StackDestroy)
free掉动态开辟的空间，使capacity 置 0，top 置 0。
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->top = 0;
ps->capacity = 0;
}
二、代码实现
Stack.h 文件存放的是函数的声明，头文件的引用，结构体的定义
Stack.c 文件存放的是函数的实现
//Stack.h 文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define SIZE 4
typedef int STDataType;
typedef struct Stack
{
STDataType* data;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);
//检查栈是否为空
bool StackEmpty(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);
//Stack.c 文件
#include "Stack.h"
//初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->data = (STDataType*)malloc(sizeof(STDataType) * SIZE);
if (ps->data == NULL)
{
perror("malloc");
exit(-1);
}
ps->top = 0;
ps->capacity = SIZE;
}
//入栈
void StackPush(Stack* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
STDataType* tmp = (STDataType*)realloc(ps->data, sizeof(STDataType) * (ps->capacity * 2));
if (tmp == NULL)
{
perror("realloc");
exit(-1);
}
ps->data = tmp;
ps->capacity *= 2;
}
ps->data[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(Stack* ps)
{
assert(ps);
assert(ps->top != 0);
ps->top--;
}
//获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->data[ps->top - 1];
}
//检查栈是否为空
bool StackEmpty(Stack* ps)
{
assert(ps);
return ps->top == 0;
}
//销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->data);
ps->top = 0;
ps->capacity = 0;
}
总结
以上就是我对于栈的实现。