栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端

称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的定义

<code>typedef int STDataType;

typedef struct Stack

{

STDataType* _a;//数组

int _top; // 栈顶,类似顺序表中的_size

int _capacity; // 容量

}Stack;

对栈的操作

栈初始化

_top可以初始化为0，此时栈顶元素是_top-1的位置

_top也可以初始化为1，此时栈顶元素就是_top的位置

初始化为0

初始化为1

<code>// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);

ps->;_a = NULL;

ps->_capacity = 0;

ps->_top = 0;

}

压栈（入栈）

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

//扩容

if (ps->_capacity == ps->_top)

{

int newcapacity = ps->_capacity == 0 ? 4 : 2 * (ps->_capacity);

STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc fail");

return;

}

ps->_a = tmp;

ps->_capacity = newcapacity;

}

ps->_a[ps->_top++] = data;

}

出栈

void StackPop(Stack* ps)

{

assert(ps);

assert(!StackEmpty(ps));

ps->_top--;

}

取栈顶元素

STDataType StackTop(Stack* ps)

{

assert(ps);

return ps->_a[ps->_top-1];

}

判断栈是否为空

bool StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top == 0;

}

栈的长度

_top初始化为0，此时的_top的大小刚好就是栈的长度

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

栈销毁

void StackDestroy(Stack* ps)

{

assert(ps);

ps->_capacity = ps->_top = 0;

free(ps->_a);

ps->_a = NULL;

}

完整总代码

头文件

#pragma once

#include<stdio.h>

#include<assert.h>

#include<stdlib.h>

#include<stdbool.h>

// 支持动态增长的栈

typedef int STDataType;

typedef struct Stack

{

STDataType* _a;//数组

int _top; // 栈顶,类似顺序表中的_size

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);

函数定义

#include"Stack.h"

// 初始化栈

void StackInit(Stack* ps)

{

assert(ps);

ps->_a = NULL;

ps->_capacity = 0;

ps->_top = 0;

}

// 入栈

void StackPush(Stack* ps, STDataType data)

{

assert(ps);

//扩容

if (ps->_capacity == ps->_top)

{

int newcapacity = ps->_capacity == 0 ? 4 : 2 * (ps->_capacity);

STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));

if (tmp == NULL)

{

perror("realloc fail");

return;

}

ps->_a = tmp;

ps->_capacity = newcapacity;

}

ps->_a[ps->_top++] = data;

}

// 出栈

void StackPop(Stack* ps)

{

assert(ps);

assert(!StackEmpty(ps));

ps->_top--;

}

// 获取栈顶元素

STDataType StackTop(Stack* ps)

{

assert(ps);

return ps->_a[ps->_top-1];

}

// 获取栈中有效元素个数

int StackSize(Stack* ps)

{

assert(ps);

return ps->_top;

}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0

bool StackEmpty(Stack* ps)

{

assert(ps);

return ps->_top == 0;

}

// 销毁栈

void StackDestroy(Stack* ps)

{

assert(ps);

ps->_capacity = ps->_top = 0;

free(ps->_a);

ps->_a = NULL;

}

测试

#include"Stack.h"

void test()

{

Stack s;

StackInit(&s);

StackPush(&s, 1);

StackPush(&s, 2);

StackPush(&s, 3);

StackPush(&s, 4);

while (StackSize(&s)>0)

{

printf("%d ", StackTop(&s));

StackPop(&s);

}

StackDestroy(&s);

}

int main()

{

test();

return 0;

}

欢迎各位一起学习交流~