一、栈的概念及结构

1.栈的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

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

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

2.栈的结构

 

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

二、栈的实现

实现功能

StackInit                                                栈初始化
StackEmpty                                           判断栈是否为空
StackDestroy                                         栈销毁
StackPush                                             入栈
void StackPop                                       出栈
StackTop                                               返回栈的最顶层元素
StackSize                                              返回栈的大小

Stack.h

#pragma once#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>#define DEFAULT 4typedef int STDataType;
typedef struct Stack
{STDataType* a;	//数组栈int top;        //栈顶int capacity;   //容量
}Stack;extern void StackInit(Stack* ps);//栈初始化
extern bool StackEmpty(Stack* ps);//判断栈是否为空
extern void StackDestroy(Stack* ps);//栈销毁
extern void StackPush(Stack* ps, STDataType x);//入栈
extern void StackPop(Stack* ps);//出栈
extern STDataType StackTop(Stack* ps);//返回栈的最顶层元素
extern int StackSize(Stack* ps);//返回栈的大小

Stack.c

#include"Stack.h"void StackInit(Stack* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void StackDestroy(Stack* ps)
{assert(ps);free(ps->a);ps->a == NULL;ps->top = ps->capacity = 0;
}void StackPush(Stack* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int new_capacity = (ps->capacity) ? ps->capacity * 2 : DEFAULT;STDataType* ptr = realloc(ps->a, sizeof(STDataType) * new_capacity);if (!ptr){perror("realloc");exit(-1);}ps->a = ptr;ps->capacity = new_capacity;}ps->a[ps->top] = x;(ps->top)++;
}bool StackEmpty(Stack* ps)
{assert(ps);return ps->top == 0;
}void StackPop(Stack* ps)
{assert(ps);if (!StackEmpty(ps))(ps->top)--;elseprintf("The stack is empty!\n");
}STDataType StackTop(Stack* ps)
{assert(ps);if (!StackEmpty(ps))return ps->a[(ps->top) - 1];printf("The stack is empty!\n");
}int StackSize(Stack* ps)
{assert(ps);return ps->top;
}

test.c

#include"Stack.h"void test()
{Stack st;StackInit(&st);StackPush(&st, 1);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPush(&st, 2);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPush(&st, 3);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPush(&st, 4);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPush(&st, 5);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPush(&st, 6);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);printf("\n");StackPop(&st);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPop(&st);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPop(&st);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackPop(&st);printf("Top元素:%d\t当前存量:(%d/%d)\n", StackTop(&st), StackSize(&st), st.capacity);StackDestroy(&st);
}int main()
{test();return 0;
}