【数据结构】栈和队列

P_M_P

修改于 2024-01-20 08:13:58

1460

修改于 2024-01-20 08:13:58

文章被收录于专栏：P_M_P学习笔记

栈

栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除操作。在进行数据插入和删除的一端称为栈顶，另一端称为栈低。栈中的元素都遵循后进先出的原则（LIFO，Last In First Out）。 压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。 出栈：栈的删除操作叫做出栈。出数据也在栈顶。

栈的实现

栈一般可以用数组或者链表来实现，相对而言数组的结构更优一些。因为数组在尾插上更加方便，而栈也只是在栈顶一端进行操作。当然也可以使用链表进行实现，使用时不需要扩容。

栈的基本操作

1.入栈

由于使用的数组栈，元素入栈时需要判断栈内是否还有足够的空间，如果空间不足，则需要扩容。

void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc error!");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;

}

2.出栈

出栈只能从栈顶出栈，同时出栈时需要注意栈是否为空

//删除栈顶元素
void STPop(ST* pst)
{
	assert(pst);
	//不为空
	assert(pst->top > 0);
	pst->top--;
}

3.获取栈顶元素

4.栈是否为空

5.栈的大小

6.栈的销毁

stack.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//栈只能先进后出
//每个元素最后进出的相对顺序不唯一，可以边进边出

typedef int STDataType;

typedef struct Stack
{
	int* a;  //存储栈内元素的数组
	int top;		// 标识栈顶位置的,代表栈顶元素的下一个位置（也可以代表是栈顶元素，但栈为空时top==-1）
	int capacity;
}ST;

void STInit(ST* pst);
void STDestroy(ST* pst);

// 栈顶插入删除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
STDataType STTop(ST* pst);

bool STEmpty(ST* pst);
int STSize(ST* pst);

stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"stack.h"
//初始化
void STInit(ST* pst)
{
	assert(pst);
	pst->a = NULL;
	pst->capacity = 0;
	//此时top表示指向栈顶元素的下一个位置
	pst->top = 0;
	//pst->top=-1;//表示指向栈顶元素

}
void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}
// 栈顶插入删除
void STPush(ST* pst, STDataType x)
{
	assert(pst);
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc error!");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
	pst->a[pst->top] = x;
	pst->top++;

}
//删除栈顶元素
void STPop(ST* pst)
{
	assert(pst);
	//不为空
	assert(pst->top > 0);
	pst->top--;
}
//返回栈顶元素
STDataType 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)
{
	return pst->top;
}

队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出 FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

队列的基本操作

1.入队列

2.出队列

3.判断队列是否为空

4.获取队头元素

5.获取队尾元素

6.销毁队列

队列的实现

Queue.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
// 链式结构：表示队列 
typedef int QDataType;
typedef struct QListNode
{
	struct QListNode* next;
	QDataType data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* head;//队头
	QNode* 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 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
	q->head = q->tail = NULL;
	q->size = 0;
}
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc!");
		return;
	}
	newnode->data = data;
	newnode->next = NULL;
	if (q->tail == NULL)
	{
		q->head = q->tail = newnode;
	}
	else
	{
		q->tail->next = newnode;
		q->tail = q->tail->next;
	}
	q->size++;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head);
	QNode* del = q->head;
	q->head = q->head->next;
	free(del);
	del = NULL;
	if (q->head == NULL)
		q->tail = NULL;
	q->size--;

}
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head);
	return q->head->data;
}
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->tail);
	return q->tail->data;
}
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
	return q->size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q)
{
	assert(q);
	return q->head == NULL;
}
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->head;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
		del = NULL;
	}
	q->head = q->tail = NULL;
	q->size = 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-20，如有侵权请联系 cloudcommunity@tencent.com 删除

数组