初步认识栈和队列

禁默

发布于 2025-12-19 14:26:02

1290

Hello，everyone，今天小编讲解栈和队列的知识！！！

1.栈

1.1栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。

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队列的概念及结构

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

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

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;
}

另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统讲解生产者消费者模型时可以就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。