栈与队列增删查改代码实现
1.栈的增删查改基本代码
基本文件:
1.头文件:Stack.h
2.源文件:Stack.c
3.源文件:Test_Stack.c
代码内容
//Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//静态栈---不实用
/*struct Stack
{
int a[N];
int top;//栈顶的位置
};*/
typedef int STDataType;
//动态栈
typedef struct Stack
{
STDataType* a;
int top;//栈顶的位置
int capacity;//容量
}ST;
void StackInit(ST* ps);//初始化栈
void StackDestory(ST* ps);//销毁栈
void StackPush(ST* ps, STDataType x);//插入栈顶元素
void StackPop(ST* ps);//删除栈顶元素
bool StackEmpty(ST* ps);//判断空栈
STDataType StackTop(ST* ps);//查找栈顶元素
int StackSize(ST* ps);//求栈的元素个数
//Stack.c
#include"Stack.h"
void StackInit(ST* ps)//初始化栈
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
//top初始化为0或-1 那么下面插入和删除方式格式有所不同，但思路一样
}
void StackDestory(ST* ps)//销毁栈
{
assert(ps);
free(ps);
ps->top = ps->capacity = 0;
ps->a = NULL;
}
void StackPush(ST* ps, STDataType x)//插入栈顶元素
{
assert(ps);
//栈满 要扩容
if (ps->top == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
ps->a = realloc(ps->a, newCapacity * sizeof(STDataType));//在原空间后在链接空间
if (ps->a == NULL)
{
printf("realloc fail\n");
exit(-1);
}
ps->capacity = newCapacity;
}
ps->a[ps->top] = x;
ps->top++;
}
void StackPop(ST* ps)//删除栈顶元素
{
assert(ps);
assert(ps->top > 0);
--ps->top;
}
bool StackEmpty(ST* ps)//判断空栈
{
assert(ps);
return ps->top == 0;//满足top=0返回true，不满足返回false
}
STDataType StackTop(ST* ps)//查找栈顶元素
{
assert(ps);
return ps->a[ps->top-1];
}
int StackSize(ST* ps)//求栈的元素个数
{
assert(ps);
return ps->top;
}
#include"Stack.h"
int main()
{
ST st;
StackInit(&st);
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
while (!StackEmpty(&st))
{
printf("%d ", StackTop(&st));
StackPop(&st);
}
printf("\n");
StackDestory(&st);
return 0;
}
2.队列的增删查改基本代码
基本文件:
头文件:.Queue.h
源代码:Queue.c
注:这里就不写Test文件了，没有什么写头
代码内容
//Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDataType;
typedef struct QueueNode//记录结点的结构体
{
QDataType data;
struct QueueNode* next;
}QNode;
typedef struct Queue//找头尾的结构体
{
//为了方便队尾的插入 创建两个结点指针
QNode* head;
QNode* tail;
}Qu;
void QueueInit(Qu* pq);//初始化队列
void QueueDestory(Qu* pq);//销毁队列
void QueuePush(Qu* pq,QDataType x);//队尾入
void QueuePop(Qu* pq);//队首出
bool QueueEmpty(Qu* pq);//判断空队列
size_t QueueSize(Qu* pq);//求队列长度
QDataType QueueFront(Qu* pq);//求队首
QDataType QueueBack(Qu* pq);//求队尾
//Queue.c
#include"Queue.h"
void QueueInit(Qu* pq)//初始化队列
{
assert(pq);
pq->head = pq->tail = NULL;
}
void QueueDestory(Qu* pq)//销毁队列
{
assert(pq);
QNode* cur = pq->head;
while (cur)
{
//遍历cur 一个一个的去掉cur的内容
QNode* next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
}
void QueuePush(Qu* pq, QDataType x)//队尾入
{
assert(pq);
QNode* newnode = (QNode*)malloc(sizeof(QNode));
assert(newnode);
newnode->data = x;
newnode->next = NULL;
if (pq->tail == NULL)
{
assert(pq->head == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
}
void QueuePop(Qu* pq)//队首出
{
assert(pq);
assert(pq->head && pq->tail);
if (pq->head->next == NULL)
{
free(pq);
pq->head = pq->tail = NULL;
}
else
{
QNode* next = pq->head->next;
free(pq->head);
pq->head = next;
}
}
bool QueueEmpty(Qu* pq)//判断空队列
{
assert(pq);
return pq->head == NULL;//或者return pq->tail==NULL 判断头、尾都可以
}
size_t QueueSize(Qu* pq)//求队列长度
{
assert(pq);
QNode* cur = pq->head;
size_t size = 0;
while (cur)
{
size++;
cur = cur->next;
}
return size;
}
QDataType QueueFront(Qu* pq)//求队首
{
assert(pq);
assert(pq->head);
return pq->head->data;
}
QDataType QueueBack(Qu* pq)//求队尾
{
assert(pq);
assert(pq->tail);
return pq->tail->data;
}
