首页 > 其他分享 >【数据结构】详细介绍栈和队列，解析栈和队列每一处细节

【数据结构】详细介绍栈和队列，解析栈和队列每一处细节

时间：2024-08-19 16:27:40浏览次数：9  
标签：每一处 ps obj 队列 为空 数据结构 节点 指针

目录

一. 栈

1. 栈的概念

2. 栈的实现

2.1 栈的结构

2.2 初始化栈

2.3 入栈

2.4 出栈

2.5 获取栈顶元素

2.6 获取栈中有效个数

2.7 判断栈是否为空

2.8 销毁栈 

二. 队列

1. 队列的概念

2. 队列的实现 

2.1 队列的结构

2.2 队列初始化 

2.3 销毁队列 

2.4 入队列(队尾) 

2.5 出队列(队头) 

2.6 获取队头数据 

2.7 获取队尾数据 

2.8 获取队列节点个数 

2.9 判断队列是否为空 

3. 循环队列

4. 编程题 设计循环队列 

三. 概念题

一. 栈

1. 栈的概念

1. 栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

2. 进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。

3. 栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。

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

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

2. 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些，因为数组在尾上插入数据的代价比较小。

2.1 栈的结构

1. top表示栈顶数据的下一个位置。

typedef int StackDataType;
typedef struct Stack
{
	StackDataType* arr; //用数组作为存放栈数据的结构
	int top;			//栈顶数据的下一个位置
	int capacity;		//容量
}Stack;

2.2 初始化栈

1. 将结构数据初始化。

void StackInit(Stack* ps)
{
	assert(ps);

	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

2.3 入栈

1. 判断扩容。

2. 数据插入栈顶。

void StackPush(Stack* ps, StackDataType data)
{
	assert(ps);

	//判断扩容
	if (ps->top == ps->capacity)
	{
		int size = ps->capacity == 0 ? 4 : ps->capacity * 2;
		StackDataType* tmp = (StackDataType*)realloc(ps->arr, sizeof(StackDataType)*size);
		if (tmp == NULL)
		{
			perror("realloc");
			return;
		}
		ps->arr = tmp;
		ps->capacity = size;
	}

	//入栈
	ps->arr[ps->top++] = data;
}

2.4 出栈

1. 栈不为空才能出栈。

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	ps->top--;
}

2.5 获取栈顶元素

1. 判断空栈

StackDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->arr[ps->top - 1];
}

2.6 获取栈中有效个数

int StackSize(Stack* ps)
{
	assert(ps);

	return ps->top;
}

2.7 判断栈是否为空

1. 栈空返回真。

bool StackEmpty(Stack* ps)
{
	assert(ps);

	return !ps->top;
}

2.8 销毁栈 

1. 释放空间，初始数据。

void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->arr);
	ps->arr = NULL;
	ps->top = ps->capacity = 0;
}

 完整代码：Stack/Stack · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

二. 队列

1. 队列的概念

1. 队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表。

2. 队列具有先进先出FIFO(First In First Out)的特点。

3. 入队列：进行插入操作，这一端称为队尾。

4. 出队列：进行删除操作，这一端称为队头。

2. 队列的实现 

队列也可以使用数组或链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1 队列的结构

1. 需要两个结构体，一个表示节点，一个表示队列整体。

2. 节点的结构包含存放的数据和指向下一个节点的指针。

3. 表示队列的结构包含队头指针和队尾指针还有节点的数量。

typedef int QueueDataType;
typedef struct QueueNode
{
	QueueDataType data;     //数据
	struct QueueNode* next; //下一个节点地址
}QueueNode;

typedef struct Queue
{
	QueueNode* prev; //队头指针
	QueueNode* tail; //队尾指针
	size_t size;     //节点个数
}Queue;

2.2 队列初始化 

1. 传入的队列指针不能为空。

2. 将队列结构体中队头队尾指针置空，节点数量置0。

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

	q->prev = q->tail = NULL;
	q->size = 0;
}

2.3 销毁队列 

1. 传入的队列指针不能为空。

2. 从队头指针开始遍历释放节点直到空停下，并将队头队尾指针置空，节点数量置0。

void QueueDestroy(Queue* q)
{
	assert(q);

	while (q->prev)
	{
		QueueNode* next = q->prev->next;
		free(q->prev);
		q->prev = next;
	}

	q->tail = NULL;
	q->size = 0;
}

2.4 入队列(队尾) 

1. 传入的队列指针不能为空。

2. 创建要入队列的节点

3. 当队列为空时，将队头队尾指针都指向新节点，节点数量加一。

4. 当队列不为空时，将新节点和最后一个节点连接，然后队尾指针指向新节点，节点数量加一。

