数据结构之队列的实现(附源码)

这篇具有很好参考价值的文章主要介绍了数据结构之队列的实现(附源码)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、队列的概念及结构

二、队列的实现

 拓展:循环队列

三、初学的队列以及栈和队列结合的练习题


一、队列的概念及结构

队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头

数据结构之队列的实现(附源码),数据结构

二、队列的实现

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

数据结构之队列的实现(附源码),数据结构

 具体代码如下(C语言实现):

#pragma once

//Queue.h
// 链式结构:表示队列

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

typedef int QDateType;

typedef struct QListNode
{
	struct QListNode* _next;
	QDateType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;//队头
	QNode* _rear;//队尾
	int size;
}Queue;

// 初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDateType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDateType QueueFront(Queue* q);
// 获取队列队尾元素 
QDateType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
//Queue.c
#include "Queue.h"

void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
	q->size = 0;
}

void QueuePush(Queue* q, QDateType data)
{
	assert(q);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("tmp malloc");
		exit(-1);
	}
	tmp->_data = data;
	tmp->_next = NULL;

	if (q->_rear == NULL)
	{
		q->_front = q->_rear = tmp;
	}
	else
	{
		q->_rear->_next = tmp;
		q->_rear = tmp;
	}
	q->size++;
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));
	if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
	q->size--;
}

QDateType QueueFront(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));
	return q->_front->_data;
}

QDateType QueueBack(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));
	return q->_rear->_data;
}

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

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size;
}

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->_front;
	while (cur)
	{
		Queue* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}
//test.c
#include "Queue.h"


void test02()
{
	Queue q1;
	QueueInit(&q1);

	QueuePush(&q1, 1);
	QueuePush(&q1, 2);
	QueuePush(&q1, 3);
	QueuePush(&q1, 4);
	QueuePush(&q1, 5);

	QueuePop(&q1);

	while (QueueEmpty(&q1))
	{
		printf("%d ", QueueFront(&q1));
		QueuePop(&q1);
	}
	printf("\n");
	QueueDestroy(&q1);
}

int main()
{
	test02();

	return 0;
}

 拓展:循环队列

数据结构之队列的实现(附源码),数据结构

如上图所示:循环队列的节点数一般会比要求的节点数多一个,以便区分空的循环队列和满的循环队列。空的循环队列front和rear指向同一个节点,满的循环队列可以理解为rear = front + 1。

三、初学的队列以及栈和队列结合的练习题

题目一:设计循环队列

  • MyCircularQueue(k): 构造器,设置队列长度为 k 。
  • Front: 从队首获取元素。如果队列为空,返回 -1 。
  • Rear: 获取队尾元素。如果队列为空,返回 -1 。
  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
  • isEmpty(): 检查循环队列是否为空。
  • isFull(): 检查循环队列是否已满。
typedef struct 
{
    int* a;
    int front;
    int rear;
    int k;
} MyCircularQueue;


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

    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    //front和rear相等即为空
    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;
    obj->a[obj->rear] = value;
    ++obj->rear;
    //不然rear可能越界
    obj->rear %= (obj->k+1);

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    return false;
    obj->front++;
    obj->front %= (obj->k+1);
    return true; 
}

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

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    return -1;
    else
    //数学方法
    return obj->a[(obj->rear + obj->k) % (obj->k + 1)];
}

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

题目二:用队列实现栈

思路:用两个队列,保持一个队列为空一个不为空,当要出栈的时候就将不为空的队列中除了队尾的元素全都入到为空的队列中,然后将唯一的那个元素出栈。

typedef int QDateType;

typedef struct QListNode
{
	struct QListNode* _next;
	QDateType _data;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* _front;
	QNode* _rear;
	int size;
}Queue;


void QueueInit(Queue* q)
{
	assert(q);
	q->_front = NULL;
	q->_rear = NULL;
	q->size = 0;
}

void QueuePush(Queue* q, QDateType data)
{
	assert(q);
	QNode* tmp = (QNode*)malloc(sizeof(QNode));
	if (tmp == NULL)
	{
		perror("tmp malloc");
		exit(-1);
	}
	tmp->_data = data;
	tmp->_next = NULL;

	if (q->_rear == NULL)
	{
		q->_front = q->_rear = tmp;
	}
	else
	{
		q->_rear->_next = tmp;
		q->_rear = tmp;
	}
	q->size++;
}

void QueuePop(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));
	if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
	q->size--;
}

QDateType QueueFront(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));
	return q->_front->_data;
}

QDateType QueueBack(Queue* q)
{
	assert(q);
	assert(QueueEmpty(q));
	return q->_rear->_data;
}

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

int QueueEmpty(Queue* q)
{
	assert(q);
	return q->size;
}

void QueueDestroy(Queue* q)
{
	assert(q);
	QNode* cur = q->_front;
	while (cur)
	{
		Queue* next = cur->_next;
		free(cur);
		cur = next;
	}
	q->_front = q->_rear = NULL;
	q->size = 0;
}

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


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

    return tmp;
}

