当前位置：网站首页>[C language] Detailed explanation of stacks and queues (define, destroy, and data operations)

[C language] Detailed explanation of stacks and queues (define, destroy, and data operations)

2022-08-05 02:31:00 【Young classmate who is getting up early】

博客主页：要早起的杨同学的博客
欢迎关注点赞收藏️留言
本文所属专栏：【数据结构】
️坚持和努力从早起开始！
参考在线编程网站：牛客网力扣
作者水平有限,如果发现错误,敬请指正！感谢感谢！

First. 栈

一. 栈的概念

栈：是一种特殊的线性表,其Only allowed in the footer for insert and delete elements operation.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则.
压栈：栈的插入操作叫做进栈 / 压栈 / 入栈,入数据在栈顶.
出栈：栈的删除操作叫做出栈.出数据也在栈顶.

二. In the form of the out of the stack

The location of the stack for the insertion and deletion of the linear table do the limit,并没有对元素进出的时间进行限制,所以,在不是所有元素都进栈的情况下,事先进去的元素也可以出栈,只要保证是栈顶元素出栈就可以.
所以栈是：一种入栈顺序,A variety of the stack order.
比如：Now there are elements1、2、3依次进栈,What are the stack order？
第一种：1、2、3（1进、1出、2进、2出、3进、3出）
第二种：3、2、1（1、2、3进,3、2、1出）
第三种：2、1、3（1、2进,2、1出,3进、3出）
第四种：1、3、2（1进、1出,2、3进,3、2出）
第五种：2、3、1（1、2进,2出,3进,3出,1出）

三. 栈的存储结构

栈的顺序存储结构

The first element of an array of as bottom of stack,The other side as the top,同时定义一个变量 top The positions of the elements in the array to record the stack.

栈的链式存储结构

单链表As the bottom of the stack to the end of,As the top head,方便插入和删除（Head inserted into the stack,The stack first delete）,头指针和栈顶指针 top 合二为一.

四. 栈的实现（顺序栈）

顺序表的结构相比链表简单,不影响效率的情况下会优先使用顺序表.
This time we use the dynamic growth of array to realize,Because the stack will only at one end for insertion and deletion operation,Use an array or high efficiency,当然,也会存在一些问题,Is every time space is not enough,要重新开辟空间,May cause some waste memory.

首先新建一个工程（博主使用的是 VS2022 ）

Stack.h（栈的类型定义、接口函数声明、引用的头文件）
Stack.c（The realization of the stack interface function）
Test.c（主函数、Test the stack each interface function）

Stack.h 头文件代码如下：

#pragma once

#include<stdio.h> /*printf, perror*/
#include<assert.h> /*assert*/
#include<stdlib.h> /*realloc*/
#include<stdbool.h> /*bool*/

typedef int STDataType;  //类型重命名,The stack element types given asint

typedef struct Stack
{
    
	STDataType* a;  //指向动态开辟的数组
	int top;        //记录栈顶位置
	int capacity;   //栈的容量大小
}Stack;

//初始化栈
void StackInit(Stack* ps);
//销毁栈
void StackDestroy(Stack* ps);
//入栈
void StackPush(Stack* ps, STDataType x);
//出栈
void StackPop(Stack* ps);
//检测栈是否为空,如果为空返回true,否则返回NULL
bool StackEmpty(Stack* ps);
//获取栈中有效元素个数
int StackSize(Stack* ps);
//获取栈顶元素
STDataType StackTop(Stack* ps);

这里重点讲解 Stack.c 中各个接口函数的实现.

4.1 栈的定义

下面是定长的静态栈的结构,实际中一般不实用,所以我们主要实现下面的支持动态增长的栈

typedef int STDataType;  //类型重命名,The stack element types given asint
#define N 20

struct Stack
{
    
	STDataType a[N];  //定长数组
	int top;          //记录栈顶位置
}SqStack;

支持动态增长的栈

Assuming the capacity of the capacity 为 5,Define an empty stack top = -1,当栈存在一个元素时 top = 0

typedef int STDataType;  //类型重命名,The stack element types given asint

typedef struct Stack
{
    
	STDataType* a;  //指向动态开辟的数组
	int top;        //记录栈顶位置
	int capacity;   //栈的容量大小
}Stack;