void QueuePush(Queue* q, QueueDataType data)
{
	//1. 传入的队列指针不能为空。
	assert(q);

	//2. 创建要入队列的节点
	QueueNode* new = (QueueNode*)malloc(sizeof(QueueNode));
	if (new == NULL)
	{
		perror("malloc");
		return;
	}
	new->data = data;
	new->next = NULL;

	//3. 当队列为空时，然后将队头队尾指针都指向新节点，节点数量加一。
	if (q->size == 0)
	{
		q->prev = q->tail = new;
		q->size++;
	}
	//4. 当队列不为空时，将新节点和最后一个节点连接，然后队尾指针指向新节点，节点数量加一。
	else
	{
		q->tail->next = new;
		q->tail = new;
		q->size++;
	}
}

2.5 出队列(队头) 

1. 传入的队列指针不能为空。

2. 队列不能为空。

3. 释放第一个节点，队头指针指向第二个节点，节点数量减一。

4. 当队列删完之后没有节点了，这种情况需要特殊处理，防止队尾指针变成野指针。

void QueuePop(Queue* q)
{
	//1. 传入的队列指针不能为空。
	assert(q);
	//2. 队列不能为空。
	assert(q->size);

	//3. 释放第一个节点，队头指针指向第二个节点，节点数量减一。
	QueueNode* next = q->prev->next;
	free(q->prev);
	q->prev = next;
	q->size--;
	//4. 当队列删完之后没有节点了，这种情况需要特殊处理，防止队尾指针变成野指针。
	if (q->size == 0) q->tail = NULL;
}

2.6 获取队头数据 

1. 队列指针不能为空。

2. 队列不能为空。

3. 返回队头节点存放的数据。

QueueDataType QueueFront(Queue* q)
{
	//1. 队列指针不能为空。
	assert(q);
	//2. 队列不能为空。
	assert(q->size);

	//3. 返回队头节点存放的数据。
	return q->prev->data;
}

2.7 获取队尾数据 

1. 队列指针不能为空。

2. 队列不能为空。

3. 返回队尾节点存放的数据。

QueueDataType QueueBack(Queue* q)
{
	//1. 队列指针不能为空。
	assert(q);
	//2. 队列不能为空。
	assert(q->size);

	//3. 返回队尾节点存放的数据。
	return q->tail->data;
}

2.8 获取队列节点个数 

1. 队列指针不能为空。

2. 返回节点个数。

int QueueSize(Queue* q)
{
	//1. 队列指针不能为空。
	assert(q);

	//2. 返回节点个数。
	return q->size;
}

2.9 判断队列是否为空 

1. 队列指针不能为空。

2. 根据节点数量判断。空返回真。

bool QueueEmpty(Queue* q)
{
	//1. 队列指针不能为空。
	assert(q);

	//2. 根据节点数量判断。空返回真。
	return !q->size;
}

完整代码： Queue/Queue · 林宇恒/DataStructure - 码云 - 开源中国 (gitee.com)

3. 循环队列

1. rear的位置插入数据，然后rear++。

2. pop一次就是front往前移一位。

3. front == rear 表示空。

4. rear+1 == front 表示满，记得取模。

5. 这里使用数组实现，因为单链表不方便获取队尾数据。

4. 编程题 设计循环队列 

链接：. - 力扣（LeetCode）

typedef struct 
{
    int* arr;  //指向队列
    int front; //队头下标
    int rear;  //队尾下标
    int k;     
} MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int)*(k+1));
    obj->front = obj->rear = 0;
    obj->k = k;

    return obj;    
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    //队头下标等于队尾下标时为空。
    return obj->front == obj->rear;    
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    //队尾下标加一等于队头下标时为满，超出数组范围需要取模。
    return (obj->rear+1) % (obj->k+1) == obj->front;    
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    //满了不能插入。
    if(myCircularQueueIsFull(obj)) return false;
    else
    {
        //在队尾放数据，然后队尾加一，记得取模。
        obj->arr[obj->rear] = value;
        obj->rear = (obj->rear+1) % (obj->k+1);
        return true;
    }
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    //空的不能删。
    if(myCircularQueueIsEmpty(obj)) return false;
    else
    {
        //删除数据队头下标直接加一即可，记得取模。
        obj->front = (obj->front+1) % (obj->k+1);
        return true;
    }    
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj)) return -1;
    return obj->arr[obj->front];    
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj)) return -1;
    //当rear等于0时需要特殊处理
    return obj->arr[(obj->rear-1+obj->k+1)%(obj->k+1)];  
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->arr);   
    free(obj);
}

三. 概念题

一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（ ）。

