首页 > 其他分享 >数据结构:栈、队列详解篇

数据结构:栈、队列详解篇

时间:2024-08-22 14:25:39浏览次数:13  
标签:pS pQue return 队列 int 详解 数据结构 data

数据结构:栈、队列详解篇

一、栈

(一)栈的概念

在这里插入图片描述

⼀种特殊的线性表,其只允许在固定的⼀端进⾏插⼊和删除元素操作。进⾏数据插⼊和删除操作的⼀端称为栈顶,另⼀端称为栈底。栈中的数据元素遵守后进先出的原则。

(二)栈的实现

1、结构定义

在定义栈时,我们下面用数组实现栈,用到 typedef 可以使得栈的数据类型更广。

typedef int StackDataType;

typedef struct Stack {
	StackDataType* data;
	int capacity;
	int top;
}Stack;

2、功能实现

(1)栈的初始化

我们传进来的栈是 &(变量)的形式,因此这里不用使用 malloc 为栈开辟空间。

void StackInit(Stack* pS) {
	assert(pS);
	pS->data = NULL;
	pS->capacity = 0;
	pS->top = 0;
	return;
}
(2)栈的销毁

只用对 data 进行释放即可,因为栈本身没有进行动态空间的申请,就不用释放,但是要记得把变量的 capacity 和 top 重置为 0

void StackDestroy(Stack* pS) {
	assert(pS);
	if (pS->data) {
		free(pS->data);
		pS->data = NULL;
	}
	pS->capacity = pS->top = 0;
	return;
}
(3)栈的扩容

利用 realloc 进行扩容即可,三目运算符记得栈初始化大小为 0

void StackCheckCapacity(Stack* pS) {
	assert(pS);
	if (pS->capacity == pS->top) {
		int capacity = pS->capacity == 0 ? 4 : 2 * pS->capacity;
		StackDataType* s = (StackDataType*)realloc(pS->data, sizeof(StackDataType) * capacity);
		if (s == NULL) {
			perror("realloc fail!");
			exit(1);
		}
		pS->data = s;
		pS->capacity = capacity;
	}
	return;
}
(4)压栈

检查容量后压栈

void StackPush(Stack* pS, StackDataType x) {
	assert(pS);
	StackCheckCapacity(pS);
	pS->data[pS->top] = x;
	pS->top += 1;
	return;
}
(5)出栈

直接 -1 即可,空间还再只是不可非法访问。

void StackPop(Stack* pS) {
	assert(pS);
	pS->top -= 1;
	return;
}
(6)取栈顶元素、判空、栈的大小

这三个操作比较简单,但是记得断言一下指针是否为空,或者栈是否为空

bool StackEmpty(Stack* pS) {
	assert(pS);
	return pS->top == 0;
}

int StackSize(Stack* pS) {
	assert(pS);
	return pS->capacity;
}

//取栈顶元素
StackDataType StackTop(Stack* s) {
	assert(s);
	assert(!StackEmpty(s));
	return s->data[s->top - 1];
}

(三)例题分析

1、有效的括号

https://leetcode.cn/problems/valid-parentheses/description/在这里插入图片描述

题目分析

采用栈来解决,如果是左括号进栈,右括号出栈,最后判断栈是否为空,
下面直接用STL提供的stack来实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        int i = 0;
        while (s[i]) {
            if (s[i] == '{' || s[i] == '[' || s[i] == '(') {
                st.push(s[i]);
            } else if (!st.empty() && (s[i] == '}' && st.top() == '{' ||
                        s[i] == ']' && st.top() == '[' ||
                        s[i] == ')' && st.top() == '(')) {
                st.pop();
            } else {
                return false;
            }
            i += 1;
        }
        if (st.empty())
            return true;
        return false;
    }
};

二、队列

(一)队列的概念

在这里插入图片描述

概念:只允许在⼀端进⾏插⼊数据操作,在另⼀端进⾏删除数据操作的特殊线性表,队列具有先进先出的性质
⼊队列:进⾏插⼊操作的⼀端称为队尾
出队列:进⾏删除操作的⼀端称为队头

(二)队列的实现

1、结构定义

我们下面用链表来实现队列,需要用到两个结构体定义结点结构和队列结构

typedef int QueueDataType;
typedef struct QueueNode {
	QueueDataType data;
	struct QueueNode* next;
}QueueNode;

typedef struct Queue {
	QueueNode* head;
	QueueNode* tail;
	int size;
}Queue;

2、功能实现

(1)队列结点生成

用队列的指针来接收动态内存申请的空间

QueueNode* BuyNode(QueueDataType data) {
	QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode));
	if (p == NULL) {
		perror("malloc fail!");
		exit(1);
	}
	p->data = data;
	p->next = NULL;
	return p;
}
(2)队列初始化
void QueueInit(Queue* pQue) {
	assert(pQue);
	pQue->head = pQue->tail = NULL;
	pQue->size = 0;
	return;
}
(3)入队列

记得处理队列结点为空的情况

