栈的概念及结构 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。 进行数据插入和删除操作的一端称为 栈顶 ,另一端称为 栈底 。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。 压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在 栈顶。 出栈:栈的删除操作叫做出栈。 出数据也在 栈顶。 栈的结构:
实现栈的方式有两种: 顺序表和链表
优点: 1、任意位置插入删除O(1) 2、按需申请释放空间 缺点: 1、不支持下标随机访问 2、CPU高速缓存命中率会更低
优点:1、尾插尾删效率不错。 2、下标的随机访问。 3、CPU高速缓存命中率会更高 缺点: 1、前面部分插入删除数据,效率是O(N),需要挪动数据。 2、空间不够,需要扩容。a、扩容是需要付出代价的 b、一般还会伴随空间浪费。
综上所述,用顺序表实现栈更好。
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈顶
int capacity;//栈的容量
}ST;
// 初始化栈
void STInit(ST* pst);
// 入栈
void STPush(ST* pst, STDataType data);
// 出栈
void STPop(ST* pst);
// 获取栈顶元素
STDataType STTop(ST* pst);
// 获取栈中有效元素个数
int STSize(ST* pst);
// 检测栈是否为空,如果为空返回true,如果不为空返回false
bool STEmpty(ST* pst);
// 销毁栈
void STDestroy(ST* pst);
pst->top表示栈的顶部指针,通常情况下,它指向栈顶元素的下一个位置,而不是指向当前栈顶元素。通过 pst->top 可以确定栈中元素的个数,打印的时候记得将 top - 1。
void STInit(ST* pst)
{
assert(pst);//防止敲代码的人传过来是NULL指针
pst->a = NULL;//栈底
//top不是数组下标,不能理解成数组下标,因为栈只能拿到栈顶的元素,而数组可以随机访问拿到中间元素
//pst->top=-1;//指向栈顶元素
pst->top = 0;//指向栈顶元素的下一个位置
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
}
这里我们会运用到三目运算符
void STPush(ST* pst,STDataType x)
{
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;//返回的是realloc出来的内存块的地址
pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量
}
pst->a[pst->top] = x;//先放值
pst->top++;//再++
}
bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{
//写法一
//assert(pst);
//if (pst->top == 0)
//{
// return true;
//}
//else
//{
// return false;
//}
//写法二
return pst->top == 0;
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void TestStack1()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
while (!STEmpty(&st))
{
printf("%d ", STTop(&st));//栈顶元素
STPop(&st);
}
STDestroy(&st);
}
void TestStack2()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
printf("%d ", STTop(&st));
STPush(&st, 3);
STPush(&st, 4);
printf("\n");
printf("%d ", STTop(&st));
//printf("%d", STSize(&st));
//while (!STEmpty(&st))
//{
// printf("%d ", STTop(&st));//栈顶元素
// STPop(&st);
//}
STDestroy(&st);
}
void TestStack3()
{
ST st;
STInit(&st);
STPush(&st, 1);
STPush(&st, 2);
STPush(&st, 3);
STPush(&st, 4);
//printf("%d", STSize(&st));
STDestroy(&st);
}
int main()
{
TestStack1();//入栈出栈
//TestStack2();//获取栈顶元素
//TestStack3();//计算栈中有效元素个数
return 0;
}
#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<stdio.h>
typedef int STDataType;
typedef struct Stack
{
STDataType* a;
int top;//栈顶的位置
int capacity;//栈的容量
}ST;
void STInit(ST* pst);
void STDestroy(ST* pst);
void STPush(ST* pst,STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST*pst);
#define _CRT_SECURE_NO_WARNINGS 1
#include"Stack.h"
void STInit(ST* pst)
{
assert(pst);
pst->a = NULL;//栈底
//top不是下标
//pst->top=-1;//指向栈顶元素
pst->top = 0;//指向栈顶元素的下一个位置
pst->capacity = 0;
}
void STDestroy(ST* pst)
{
assert(pst);
free(pst->a);
pst->a = NULL;
}
void STPush(ST* pst,STDataType x)
{
if (pst->top == pst->capacity)
{
int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;//true,4.false,括2倍
STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));//返回值地址相等就是原地扩容,不同就是异地扩
if (tmp == NULL)
{
perror("realloc fail");
return;
}
pst->a = tmp;//返回的是realloc出来的内存块的地址
pst->capacity = newCapacity;//把扩容后的空间大小赋值给栈容量
}
pst->a[pst->top] = x;//先放值
pst->top++;//再++
}
void STPop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
pst->top--;
}
STDataType STTop(ST* pst)
{
assert(pst);
assert(!STEmpty(pst));
return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)//栈为空返回true,不为空返回false
{
//assert(pst);
//if (pst->top == 0)
//{
// return true;
//}
//else
//{
// return false;
//}
return pst->top == 0;
}
int STSize(ST* pst)
{
assert(pst);
return pst->top;
}