数据结构----栈和队列认识

发布于：2025-08-11 ⋅ 阅读:(21) ⋅ 点赞:(0)

目录

栈（后进先出）

栈的实现

头文件

初始化

入栈

注意：

bool 判空

出栈----栈顶

注意

出栈顶元素，元素不会删除

注意：

获取栈中有效个数

销毁栈

源文件操作

用栈实现递归*

队列（先进先出）

队列实现

头文件（基本操作）：

结构

初始化

判空

入队----队尾

出队----队头

优势：

取队头队尾数据

优势：

销毁

栈（后进先出）

是⼀种特殊的线性表，其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作
的⼀端称为栈顶，另⼀端称为栈底。
压栈：栈的插⼊操作叫做进栈/压栈/⼊栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。

底层结构是由数组实现的，相对来说数组在尾结点插入快

逻辑结构和物理结构都是线性的

栈的实现

头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定义栈的结构
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;
	int top;//有效数据个数
	int capacity;//容量
}ST;

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

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

//入栈----栈顶
void StackPush(ST* ps, STDataType x);

//出栈----栈顶
void StackPop(ST* ps);

//出栈顶数据
STDataType StackTop(ST* ps);
\ No newline at end of file
STDataType StackTop(ST* ps);

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

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

初始化

//初始化
void StackInit(ST* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

使用前先调用StackInit初始化栈，然后才能进行入栈等其他操作，否则可能会导致未定义行为。

入栈

//入栈----栈顶
void StackPush(ST* ps, STDataType x)
{
	if (ps->top == ps->capacity)
	{
		//增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc");
			exit(1);
		}//空间申请成功
		ps->arr = tmp;
		ps->capacity = newCapacity;
    }
	ps->arr[ps->top++] = x;
}
  1. 首先检查栈是否已满（ps->top == ps->capacity）
  2. 如果栈满，则进行扩容操作：
    • 初始容量为 0 时，扩容到 4 个元素
    • 否则，按照 2 倍容量进行扩容
    • 使用realloc重新分配内存空间
    • 处理内存分配失败的情况（打印错误并退出程序）
  3. 将新元素x放入栈顶位置（ps->arr[ps->top]）
  4. 栈顶指针top自增，指向新的栈顶位置

注意：

  • ps指针不为空,一般断言一下。
  • 栈结构ST已经正确初始化
  • STDataType已经定义（通常是某种基本数据类型）

bool 判空

//栈是否为空
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

为空则返回true,非空则是false

出栈----栈顶

//出栈----栈顶
void StackPop(ST* ps)
{
	assert(!STEmpty(ps));
	--ps->top;
}
  • 效率高，时间复杂度为 O (1)
  • 实现简洁，通过移动栈顶指针而非真正释放内存来 "删除" 元素

注意

  • 该函数依赖STEmpty函数来判断栈是否为空，需要确保STEmpty已正确实现
  • 出栈操作只是逻辑上移除元素（移动栈顶指针），并未真正释放内存，这是栈实现的常见做法
  • 调用前应确保栈不为空，否则assert会触发程序中断

出栈顶元素，元素不会删除


//出栈顶数据,元素不会删除
STDataType StackTop(ST* ps)
{
	assert(!STEmpty(ps));
	return ps->arr[ps->top - 1];

}

注意：

  • 栈顶指针top指向的是下一个可以插入元素的位置，所以当前栈顶元素的索引是top - 1
  • 仅仅返回元素值，不修改top指针，因此元素不会被 "删除"
  • 依赖STEmpty函数判断栈是否为空，需要确保该函数已正确实现

获取栈中有效个数

//获取栈中有效元素个数
int StackSize(ST* ps)
{
	return ps->top;
}
  1. 直接返回栈顶指针top的值作为栈中有效元素的个数
  2. 这是因为栈的实现中top指针恰好表示了下一个可以插入元素的位置，同时也等于当前栈中元素的数量
  3. 时间复杂度为 O (1)，效率极高

销毁栈

void StackDestroy(ST* ps)
{
    assert(ps);
    free(ps->arr);  // 释放底层数组内存
    ps->arr = NULL; // 避免野指针
    ps->top = ps->capacity = 0; // 重置状态
}

源文件操作

#include"Stack.h"
void test1()
{
	ST st;
	StackInit(&st);
	StackPush(&st,1);
	StackPush(&st, 1);
	StackPush(&st, 2);
	StackPush(&st, 3);
	StackPush(&st,4);
	StackPush(&st, 4);
	StackPush(&st, 5);
	/*StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);
	StackPop(&st);

	StackPop(&st);*/
	/*while (!STEmpty(&st))
	{
		int top = StackTop(&st);
		printf("%d ", top);
		StackPop(&st);
	}*/
	int size = StackSize(&st);
	printf("%d\n", size);
}
int main()
{
	test1();
	return 0;
}

用栈实现递归*

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

// 定义栈结构
typedef int STDataType;
typedef struct Stack {
    STDataType* arr;
    int top;        // 栈顶指针，指向栈顶元素的下一个位置
    int capacity;   // 容量
} ST;