4.2 栈的初始化

//初始化栈
void StackInit(Stack* ps)
{
    
	assert(ps);

	ps->a = NULL;
	ps->top = -1;
	ps->capacity = 0;
}

4.3 栈的销毁

//销毁栈
void StackDestroy(Stack* ps)
{
    
	assert(ps);

	if (ps->a)
	{
    
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = -1;
	ps->capacity = 0;
}

4.4 入栈

//入栈
void StackPush(Stack* ps, STDataType x)
{
    
	assert(ps);

	if (ps->top == ps->capacity - 1)  //Check whether the stack space is full of
	{
    
		//If the stack the original capacity of0,New capacity is set to4,Otherwise set as the original capacity2倍
		int newcapacity = (ps->capacity == 0) ? 4 : (ps->capacity) * 2;
		//New capacity expansion to
		STDataType* newS = realloc(ps->a, newcapacity * sizeof(STDataType));
		if (newS == NULL)
		{
    
			perror("realloc");
			exit(-1);
		}
		ps->a = newS;
		//更新容量
		ps->capacity = newcapacity;
	}
	ps->top++;           //栈顶指针加一
	ps->a[ps->top] = x;  //Will new elements into the stack space
}

4.5 出栈

//出栈
void StackPop(Stack* ps)
{
    
	assert(ps);
	assert(ps->top != -1);  //栈不能为空

	ps->top--;  //栈顶指针减一
}

4.6 检测栈是否为空

//检测栈是否为空,如果为空返回true,否则返回NULL
bool StackEmpty(Stack* ps)
{
    
	assert(ps);
	
	return ps->top == -1;
}

4.7 获取栈中有效元素个数

//获取栈中有效元素个数
int StackSize(Stack* ps)
{
    
	assert(ps);

	return ps->top + 1;
}

4.8 获取栈顶元素

//获取栈顶元素
STDataType StackTop(Stack* ps)
{
    
	assert(ps);
    assert(!StackEmpty(ps));  //栈不能为空

	return ps->a[ps->top];
}

五. Test the functionality of the stack

栈的实现,Not like a sequence table,To achieve a print function to traverse the stack and output,So it is not in conformity with the characteristics of stack（只能在栈顶插入删除,后进先出）,So we like to implement a stack：Obtain and print the stack elements,再删除栈顶元素,Continue to get new stack elements.

void TestStack()  //测试函数
{
    
	Stack s;
    //初始化栈
	StackInit(&s);
	//入栈
	StackPush(&s, 1);
	StackPush(&s, 2);
	StackPush(&s, 3);
	StackPush(&s, 4);
	StackPush(&s, 5);
	//出栈
	while (!StackEmpty(&s))
	{
    
		printf("%d ", StackTop(&s));  //获取栈顶元素
		StackPop(&s);
	}
	printf("\n");
	//销毁栈
	StackDestroy(&s);
}

运行结果

Second. 队列

一. 队列的概念

队列：只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出
FIFO(First In First Out) 的特点.
入队列：进行插入操作的一端称为队尾 .
出队列：进行删除操作的一端称为队头.
Team a team form：一种入队顺序,只有一种出队顺序.
队列的应用：Such as lining up to buy things in life,First in line to buy,Usually we use WeChat chat,Use the keyboard for a variety of digital input,To the output of the chat box,Is the application of the queue.

二. 队列的结构

队列的顺序结构

入队,不需要移动任何元素,时间复杂度为O(1)

出队,All elements need to move forward,时间复杂度为O(N)

队列的链式结构

首先我们定义两个指针,Team head pointer to the first node,队尾指针指向尾节点

入队（尾插）,时间复杂度为O(1)

出队（头删）,时间复杂度为O(1)

三. 队列的实现（链式结构）

首先新建一个工程（博主使用的是 VS2022）

Queue.h（队列的类型定义、接口函数声明、引用的头文件）
Queue.c（The realization of the queue interface function）
Test.c（主函数、Test queue each interface functions）

Queue.h 头文件代码如下：

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int bool;
#define false 0
#define true 1

typedef int QDatatype;

typedef struct QNode
{
    
	struct QNode* next;
	QDatatype val;
}QNode;


/* We realize the headless chain table head plug delete interface,因为需要改变头指针的指向 There are such methods： 1、传二级指针 2、改变返回值,返回新的头 3、Adds a sentry to list a head node 4、Structure wrapped up */

typedef struct Queue//队列的链式结构
{
    
	QNode* front;//队头指针
	QNode* tail;//队尾指针
}Queue;

//初始化
void queue_init(Queue* qst);
//销毁
void queue_destory(Queue* qst);
//入列
void queue_push(Queue* qst,QDatatype x);
//出列
void queue_pop(Queue* qst);
//队头数据
QDatatype queue_front(Queue* qst);
//队尾数据
QDatatype queue_back(Queue* qst);
//判空
bool queue_empty(Queue* qst);
//大小
int queue_size(Queue* qst);

这里重点讲解 Queue.c 中各个接口函数的实现.

3.1 队列的定义

typedef int QDatatype;

typedef struct QNode//队列节点结构
{
    
	struct QNode* next;//节点指针
	QDatatype val;//节点数据
}QNode;

typedef struct Queue//队列的链式结构
{
    
	QNode* front;//队头指针
	QNode* tail;//队尾指针
}Queue;

3.2 队列的初始化

//初始化
void queue_init(Queue* qst)
{
    
	assert(qst);
	qst->front = qst->tail = NULL;
}

3.3 队列的销毁

//销毁
void queue_destory(Queue* qst)
{
    
	assert(qst);
	QNode* cur = qst->front;
	while (cur)
	{
    
		QNode* Next = cur->next;
		free(cur);
		cur = Next;
	}
	qst->front = qst->tail = NULL;

}

3.4 入队（尾插）

To be divided into two cases to discuss,The queue is empty and queue is empty

//入列
void queue_push(Queue* qst, QDatatype x)
{
    
	assert(qst);
	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	newNode->next = NULL;
	newNode->val = x;
    
	if (queue_empty(qst))
	{
    
		qst->front = qst->tail = newNode;
	}
	else
	{
    
		qst->tail->next = newNode;
		qst->tail = newNode;
	}
}

3.5 出队（头删）

The queue can't be empty oh,Remember at the beginning of the check

//出队
void queue_pop(Queue* qst)
{
    
	assert(qst);
	assert(!queue_empty(qst));
    //If only one node,要注意给tail置空
    //防止出现野指针
	if (qst->front->next == NULL)
	{
    
		free(qst->front);
		qst->front = qst->tail = NULL;
	}
	else
	{
    
		QNode* del = qst->front;
		qst->front = qst->front->next;

		free(del);
		del = NULL;
	}
	
}

3.6 获取队列元素个数

//获取队列元素个数
//If the interface function called frequently,可以在QueuePtr中加一个size记录数据个数
int queue_size(Queue* qst)
{
    
	assert(qst);
	QNode* cur = qst->front;
	int count = 0;
	while (cur)
	{
    
		cur = cur->next;
		++count;
	}
	return count;
}

3.7 获取队头元素

The queue is empty is to get the element oh,记得检查一下

//获取队头元素
QDatatype queue_front(Queue* qst)
{
    
	assert(qst);
	assert(!queue_empty(qst));
	return qst->front->val;
}

3.8 获取队尾元素

The queue is empty is to get the element oh,记得检查一下

//获取队尾元素
QDatatype queue_back(Queue* qst)
{
    
	assert(qst);
	assert(!queue_empty(qst));
	return qst->tail->val;
}

3.9 检查队列是否为空

//检查队列是否为空,若为空返回true,否则返回false
bool queue_empty(Queue* qst)
{
    
	assert(qst);
	return qst->front == NULL && qst->tail == NULL;
}

四. The function of the test queue

void Test(Queue* qst)
{
    
	queue_init(qst);
	queue_push(qst, 1);
	queue_push(qst, 2);
	queue_push(qst, 3);
	queue_push(qst, 4);
	queue_push(qst, 6);

	printf("%d\n", queue_front(qst));
	printf("%d\n", queue_back(qst));
	printf("%d\n", queue_size(qst));

	while (!queue_empty(qst))
	{
    
		printf("%d ", queue_front(qst));
		queue_pop(qst);
	}

	queue_destory(qst);
}