1.栈
1.1栈的概念及结构


1.2栈的实现
1.2.1 头文件的建立
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int datatype;
//这里选用动态数组实现栈,单链表也可以
typedef struct stack {
datatype* a;
int top;//栈顶
int capacity;
}ST;
//栈的初始化和销毁
void STInit(ST* pst);
void STDestory(ST* pst);
//入栈和出栈
void STPush(ST* pst,datatype x);
void STPop(ST* pst);
//获取栈顶数据
datatype STTop(ST* pst);
//判空
bool STEmpty(ST* pst);
//栈的数据个数
int STSize(ST* pst);
1.2.2 函数的实现
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
//栈的初始化和销毁
void STInit(ST* pst){
assert(pst);
pst->a = NULL;
//top指向栈顶数据的下一个位置,可以理解为下标
pst->top = 0;
//top指向指向栈顶数据,可以理解成栈的数据个数
//pst->top=-1;
pst->capacity = 0;
}
void STDestory(ST* pst) {
assert(pst);
free(pst->a);
pst->a = NULL;
pst->top = pst->capacity = 0;
}
//容量检查
void Checkcapacity(ST* pst) {
assert(pst);
if (pst->top == pst->capacity) {
int newcapacity = pst->capacity==0?4:pst->capacity * 2;
datatype* temp = (datatype*)realloc(pst->a, newcapacity * sizeof(datatype));
if (temp == NULL) {
perror("relloc fail");
return;
}
pst->a = temp;
pst->capacity = newcapacity;
}
}
//入栈和出栈
void STPush(ST* pst, datatype x) {
assert(pst);
Checkcapacity(pst);
pst->a[pst->top] = x;
pst->top++;
}
void STPop(ST* pst) {
assert(pst);
assert(pst->top>0);
pst->top--;
}
//获取栈顶数据
datatype STTop(ST* pst) {
assert(pst);
assert(pst->top > 0);
return pst->a[pst->top-1];
}
//判空
bool STEmpty(ST* pst) {
assert(pst);
return pst->top == 0;//表达式判断
}
//栈的数据个数
int STSize(ST* pst) {
assert(pst);
return pst->top;
}
1.2.3 测试文件
#define _CRT_SECURE_NO_WARNINGS
#include "Stack.h"
int main() {
ST s;
STInit(&s);
STPush(&s, 1);
STPush(&s, 2);
STPush(&s, 3);
STPush(&s, 4);
STPush(&s, 5);
printf("%d\n", STTop(&s));
STPop(&s);
//STPop(&s);
printf("%d\n", STTop(&s));
while (!STEmpty(&s)) {
printf("%d ", STTop(&s));
STPop(&s);
}
STDestory(&s);
return 0;
}
2.队列
2.1队列的概念及结构

2.2队列的实现


2.2.1 头文件的建立
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
typedef int Qdatatype;
//链式结构表示队列
typedef struct QueueNode {
struct QueueNode* next;
Qdatatype x;
}Node;
//定义结构体表示队头队尾,后续传参改变队列也很方便,不用传二级指针。
typedef struct Queue {
Node* head;
Node* tail;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, Qdatatype data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
Qdatatype QueueFront(Queue* q);
// 获取队列队尾元素
Qdatatype QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
2.2.2 函数的实现
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
void QueueInit(Queue* q) {
assert(q);
q->head = NULL;
q->tail = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, Qdatatype data) {
assert(q);
Node* newnode = (Node*)malloc(sizeof(Node));
if (newnode == NULL) {
perror("malloc fail");
return;
}
newnode->next = NULL;
newnode->x = data;
if (q->tail ==NULL) {
q->head = q->tail = newnode;
}
else {
q->tail->next = newnode;
q->tail = newnode;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q) {
assert(q);
assert(q->size != 0);
//一个节点
if (q->head->next == NULL) {
free(q->head);
q->head = q->tail = NULL;
}
else {
Node* next = q->head->next;
free(q->head);
q->head = next;
}
q->size--;
}
// 获取队列头部元素
Qdatatype QueueFront(Queue* q) {
assert(q);
assert(q->head);
return q->head->x;
}
// 获取队列队尾元素
Qdatatype QueueBack(Queue* q) {
assert(q);
assert(q->tail);
return q->tail->x;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q) {
assert(q);
return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
bool QueueEmpty(Queue* q) {
assert(q);
return q->size == 0;//为0,返回1,不为0,返回0;
}
// 销毁队列
void QueueDestroy(Queue* q) {
assert(q);
Node* qcur = q->head;
while (qcur) {
Node* next = qcur->next;
free(qcur);
qcur = next;
}
q->head = q->tail = NULL;
q->size = 0;
}
2.2.3 测试文件
#define _CRT_SECURE_NO_WARNINGS
#include "Queue.h"
int main() {
Queue p;
QueueInit(&p);
QueuePush(&p,1);
QueuePush(&p,2);
printf("%d\n", QueueFront(&p));
QueuePush(&p, 3);
QueuePush(&p, 4);
printf("%d\n",QueueBack(&p));
QueuePop(&p);
printf("%d\n", QueueFront(&p));
while (!QueueEmpty(&p))
{
printf("%d ", QueueFront(&p));
QueuePop(&p);
}
printf("\n");
return 0;
}