void QueuePush(Queue* pQue, QueueDataType data) {
	assert(pQue);
	QueueNode* node = BuyNode(data);
	if (pQue->head == NULL) {
		pQue->head = pQue->tail = node;
	}
	else {
		pQue->tail->next = node;
		pQue->tail = node;
	}
	pQue->size += 1;
	return;
}
(4)出队列

元素个数为 1 时,需要特殊处理。

void QueuePop(Queue* pQue) {
	assert(pQue);
	assert(!QueueEmpty(pQue));
	pQue->size -= 1;
	if (pQue->head == pQue->tail) {
		free(pQue->head);
		pQue->head = pQue->tail = NULL;
		return;
	}
	QueueNode* node = pQue->head;
	pQue->head = pQue->head->next;
	free(node);
	node = NULL;
	return;
}
(5)队列的销毁

遍历队列结点后销毁,然后记得将指针置空,将元素数量置为 0

void QueueDestroy(Queue* pQue) {
	assert(pQue);
	if (QueueEmpty(pQue)) return;
	QueueNode* p = pQue->head;
	while (p) {
		QueueNode* node = p;
		p = p->next;
		free(node);
	}
	pQue->head = pQue->tail = NULL;
	pQue->size = 0;
	return;
}
(6)队列判空、取队列首元素、尾元素、数据个数

代码难度不大,一样断言判断传入的数据是不是有效数据,以及+队列是否为空

bool QueueEmpty(Queue* pQue) {
	assert(pQue);
	return pQue->head == NULL && pQue->tail == NULL;
}


QueueDataType QueueFront(Queue* pQue) {
	assert(pQue);
	assert(!QueueEmpty(pQue));
	return pQue->head->data;
}

QueueDataType QueueBack(Queue* pQue) {
	assert(pQue);
	assert(!QueueEmpty(pQue));
	return pQue->tail->data;
}

int QueueSize(Queue* pQue) {
	assert(pQue);
	return pQue->size;
}

(三)例题分析

1、用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/description/
在这里插入图片描述

题目分析

创建两个栈 pushS 和 popS
push 操作直接往 pushS 里面压入元素
pop 操作弹出 popS 的栈顶元素。如果popS里面没有元素,就将pushS 的元素放进popS,再弹出栈顶元素

class MyQueue {
public:
    stack<int> pushS;
    stack<int> popS;

    MyQueue() {}
    
    void push(int x) {
        pushS.push(x);
    }
    
    int pop() {
        if(popS.empty()){
            while(pushS.size()){
                int top = pushS.top();
                popS.push(top);
                pushS.pop();
            }
        }
        int ret = popS.top();
        popS.pop();
        return ret;
    }
    
    int peek() {
        if(popS.empty()){
            while(pushS.size()){
                int top = pushS.top();
                popS.push(top);
                pushS.pop();
            }
        }
        return popS.top();
    }
    
    bool empty() {
        return popS.empty() && pushS.empty();
    }
};

小结:队列的两道题涉及栈和队列的相互转换,同时可以用来提升思维能力

2、用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/description/
在这里插入图片描述

题目分析

用两个队列实现栈, 两个队列中,一个队列设置为空,另外一个放元素。
push 操作直接往有元素的队列放入元素即可。
pop 操作要先将有元素的队列 size - 1 个元素依次出队列,按照出队列顺序进入另外一个队列,然后弹出并返回最后一个元素即可。
top 操作直接返回有元素队列的最后一个元素。

class MyStack {
public:
    queue<int> q1;
    queue<int> q2;
    
    MyStack() {}
    
    void push(int x) {
        if (!q1.empty()) {
            q1.push(x);
        } else {
            q2.push(x);
        }
    }
    int pop() {
        queue<int> *emp = &q1;
        queue<int> *nemp = &q2;
        if (!q1.empty()) {
            emp = &q2, nemp = &q1;
        }
        int n = nemp->size() - 1;
        while (n--) {
            emp->push(nemp->front());
            nemp->pop();
        }
        int ret = nemp->front();
        nemp->pop();
        return ret;
    }

    int top() {
        queue<int> *emp = &q1;
        queue<int> *nemp = &q2;
        if (!q1.empty()) {
            emp = &q2, nemp = &q1;
        }
        return nemp->back();
    }

    bool empty() { return q1.empty() && q2.empty(); }
};

小结:这里不要错误的直接用引用取别名,emp 和 nemp 不然后面不可以修改

3、设计循环队列

https://leetcode.cn/problems/design-circular-queue/description/
在这里插入图片描述

class MyCircularQueue {
public:
    int* data;
    int capacity;
    int tail;
    int head;

    MyCircularQueue(int k) {
        data = (int*)malloc(sizeof(int) * (k + 1));
        capacity = k + 1;
        head = tail = 0;
    }
    
    bool enQueue(int value) {
        if(isFull()) return false;
        data[tail] = value;
        if((tail + 1) == capacity) tail = 0;
        else tail++;
        return true;
    }
    
