当前位置： 首页 > article >正文

【落羽的落羽 数据结构篇】栈和队列

article 2025/2/22 4:37:05

在这里插入图片描述

文章目录

  • 一、栈
    • 1. 概念
    • 2. 栈操作
      • 2.1 定义栈结构
      • 2.2 栈的初始化
      • 2.3 入栈
      • 2.4 出栈
      • 2.5 取栈顶元素
    • 3. 栈的使用实例
  • 二、队列
    • 1. 概念
    • 2. 队列操作
      • 2.1 定义队列结构
      • 2.2 入队列
      • 2.3 出队列
      • 2.4 销毁队列
  • 三、用队列实现栈
  • 四、用栈实现队列

一、栈

1. 概念

栈（stack）是一种特殊的线性表，它只允许在一端进行插入和删除数据操作。进行插入和删除数据操作的一端称之为栈顶，另一端称之为栈底。栈中的数据元素遵循后进先出（Last In First Out）的原则
在这里插入图片描述
把栈想象成一个桶，数据只能从最上面投入，拿出时只能先拿出最上面的数据。比如：依次放入data1、data2、data3，再依次拿出，顺序则是data3、data2、data1在这里插入图片描述

  • 栈的插入数据操作叫做进栈/入栈/压栈，入数据在栈顶
  • 栈的删除数据操作叫做出栈，出数据也在栈顶

栈既然也是一种线性表，说明它在逻辑上是线性的，在物理上不一定是线性的。它的物理结构是否线性，取决于栈的底层结构，是数组还是链表。实现链表的操作中使用哪种都可以，相对而言数组的结构更优，因为使用数组新增数据比较容易，而链表还涉及开辟新节点。今天我们就展示用数组实现栈。

2. 栈操作

2.1 定义栈结构

typedef struct Stack
{
	STDataType* arr;
	int top; //指向栈顶的位置
	int capacity; //栈容量
}ST;

在这里插入图片描述

2.2 栈的初始化

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

测试：
在这里插入图片描述

2.3 入栈

插入数据前先检查空间是否足够，将新入栈的元素置于下标为top的位置，然后top++

void StackPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->top == ps->capacity) //如果空间不够，要增容
	{
		int newcapacity = ps->capacity == 0 ? 5 : 2 * ps->capacity;
		STDataType* tmp = (STDataType*)realloc(ps->arr, newcapacity * sizeof(STDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

测试：
在这里插入图片描述

2.4 出栈

void StackPop(ST* ps)
{
	assert(ps);
	assert(ps->top != 0); //保证栈不为空，否则无数据可删
	ps->top--;
}

测试：
在这里插入图片描述

2.5 取栈顶元素

STDataType StackTop(ST* ps)
{
	assert(ps);
	assert(ps->top != 0); //保证栈不为空，否则无数据可删
	return ps->arr[ps->top - 1];
}

测试：
在这里插入图片描述

3. 栈的使用实例

有些算法题要用到栈的特性，题目实例：有效的括号
https://leetcode.cn/problems/valid-parentheses/description/
在这里插入图片描述

思路：借助栈的特性，遍历字符串，遇到左括号入栈，遇到右括号就跟栈顶元素看是否是匹配的左括号，匹配就让左括号出栈，不匹配或栈为空则返回false，遍历完栈为空则返回true：

typedef struct Stack
{
	char arr[10001];
	int top; 
}ST;

bool isValid(char* s) {
    ST stack;
    stack.top = 0;
    char* pcur = s;
    while(*pcur != '\0')
    {
        if(*pcur == '(' || *pcur == '[' || *pcur == '{')
        {
	        stack.arr[stack.top++] = *pcur;
        }
        else
        {
            if(stack.top == 0)
            {
                return false;
            }
            char top = stack.arr[stack.top-1];
            if(top == '(' && *pcur != ')'
            || top == '[' && *pcur != ']'
            || top == '{' && *pcur != '}')
            {
                return false;
            }
            stack.top--;
        }
        pcur++;
    }
    bool ret = stack.top == 0? true: false;
    return ret; 
}

在这里插入图片描述
在这里插入图片描述

二、队列

1. 概念

队列（queue）是另一种特殊线性表，它只允许在一端进行插入数据操作，在另一端进行删除数据操作，队列具有先进先出（First In First Out）的特性。

  • 进行插入数据操作的一端称为队尾
  • 进行删除数据操作的一端称为队头

把队列想象成一个单向通道，数据只能依次从一端进入，依次从另一端出去在这里插入图片描述
队列也是线性表，说明队列的逻辑上是线性的。队列的底层结构要用数组还是链表呢？

不难想象：若用数组作为队列底层结构，把下标0作为队头，插入数据操作的时间复杂度为O(1)，删除数据操作的时间复杂度为O(n)，因为要把后面数据的下标遍历前挪；把下标0作为队尾，删除数据操作的时间复杂度为O(1)，插入数据操作的时间复杂度为O(n)，因为从队尾插入新数据要把后面数据的下标遍历后挪。
使用链表作为底层结构，只要保存队尾节点指针和队头节点指针，删除插入操作的时间复杂度都是O(1)。综上来看，使用链表实现队列更优。

2. 队列操作

2.1 定义队列结构

typedef int QDataType;

typedef struct QueueNode //队列节点结构
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue //队列结构
{
	QueueNode* phead; //队头
	QueueNode* ptail; //队尾
	//有时也需要来一个int size;记录有效元素个数
}Queue;

2.2 入队列

将一个新数据从队尾插入队列中

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) //队列为空，则newnode是队头也是队尾
	{
		pq->phead = pq->ptail = newnode;
	}
	else //队列不为空，则newnode插入到队尾
	{
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	//pq->size++;
}

测试：在这里插入图片描述

2.3 出队列

将队头数据从队列中删除

void QueuePop(Queue* pq)
{
	assert(pq->phead != NULL); //队列不能为空，否则无数据可出
	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;
	}
	//pq->size--;
}

测试：在这里插入图片描述

2.4 销毁队列

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

测试：
在这里插入图片描述
在这里插入图片描述

三、用队列实现栈

题目：用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/
在这里插入图片描述

我们要用两个队列实现栈的特性先进后出

  • push：入栈：往不为空的队列中插入数据
  • pop：出栈：把不为空的队列中的前size-1个数据挪到另一个队列中，再将该队列中的最后一个数据出队列
  • top：取栈顶元素（不出数据）：取不为空的队列中的队尾数据
  • empty：判断栈是否为空：看两个队列是不是都为空
typedef struct QueueNode
{
	int data;
	struct QueueNode* next;
}QueueNode;

//定义队列的结构
typedef struct Queue {
	QueueNode* phead;//队头
	QueueNode* ptail;//队尾
	int size;//记录有效数据个数
}Queue;

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
    pq->size = 0;
}

//销毁队列
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;
}

//入队---队尾
void QueuePush(Queue* pq, int x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->next = NULL;

	//队列为空，newnode是队头也是队尾
	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else {
		//队列非空，直接插入到队尾
		pq->ptail->next = newnode;
		pq->ptail = pq->ptail->next;
	}
	pq->size++;
}

//出队---队头
void QueuePop(Queue* pq)
{
	assert(pq->phead != NULL);
	//只有一个结点的情况
	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;
	}
	pq->size--;
}

/以上是要用到的队列操作

typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

void myStackPush(MyStack* obj, int x) {
    if(obj->q1.phead != NULL)
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    //找不为空的队列，将不为空队列的前size-1个数据挪到空队列
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if(obj->q1.phead != NULL)
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    while(noempty->size > 1)
    {
        //把noempty的队头数据挪到空队列中
        QueuePush(empty, noempty->phead->data);
        QueuePop(noempty);
    }
    int top = noempty->phead->data;
    QueuePop(noempty);
    return top;
}

int myStackTop(MyStack* obj) {
    if(obj->q1.phead != NULL)
    {
        return obj->q1.ptail->data;
    }
    else
    {
        return obj->q2.ptail->data;
    }
}