void myStackPush(MyStack* obj, int x) 
{
    if(QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) 
{
    Queue* empty = &obj->q1;
    Queue* noempty = &obj->q2;
    if(QueueEmpty(&obj->q1))
    {
        empty = &obj->q2;
        noempty = &obj->q1;
    }
    while(QueueSize(noempty) > 1)
    {
        QueuePush(empty, QueueFront(noempty));
        QueuePop(noempty);
    }
    int top = QueueFront(noempty);
    QueuePop(noempty);
    return top;
}

int myStackTop(MyStack* obj) 
{
    if(QueueEmpty(&obj->q1))
    return QueueBack(&obj->q1);
    else
    return QueueBack(&obj->q2);
}

bool myStackEmpty(MyStack* obj) 
{
    int ret1, ret2;
    if(QueueEmpty(&obj->q1) == 0)
    ret1 = 0;
    else
    ret1 = 1;
    if(QueueEmpty(&obj->q2) == 0)
    ret2 = 0;
    else
    ret2 = 1;

    if(ret1 == 0 && ret2 == 0)
    return true;
    else
    return false;
}

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

题目三:用栈实现队列

思路:使用两个栈,一个push栈一个pop栈,先往push栈中堆入元素,出队时,先将push栈中的元素先pop到pop栈中,再从pop栈中pop元素,其间再有元素堆入入到push栈中。文章来源地址https://www.toymoban.com/news/detail-704197.html

typedef int STDataType;
typedef struct Stack
{
	STDataType* _a;
	int _top;		// 栈顶
	int _capacity;  // 容量 
}Stack;

void StackInit(Stack* ps)
{
	assert(ps);
	ps->_a = NULL;
	ps->_top = 0;
	ps->_capacity = 0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->_capacity == ps->_top)
	{
		int newCapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->_a,sizeof(STDataType) * newCapacity);

		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->_a = tmp;
		ps->_capacity = newCapacity;
	}

	ps->_a[ps->_top] = data;
	ps->_top++;
}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	ps->_top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->_top > 0);
	return ps->_a[ps->_top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	return ps->_top;
}

int StackEmpty(Stack* ps)
{
	return ps->_top;
}

void StackDestroy(Stack* ps)
{
	assert(ps);
	free(ps->_a);
	ps->_a = NULL;
	ps->_capacity = 0;
	ps->_top = 0;
}


typedef struct 
{
    Stack pushst;
    Stack popst;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&obj->pushst);
    StackInit(&obj->popst);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) 
{
    StackPush(&obj->pushst, x);
}

int myQueuePeek(MyQueue* obj) 
{
    //pop栈为空就往其中堆入元素
    if(StackEmpty(&obj->popst) == 0)
    {
        while(StackEmpty(&obj->pushst) > 0)
        {
            StackPush(&obj->popst, StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}

int myQueuePop(MyQueue* obj) 
{
    int front = myQueuePeek(obj);
    StackPop(&obj->popst);
    return front;
}


bool myQueueEmpty(MyQueue* obj) 
{
    int ret1, ret2;
    if(StackEmpty(&obj->pushst) == 0)
    ret1 = 0;
    else
    ret1 = 1;
    if(StackEmpty(&obj->popst) == 0)
    ret2 = 0;
    else
    ret2 = 1;
    if(ret1 == 0 && ret2 == 0)
    return true;
    else
    return false; 
}

void myQueueFree(MyQueue* obj) 
{
    StackDestroy(&obj->pushst);
    StackDestroy(&obj->popst);
    free(obj);
}

到了这里,关于数据结构之队列的实现(附源码)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】:队列的实现

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如

    2024年02月07日
    浏览(36)
  • 【数据结构】队列的实现

    队列是一种常用的数据结构,也是一种操作受限制的线性表,特点是只允许在表的头部进行删除操作,在表的尾部进行插入操作,队列具有先进先出FIFO(First In First Out)。 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 我们实现可以用数组和链表

    2024年02月02日
    浏览(37)
  • 【数据结构—队列的实现】

    提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言 一、队列 1.1队列的概念及结构 二、队列的实现 2.1头文件的实现—Queue.h 2.2源文件的实现—Queue.c 2.3源文件的测试—test.c 三、测试队列实际数据的展示 3.1正常队列的出入 3.2入队列的同时存

    2024年02月04日
    浏览(40)
  • 数据结构---队列的实现

    前言 一、什么是队列? 二、 队列接口的实现 1. 队列结构的定义 2. 接口实现 总结 队列是一种特殊的线性表。 特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。 进行插入操作的端称为

    2024年02月02日
    浏览(33)
  • 数据结构—队列的实现

    前言:上次我们已经学习了数据结构中一个重要的线性表—栈,那么我们这一次就来学习另外一个重要的线性表—队列。 一、 队列的概念 二、 队列的实现: 1.队列的创建 三、 队列的操作 1.初始化队列 2.队尾入队列 3.队头出队列 4.获取队列头部元素 5.获取队列队尾元素 6.获

    2024年02月04日
    浏览(36)
  • 【数据结构】队列及其实现

    目录 😎前言 认识队列 队列的初始化 队列判空 数据队尾入队 数据队头出队 取队头数据 取队尾数据 队列数据的个数 队列销毁 总结 上次我们学习了栈及其实现,当然也少不它的好兄弟队列啦,今天我们开始队列的学习 队列的性质是 先进先出 ,就比如车辆进出隧道一般,它

    2024年02月09日
    浏览(43)
  • 数据结构 | 队列的实现

    队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出 FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如

    2024年02月05日
    浏览(41)
  • 【数据结构与算法】用队列实现栈&&用栈实现队列&&设计循环队列

    🌠 作者:@ 阿亮joy. 🎆 专栏:《数据结构与算法要啸着学》 🎇 座右铭:每个优秀的人都有一段沉默的时光,那段时光是付出了很多努力却得不到结果的日子,我们把它叫做扎根 请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、

    2024年01月20日
    浏览(43)
  • 【数据结构】 队列(Queue)与队列的模拟实现

    队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有==先进先出FIFO(FirstIn First Out) ==入队列: 进行插入操作的一端称为 队尾(Tail/Rear) 出队列: 进行删除操作的一端称为 队头(Head/Front) 在Java中, Queue是个接口,底层是通过链表实现

    2024年02月11日
    浏览(49)
  • 数据结构-用栈实现队列

    前言: 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 boolean empty() 如果队列为空,返回 true ;否

    2023年04月08日
    浏览(88)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包