    bool deQueue() {
        if(isEmpty()) return false;
        if((head + 1) == capacity) head = 0;
        else head++;
        return true;
    }
    
    int Front() {
        if(isEmpty()) return -1;
        return data[head];
    }
    
    int Rear() {
        if(isEmpty()) return -1;
        int ind = tail - 1;
        if(tail == 0) ind = capacity - 1;
        return data[ind];
    }
    
    bool isEmpty() {
        return head == tail;
    }
    
    bool isFull() {
        return ((tail + 1) % capacity) == head;
    }
};

小结:设计循环队列时,可以在申请 data 空间时多申请一份,这样就不用再创建另外的变量。另外,注意在 head tail 指针在 ++ 过程中,如果越界了要将位置移动到 0。

结束语

栈和队列的分析就到这里了,如果文章可以帮助到你,那真的十分有幸,记得动手支持支持小编哦!
在这里插入图片描述

标签:pS,pQue,return,队列,int,详解,数据结构,data
From: https://blog.csdn.net/2301_81454749/article/details/141403569

相关文章

  • 详解Elastic Search及架构
    前言             如果我有三段文本,id分别为0、1、2,具体如下,我要找到哪段文本里有关键词es,这时最容易想到的办法就是依次遍历文本,匹配es,最后将符合的文本id输出。    0 ilike es    1 ilovees    2 iusedevops......
  • Static关键字详解
    Static关键字是什么static修饰的代码属于类定义的变量存储在方法区的静态常量池当中java为什么要设置static关键字?因为要方便类去使用自己的方法和变量例如:1.方法和变量上面没有static关键字packageWork1;publicclassA{publicStringname="张三";pub......
  • 数据结构链表入门指南 链表基本代码实现以及测试步骤
    链表介绍链表是一种数据结构,它由一系列节点组成,每个节点包含数据部分和指向下一个节点的指针。链表的基本特性包括:动态大小:链表的大小可以根据需要动态调整,不像数组那样需要事先定义固定大小。节点连接:每个节点通过指针连接到下一个节点,从而形成一个链状结构。灵活插入和......
  • Redis 数据类型详解
    Redis是一个开源的内存数据结构存储系统,广泛应用于缓存、消息队列、实时数据分析等场景。Redis提供了多种数据类型,本文将详细介绍Redis的五种主要数据类型及其应用场景,并从概述、基本操作、应用场景和数据结构等方面进行深入探讨。1.字符串(String)概述字符串是Redis......
  • MySQL 数据类型详解
    MySQL是一种广泛使用的关系型数据库管理系统,它支持多种数据类型以满足各种应用场景的需求。本文将详细介绍MySQL支持的数据类型、它们的使用场景以及实现原理,并通过图示帮助读者更直观地理解。目录简介数值类型整型浮点型定点型日期和时间类型字符串类型字符串二进制字......
  • 位运算符-按位取反运算符补充详解
    位运算符在计算机中用于直接操作整数的二进制位的运算符。这些运算符通常用于低级编程和优化特定类型的计算任务。以下是几种常见的位运算符及其解释:按位与(&):对应位都是1时结果为1,否则为0。例如:0101&0111=0101按位或(|):只要对应位有一个是1,结果就为1。例如:0101|0111=......
  • 为什么用Vite框架?来看它的核心组件案例详解
    Vite是一个前端构建工具,它以其快速的开发服务器和生产优化的打包器而闻名前端界,今天的内容,必须得唠唠Vite的关键能力,以下是Vite的核心组件分析,以及使用案例:原理分析:Vite利用了现代浏览器对ESModule语法的支持,在开发环境中不进行打包编译,而是通过启动本地devServer......
  • cnhw06s.dll谜团揭秘:硬件加速支持的权威修复策略详解
    解决cnhw06s.dll文件丢失的问题,可以尝试以下步骤来恢复硬件支持功能:1.系统还原:•如果你知道DLL文件丢失前的一个还原点,可以尝试使用Windows的系统还原功能回到那个状态。2.重新安装相关软件:•cnhw06s.dll通常与某些硬件相关的软件或驱动程序关联。尝试确定该DLL属于哪个程......
  • 触摸输入故障深度剖析:tiptsf.dll修复的高级策略详解
    针对tiptsf.dll文件丢失或损坏导致的触摸输入问题,可以采取以下专业修复步骤:1.安全模式启动:首先,尝试重启计算机进入安全模式。这有助于防止加载可能干扰修复过程的第三方服务。2.系统还原点:检查是否有最近的系统还原点。通过“控制面板”->“系统”->“系统保护”->......
  • 提升代码迭代速度的Python重载方法使用详解
        概要在Python编程中,模块是组织代码的重要工具,它们使得代码更加模块化和易于维护。在开发和调试过程中,有时需要对已经导入的模块进行修改并重新加载以应用更改。Python提供了一个名为reload的模块,用于在不重新启动解释器的情况下重新加载已经导入的模块。本文将详......