A 12345ABCDE

B EDCBA54321

C ABCDE12345

D 54321EDCBA

答：B

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

答：C

循环队列的存储空间为 Q(1:100) ，初始状态为 front=rear=100 。经过一系列正常的入队与退队操作后， front=rear=99 ，则循环队列中的元素个数为（ ）

A 1

B 2

C 99

D 0或者100

答：D

以下( )不是队列的基本运算？

A 从队尾插入一个新元素

B 从队列中删除第i个元素

C 判断一个队列是否为空

D 读取队头元素的值 

答：B

现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)

A (rear - front + N) % N + 1

B (rear - front + N) % N

C (rear - front) % (N + 1)

D (rear - front + N) % (N - 1) 

答：B

标签：每一处,ps,obj,队列,为空,数据结构,节点,指针
From： https://blog.csdn.net/m0_71164215/article/details/141172560

相关文章

  • 算法与数据结构——时间复杂度
    时间复杂度运行时间可以直观且准确地反映算法的效率。要准确预估一段代码的运行时间，应该进行如下操作。确定运行平台，包括硬件配置、编程语言、系统环境等，这些因素都会影响代码的运行效率。评估各种计算操作的运行时间，例如加法操作需要1ns，乘法操作需要10ns，打印操作需要5ns等。......
  • 算法与数据结构——复杂度分析
    复杂度分析算法效率评估在算法设计中，我们追求以下两个层面的目标。找到问题解法：算法需要再规定的输入范围内可靠地求得问题的正确解寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。也就是说，在能够解决问题的前提下，算法效率已经成为衡量算法优劣的主......
  • 数据结构（二）- 线性表
    数据结构（二）-线性表数据结构三要素——逻辑结构、数据的运算、存储结构；存储结构不同运算实现的方式不同；1.线性表的定义定义：线性表是具有相同数据类型的n(n>0)个数据元素的有限序列，其中n为表长，当n=0线性表是一个空表。一般表示为L=(a1,a2,…,ai,ai+1,…,an)......
  • Linux学习记录（十一）———进程间的通信（消息队列）
    文章目录4.消息队列4.1特点4.2.相关函数ftok函数消息队列进程间的通信消息队列全双工通信4.消息队列消息队列，是消息的链表，存放在内核中，一个消息队列由一个标识符（队列ID）来标识。查看消息队列指令ipcs-q4.1特点消息队列是面向记录的，其中的消息具有特......
  • java队列
    1.队列定义：在Java中，队列（Queue）是一种常用的数据结构，属于java.util包。Queue接口继承自Collection接口，定义了一些基本操作，如入队、出队、查看队列头部等。Java提供了多种实现Queue接口的类，这些类可以满足不同的使用需求。2.Java队列的常见实现LinkedList：实现了Que......
  • 基础数据结构回顾记录
    数组初始化两种方式声明和初始化数组——使用new关键字和使用大括号。refer:https://www.freecodecamp.org/chinese/news/java-array-declaration-how-to-initialize-an-array-in-java-with-example-code/先声明，后赋值//数组声明dateType[]nameOfArray=newdataType......
  • 代码随想录算法训练营第10天|栈与队列part02
    150.逆波兰表达式求值本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题classSolution{public:intevalRPN(vector<string>&tokens){stack<longlong>st;for(conststring&token:tokens){if(token=="+......
  • 【数据结构与算法】如何构建最小堆
    最小堆的定义最小堆，作为一种独特且重要的数据结构，它是一种特殊的二叉树。在这种二叉树中，有一个关键的规则：每一个父节点所存储的值，都必然小于或者等于其对应的子节点的值。这一规则确保了根节点总是承载着整个堆中的最小数值。例如，下面这样一个简单的结构就是最小堆：1......
  • informer中的WorkQueue机制的实现分析与源码解读(3)之限速队列RateLimitingQueue
    概述前面2篇文章介绍了workqueue中的普通队列FIFO和延时队列。接下来我们分析workqueue中的第三种队列:限速队列client-go的util/workqueue包里主要有三个队列，分别是普通队列Queue，延时队列DelayingQueue，限速队列RateLimitingQueue，后一个队列以前一个队列的实现为基础，......
  • RabbitMQ集群 - 仲裁队列、Raft协议（最详细的选举流程）
    文章目录仲裁队列概述Raft协议概述基本概念选举流程（重点）消息复制仲裁队列的使用MQ管理平台SpringAMQP仲裁队列概述1）RabbitMQ普通队列在一个节点宕机之后，其他节点无法读写宕机节点的队列，为了解决这个问题，引入了仲裁队列.2）仲裁队列通过Raft协议，实现了不同......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99