// 栈的基本操作
void StackInit(ST* ps) {
    assert(ps);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

void StackPush(ST* ps, STDataType x) {
    assert(ps);
    if (ps->top == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
    ps->arr[ps->top++] = x;
}

void StackPop(ST* ps) {
    assert(ps);
    assert(ps->top > 0);
    ps->top--;
}

STDataType StackTop(ST* ps) {
    assert(ps);
    assert(ps->top > 0);
    return ps->arr[ps->top - 1];
}

int StackSize(ST* ps) {
    assert(ps);
    return ps->top;
}

void StackDestroy(ST* ps) {
    assert(ps);
    free(ps->arr);
    ps->arr = NULL;
    ps->top = ps->capacity = 0;
}

// 用栈模拟递归计算n的阶乘
int Factorial(int n) {
    if (n < 0) return -1; // 处理异常情况
    
    ST stack;
    StackInit(&stack);
    
    // 1. 模拟递归调用过程：将所有需要计算的数值入栈
    while (n > 1) {
        StackPush(&stack, n);
        n--;
    }
    
    // 2. 模拟递归返回过程：从栈顶开始计算
    int result = 1;
    while (StackSize(&stack) > 0) {
        result *= StackTop(&stack);
        StackPop(&stack);
    }
    
    StackDestroy(&stack);
    return result;
}

int main() {
    int num = 5;
    int result = Factorial(num);
    printf("%d的阶乘是: %d\n", num, result); // 输出：5的阶乘是: 120
    return 0;
}

队列（先进先出）

只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表
⼊队列：进⾏插⼊操作的⼀端称为队尾
出队列：进⾏删除操作的⼀端称为队头

队列实现

头文件（基本操作）：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
//队列结点的结构
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size; //队列中有效数据个数
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);

//入队——队尾
void QueuePush(Queue* pq, QDataType x);

//出队——队头
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);

//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);

结构

//队列结点的结构
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
//队列的结构
typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
	//int size; //队列中有效数据个数
}Queue;
  • 插入和删除操作效率高（队尾插入、队首删除均可在 O (1) 时间完成）
  • 不需要预先分配固定大小的内存，动态性好

初始化

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
	//pq->size = 0;
}
  1. 使用assert(pq)确保传入的队列指针pq不为空，避免空指针操作
  2. 将队头指针phead和队尾指针ptail都初始化为NULL，表示初始状态下队列为空
  3. 注释掉的pq->size = 0用于初始化队列元素个数（如果保留size成员的话）

判空

/队列判空
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL;
}

入队----队尾

//入队——队尾
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq ->phead!= NULL)//队列非空
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
	else//队列为空
	{
		pq->phead = pq->ptail = newnode;
	}
	//size++;
}
  1. 当队列为空时（phead为NULL），新节点既是队头也是队尾
  2. 当队列非空时，将新节点链接到当前队尾节点（ptail）的next，然后更新ptail指向新节点

出队----队头

//出队——队头
void QueuePop(Queue* pq)
{
	assert(!QueueEmpty(pq));
	if (pq->phead == pq->ptail)//只有一个节点，头尾都置为空
	{
		free(pq->phead);
		pq->phead=pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}
}
  1. 分两种情况处理：
    • 当队列中只有一个节点时（pq->phead == pq->ptail）：
      • 释放该节点内存
      • 将phead和ptail都置为NULL，保持空队列状态
    • 当队列中有多个节点时：
      • 先保存头节点的下一个节点指针
      • 释放头节点内存
      • 更新phead指向保存的下一个节点

优势：

  • 正确维护了队列的头指针和尾指针状态
  • 避免了内存泄漏（释放了被移除节点的内存）
  • 处理了队列从有元素变为空的边界情况

若包含size,size--保持数量一致

取队头队尾数据

//取队头数据
QDataType QueueFront(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}



//取队尾数据
QDataType QueueBack(Queue* pq)
{
	assert(!QueueEmpty(pq));
	return pq->ptail->data;

}

优势：

  • 时间复杂度都是 O (1)，效率很高
  • 仅获取元素值，不会修改队列的结构和状态
  • 依赖QueueEmpty函数判断队列是否为空，保持了代码的一致性
  • 符合队列 "先进先出" 的特性，分别提供了访问两端元素的接口

销毁

//销毁队列
void QueueDestroy(Queue* pq)
{
	assert（pq);
	QueueNode* pcur = pq->phead;
	while (pcur)
	{
		QueueNode* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	pq->phead = pq->ptail =NULL;
	//pq->size =0;
}

销毁队列是一个通用操作，即使队列为空（初始状态或已清空），也应该允许调用QueueDestroy，这样可以避免在调用销毁函数前还需要手动判断队列是否为空。

允许对空队列进行销毁

  • 当队列为空时，pcur初始为NULL，循环不会执行，直接重置phead和ptail
  • 当队列非空时，循环释放所有节点，最后重置指针

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布