栈的和队列的实现

一、栈

1.概念

一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作，进行数据插入和删除操作的一端称为栈顶，另一端称为栈底，栈中的数据元素遵循后进先出的原则。
注意从栈顶入，栈顶出

二 、栈的实现(顺序表)

1.函数的定义和结构体的创建——stack.h

#pragma once
#include
#include
#include
#include
typedef int datatype;
typedef struct stack
{
	datatype* a;
	int top;
	int capacity;
}ST;
void stackinit(ST* p);
void stackpush(ST* p, datatype x);
int stacktop(ST* p);
void stackpop(ST* p);
int stacksize(ST* p);
bool stackempty(ST* p);
void stackdestroy(ST* p);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2.函数的调用——test.c

#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);//移除栈顶元素
	}
	stackdestroy(&st);//内存销毁
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.栈的接口

1.初始化

void stackinit(ST* p)//栈的初始化
{
	assert(p);
	p->a = NULL;
	p->top = 0;
	p->capacity = 0;
}
1
2
3
4
5
6
7

2.入栈

void stackpush(ST* p, datatype x)//入栈
{
	assert(p);
	if (p->top == p->capacity)//扩容
	{
		int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
		datatype* tmp = (datatype*)realloc(p->a, sizeof(datatype) * newcapacity);
		if (tmp != NULL)
		{
			p->a = tmp;
			p->capacity = newcapacity;//扩容成原来的2倍
		}
	}
	p->a[p->top] = x;
	p->top++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.移除栈顶元素

void stackpop(ST* p)//移除栈顶元素
{
	assert(p);
	assert(p->top > 0);
	p->top--;
}
1
2
3
4
5
6

4.出栈

int  stacktop(ST* p)//出栈
{
	assert(p);
	assert(p->top > 0);
	return p->a[p->top - 1];//top从0开始，每次入栈top都向后移，所以top-1是实际储存的元素
}
1
2
3
4
5
6

5.判断为空

bool  stackempty(ST* p)//是否为空
{
	return p->top == 0;//当栈中没有数据时，则为空，为真， 否则为假。
}
1
2
3
4

6.栈中元素个数

int stacksize(ST* p)//栈中元素个数
{
	assert(p);
	return p->top;//虽然top是指向下一个，但是top从0开始，top正好是元素个数
}
1
2
3
4
5

7.内存销毁

void stackdestroy(ST* p)//内存销毁
{
	assert(p);
	free(p->a);//销毁动态开辟数组
	p->a = NULL;
	p->top = 0;
	p->capacity = 0;
}
1
2
3
4
5
6
7
8

三、队列

1.概念

只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出的原则。
入队列：进行插入操作的一段称为队尾
出队列：进行删除操作的一端称为对头
注意 ：对尾入，对头出

四、队列的实现(链表)

1.函数的定义和结构体的创建——queue.h

#pragma once
#include
#include
#include
#include
typedef int datatype;
typedef struct queuenode
{
	datatype data;
	struct queuenode* next;
}queuenode;
typedef struct queue
{
	queuenode * head;
	queuenode * tail;
}queue;
void queueinit(queue*p);
void queuedestroy(queue* p);
void queuepush(queue* p,datatype x);
void queuepop(queue* p);
datatype queuefront(queue* p);
datatype queueback(queue* p);
int queuesize(queue* p);
bool queueempty(queue* p);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

2.函数的调用——test.c

#include"queue.h"
int main()
{
	queue p;
	queueinit(&p);
	queuepush(&p, 1);
	queuepush(&p, 2);
	queuepush(&p, 3);
	queuepush(&p, 4);
	while (!queueempty(&p))//判断为空
	{
		datatype front = queuefront(&p);
		printf("%d ", front);
		queuepop(&p);
	}
	queuedestroy(&p);//内存销毁
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3.取一级指针的原因

正常来说，如果将head与tail放在queuenode内部，应该取二级指针，
但是由于此时定义的是结构体为queue 的变量，改变的是该变量的内部。
所以只取一级指针就可以。

4.队列的接口的实现

1.初始化

void queueinit(queue* p)//初始化队列
{
	assert(p);
	p->head = NULL;
	p->tail = NULL;
}
1
2
3
4
5
6

2.入队列

void queuepush(queue* p,datatype x)//入队列 (队尾入)
{
	assert(p);
	queuenode* newnode = (queuenode*)malloc(sizeof(queuenode));
	newnode->data = x;
	newnode->next = NULL;
	if (p->tail == NULL)
	{
		p->tail = newnode;
		p->head = newnode;
	}
	else
	{
		p->tail->next = newnode;
		p->tail = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.删除数据

void queuepop(queue* p)//删除数据
{
	assert(p);
	assert(!queueempty(p));//断言队列是否为空
	queuenode* next = p->head->next;
	free(p->head);
	p->head = next;
	if (p->head == NULL)//当删除只剩下最后一个节点时 head与tail都指向，free(head) ,tail就变成了野指针
	{
		p->tail = NULL;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

4.取对头数据

datatype queuefront(queue* p)//取队头数据
{
	assert(p->head);
	assert(!queueempty(p));
	return p->head->data;
}
1
2
3
4
5
6

5.取队尾数据

datatype queueback(queue* p)//取队尾数据
{
	assert(p->head);
	assert(!queueempty(p));
	return p->tail->data;
}
1
2
3
4
5
6

6.取队的元素个数

int queuesize(queue* p)//队的数量
{
	assert(p);
	int sum = 0;
	queuenode* cur = p->head;
	while (cur != NULL)
	{
		sum++;
		cur= cur->next;
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12

7.判断为空

bool queueempty(queue* p)//判断队列是否为空
{
	assert(p);
	return p->head == NULL;
}
1
2
3
4
5

8.内存销毁

void queuedestroy(queue* p)//内存销毁
{
	assert(p);
	queuenode* cur = p->head;
	while (cur != NULL)
	{
		queuenode* next = cur->next;
		free(cur);
		cur = next;
	}
	p->head = NULL;
	p->tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13