【数据结构与算法】栈和队列(上)

记录自己所学，无详细讲解

栈的实现--使用动态数组

1.项目目录文件

2.头文件 stack.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
struct Stack
{int* _a;int top;int capacity;
};
typedef struct Stack Stack;
void StackInit(Stack* p); //初始化
void StackDestory(Stack* p); //销毁
void StackPush(Stack* p,int n);//入栈
void StackPop(Stack* p);//出栈
int StackTop(Stack* p);//查看栈顶
int StackSize(Stack* p);//查看栈大小
bool StackEmpty(Stack* p);//栈是否为空

3.函数定义源文件 stack.c

#include "stack.h"
void StackInit(Stack* p)
{p->_a = (int*)malloc(sizeof(int) * 4);assert(p->_a);p->top = 0;p->capacity = 4;
}
void StackDestory(Stack* p)
{assert(p);free(p->_a);p->_a = NULL;p->top = 0;p->capacity = 4;
}
void StackPush(Stack* p, int n)
{assert(p);	if (p->top == p->capacity){int * new = (int*)realloc(p->_a, p->capacity*2*sizeof(int));assert(new);p->_a = new;p->capacity = p->capacity * 2;}p->_a[p->top] = n;p->top++; 
}
void StackPop(Stack* p)
{assert(p);//p->_a[p->top] = 0; 没必要assert(p->top>0);//栈空了再出栈直接报错中止p->top--;//p->capacity--;
}
int StackTop(Stack* p)
{assert(p);assert(p->top> 0);//栈为空不能调; return p->_a[p->top-1];
}
int StackSize(Stack* p)
{assert(p->top > 0);return p->top;
}
bool StackEmpty(Stack* p)
{assert(p);if (p->top == 0){return true;}return false;
}

4.函数调用测试源文件test.c

#include "stack.h"
int main()
{Stack st;StackInit(&st);//StackDestory(&st);StackPush(&st,5);StackPush(&st, 4);StackPush(&st, 3);StackPush(&st, 2);StackPush(&st, 1); //StackPop(&st);//StackPop(&st);//StackPop(&st);//StackPop(&st);//StackPop(&st);printf("%d\n",StackTop(&st));printf("%d\n",StackSize(&st));if (StackEmpty(&st)){printf("没东西");}else{printf("有东西");}while (!StackEmpty(&st)){printf("%2d", StackTop(&st));StackPop(&st);}
}