【初阶数据结构】栈与队列

一、栈 ( Stack )

1.1 栈的概念

  1. 什么是栈?

    栈是一种特殊的线性表结构，其特殊性体现在数据操作的位置限制：所有数据的插入（称为压栈）和删除（称为出栈）都只能在线性表的同一端进行，这一端被称为栈顶，而另一端不允许操作的称为栈底。

    核心特性是先进后出（Last In First Out, LIFO）

    • 如同叠放餐盘，最后放置的盘子总是最先被取用
    • 类似文档的撤销功能，最后执行的操作最先被撤销
    • 当删除数据时，最后进入栈的元素会最先被移除

  2. 压栈与出栈

    • 压栈（Push）

      • 仅在栈顶进行
      • 新元素被放置在栈顶上方 → 栈顶指针自动上移指向新位置

      出栈（Pop）

      • 同样只能在栈顶完成
      • 取出当前栈顶元素 → 栈顶指针自动下移指向次顶层

1.2 栈的结构

从结构上可以更清楚地观察栈在插入数据与删除数据是如何表现的

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

1.3 栈的接口实现 ( 完整代码 )

Stack.h
#pragma once

#include 
#include 
#include 
#include 

// 动态栈
typedef int STDataType;
 
typedef struct Stack {
	STDataType* a;
	int top;
	int capacity;

}ST;

// 初始化
void STInit(ST* ps);

// 入栈
void STPush(ST* ps, STDataType x);

// 出栈
void STPop(ST* ps);

// 是否为空
bool STEmpty(ST* ps);

// 判断数据个数，如果等于capacity就扩容
int STSize(ST* ps);

//销毁
void STDestroy(ST* ps);

// 访问栈顶元素
STDataType STTop(ST* ps);
  • 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
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
Stack.c
#pragma once

#include "Stack.h"


// 初始化
void STInit(ST* ps) {
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL) {
		perror("malloc fail");
		return;
	}
	ps->capacity = 4;
	// 如何定义top?
	// 1.top表示的是栈顶元素的下一个位置
	ps->top = 0;

	// 2. top表示的是栈顶元素的位置
	//ps->top = -1; 
}

// 入栈
void STPush(ST* ps, STDataType x) {
	assert(ps);

	if (ps->top == ps->capacity) {
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity * 2); //扩到当前的二倍
		if (tmp == NULL) {
			perror("realloc fail");
			return;
		}
		ps->a = tmp;
		ps->capacity *= 2;

	}
	ps->a[ps->top] = x;
	ps->top++;

}

// 出栈
void STPop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps)); // 不等于空就可以继续删，空了就不能删

	ps->top--;

}

// 是否为空
bool STEmpty(ST* ps) {
	assert(ps);

	return ps->top == 0;
}

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

	return ps->top;
}

//销毁
void STDestroy(ST* ps) {
	assert(ps);

	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	// 这一个top如何写，根据你初始化的top
	ps->top = 0;
}

// 访问栈顶元素
STDataType STTop(ST* ps) {
	assert(ps);
	assert(!STEmpty(ps));
	return ps->a[ps->top - 1];
}
  • 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
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82

二、队列 ( Queue )

2.1 队列的概念

  1. 什么是队列?

    队列也是一种特殊的线性表结构，其操作限制表现为：插入数据（称为入队）只能在线性表的一端（称为队尾）进行，删除数据（称为出队）只能在另一端（称为队头）完成。

    核心特性是先进先出（First In First Out, FIFO）

    • 类比日常生活中的排队场景：先到服务窗口的人优先获得服务
    • 类似打印机任务队列，先提交的打印任务最先被执行
    • 当删除数据时，最早进入队列的元素会最先被移除

  2. 入队与出队

    • 入队（Enqueue）

      • 仅在队尾进行
      • 新元素追加到队尾后方 → 队尾指针自动后移指向新位置

      出队（Dequeue）

      • 仅在队头完成
      • 移除当前队头元素 → 队头指针自动后移指向次首元素

2.2 队列的结构

在这里插入图片描述

2.3 队列的接口实现 ( 完整代码 )

架构

在这里插入图片描述

Queue.h
#define _CRT_SECURE_NO_WARNINGS  1
#pragma once


#include 
#include 
#include 
#include 

// 定义结构体 ( 我们的队列以单链表方式实现 )

typedef int QDataType;


// 单个节点的数据存储（data）和 节点间的链接关系（next）
typedef struct QueueNode {
	struct QueueNode* next;
	QDataType data;

}QNode;

// 队列整体
typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 销毁
void QueueDestroy(Queue* pq);
// 插入
void QueuePush(Queue* pq, QDataType x);
// 删除
void QueuePop(Queue* pq);
// 有效数据个数
int QueueSize(Queue* pq);
// 判断是否为空
bool QueueEmpty(Queue* pq);
// 取队头数据
QDataType QueueFront(Queue* pq);
// 取队尾数据
QDataType QueueBack(Queue* pq);
  • 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
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
Queue.c
#define _CRT_SECURE_NO_WARNINGS  1

#include "Queue.h"



void QueueInit(Queue* pq) {
	assert(pq);

	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueueDestroy(Queue* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Queue* pq, QDataType x) {
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		return;
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->head == NULL) {
		assert(pq->tail == NULL);

		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = pq->tail->next;
	}
	pq->size++;
}

void QueuePop(Queue* pq) {
	assert(pq);
	assert(pq->head != NULL);

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}

int QueueSize(Queue* pq) {
	assert(pq);

	return pq->size;

}

bool QueueEmpty(Queue* pq) {
	assert(pq);

	return pq->size == 0;
}

QDataType QueueFront(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;


}

QDataType QueueBack(Queue* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
  • 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
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
注：本文转载自blog.csdn.net的逐花归海.的文章"https://blog.csdn.net/2503_90450246/article/details/145556446"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！