bool myStackEmpty(MyStack* obj) {
    if(obj->q1.phead == NULL && obj->q2.phead == NULL)
        return true;
    return false;
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
    obj == NULL;
}

在这里插入图片描述

四、用栈实现队列

题目：用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
在这里插入图片描述
我们要用两个栈实现队列的特性先进先出
思路：一个栈命名为pushST，一个栈命名为popST

  • 入队：往pushST中插入数据
  • 出队：若popST不为空则直接出数据，否则将pushST的数据先挪到popST中再从popST出数据
  • 找队头数据：逻辑同出队操作，只不过只取数据不用pop
typedef struct Stack
{
	int* arr;
	int top;       //指向栈顶的位置
	int capacity;  //容量
}ST;

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

//栈销毁
void STDestroy(ST* ps)
{
	if (ps->arr)
		free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

//入栈----栈顶
void StackPush(ST* ps, int x)
{
	assert(ps);
	if (ps->top == ps->capacity)
	{
		//空间不够---增容
		int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		int* tmp = (int*)realloc(ps->arr, newCapacity * sizeof(int));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		ps->arr = tmp;
		ps->capacity = newCapacity;
	}
	//空间足够
	ps->arr[ps->top++] = x;
}

//出栈----栈顶
void StackPop(ST* ps)
{
	assert(ps->top != 0);
	--ps->top;
}

//取栈顶数据
int StackTop(ST* ps)
{
	assert(ps->top != 0);
	return ps->arr[ps->top - 1];
}


//以上是要用到的栈操作

typedef struct {
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() {
    MyQueue* pq = (MyQueue*)malloc(sizeof(MyQueue));
    STInit(&pq->pushST);
    STInit(&pq->popST);
    return pq;
}

void myQueuePush(MyQueue* obj, int x) {
    //往pushST中插入数据
    StackPush(&obj->pushST, x);
}

int myQueuePop(MyQueue* obj) {
    if(obj->popST.top == 0) //popST为空
    {
        //从pushST中挪数据
        while(obj->pushST.top != 0)
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    //popST不为空
    int top = StackTop(&obj->popST);
    StackPop(&obj->popST);
    return top;
}

int myQueuePeek(MyQueue* obj) {
    if(obj->popST.top == 0) //popST为空
    {
        //从pushST中挪数据
        while(obj->pushST.top != 0)
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
    //popST不为空
    int top = StackTop(&obj->popST);
    return top;
}

bool myQueueEmpty(MyQueue* obj) {
    if(obj->pushST.top == 0 && obj->popST.top == 0)
        return true;
    return false;
}

void myQueueFree(MyQueue* obj) {
    STDestroy(&obj->pushST);
    STDestroy(&obj->popST);
    free(obj);
    obj = NULL;
}

在这里插入图片描述
在这里插入图片描述
本篇完，感谢阅读


http://www.kler.cn/a/552908.html

相关文章：

  • 从零开始学习服务网格：2025全面指南
  • 【ISO 14229-1:2023 UDS诊断（ECU复位0x11服务）测试用例CAPL代码全解析⑰】
  • 基于 Redisson 分布式锁 实现报名人数限制功能
  • Python----数据结构（栈：列表栈，链栈。初始化，入栈，出栈，获取栈长度，判断是否为空，访问栈顶元素）
  • GcExcel
  • K8S的Dashboard登录及验证
  • 【数据挖掘】--算法
  • Python 学习之旅：高级阶段（十）数据库操作 MongoDB
  • Spark算子：大数据处理的魔法棒
  • Spring Bean 生命周期
  • 机器学习小项目之鸢尾花分类
  • ubuntu系统中新增硬盘挂载硬盘
  • SVN 创建版本库
  • 力扣 买卖股票的最佳时机
  • PyCharm Terminal 自动切换至虚拟环境
  • module ‘cv2.dnn‘ has no attribute ‘DictValue‘解决办法
  • Java并发编程面试题：锁（17题）
  • AI时代的前端开发：新兴职位与效率提升工具
  • QT异步编程之QMetaObject::invokeMethod
  • 极限网关 INFINI Gateway 配置文件核心解读