C语言循环队列与用队列实现栈问题解析

目录

“莫听穿林打叶声,何妨吟啸且徐行”

这里是目录 循环队列题目描述题目链接思路分析代码实现 用队列实现栈题目描述题目链接思路分析代码实现

循环队列

循环队列: 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环
循环队列的好处可以重新利用队列的空间。我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

题目描述

设计你的循环队列实现。
你的实现应该支持如下操作:

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

题目链接

LeetCode622. 设计循环队列

思路分析

循环队列和普通队列对比。

循环队列:入队需要尾插。出队需要头删,删除并不是真正的删除,只需要使头指针往后移动就可以了,因为要重复利用其空间。真正意义上只需要尾插罢了。尾插的话链表和顺序表时间复杂度相同。综上所述:所以循环队列用顺序表或者链表实现都可以,差异不大。要真正的谁更优,因为顺序表物理空间是连续的,CPU缓存命中率高。所以顺序表更好一点。
普通队列:入队需要尾插,出队需要头删,头删需要真正的删除,但是顺序表头删后还需要覆盖,效率低,所以用单链表实现。

思路 :
1.创建循环队列结构体,包含一个顺序表a,头指针和尾指针head和tail,队列的长度k。
2.要为队列多开一个空间,这样可以正确判断队列是否为空,或者是否满了。红色的空间是多开的一个空间。
3.循环队列的关键在于判断队列是否为空或者队列是否满了。
为空:只有当tail == head才为空。
满了:分两种情况。
情况1.当tail == 队列长度(k) && head == 0
情况2:当tail+1 == head时

代码实现

代码写好后。经过我数十次的调试,bug终于调完。
说一说我遇到的bug:
1.第一次提交发现循环队列的创建失败。原因是没有对循环队列的结构体进行初始化。
2.在获取尾部元素的时候报错。漏掉了一个特殊情况,就是假如尾部的元素在第一个怎么办?这时候tail-1就变为-1了。数组产生了越界。这时候报的错误是一堆看不懂的内存错误,让人摸不着头脑。
3.在入队的时候发生错误。逻辑错误。要牢记tail指向的是即将入队的空间。应该先入队,tail再++。

typedef struct {    int* a;    int head;    int tail;    int k;} MyCircularQueue;bool myCircularQueueIsEmpty(MyCircularQueue* obj) ;bool myCircularQueueIsFull(MyCircularQueue* obj) ;MyCircularQueue* myCircularQueueCreate(int k){    //给结构体指针变量开辟空间,否则为野指针。    MyCircularQueue* new =(MyCircularQueue*)malloc(sizeof(MyCircularQueue));    int* b = (int*)malloc(sizeof(int)*(k+1));    new->a = b;    new->head = 0;    new->tail = 0;    new->k = k;    return new;}bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {    assert(obj);    if(myCircularQueueIsFull(obj))    {        return false;    }        obj->a[obj->tail] = value;    if(obj->tail == obj->k)    {        obj->tail = 0;    }    else    {     obj->tail++;    }    return true;}bool myCircularQueueDeQueue(MyCircularQueue* obj) {     assert(obj);     if(myCircularQueueIsEmpty(obj))     {         return false;     }      if(obj->head == obj->k)     {        obj->head = 0;    }        else        {            obj->head++;        }         return true;}int myCircularQueueFront(MyCircularQueue* obj) {    assert(obj);    if(myCircularQueueIsEmpty(obj))    {        return -1;    }    return obj->a[obj->head];}int myCircularQueueRear(MyCircularQueue* obj) {     assert(obj);     if(myCircularQueueIsEmpty(obj))     {         return -1;     }     if(obj->tail == 0)     {         return obj->a[obj->k];     }     return obj->a[obj->tail-1];}bool myCircularQueueIsEmpty(MyCircularQueue* obj) {    assert(obj);    return obj->head == obj->tail;}bool myCircularQueueIsFull(MyCircularQueue* obj) {     assert(obj);     if(obj->head==0 && obj->tail == obj->k)     {         return true;     }     else     {         return obj->head == obj->tail+1;     }}void myCircularQueueFree(MyCircularQueue* obj) {    assert(obj);    free(obj->a);    free(obj);}

用队列实现栈

用两个队列实现一个栈的基本功能。用C语言做,需要先创建两个队列。

题目描述

请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通栈的全部四种操作(push、top、pop 和 empty)。

题目链接

LeetCode225. 用队列实现栈

思路分析

此题和用栈实现队列往期博客是个兄弟题。差不多。
思路:
1.压栈就是谁不为空就往谁里面进行入队。
2.出栈就是先把不为空的一个队列里面的前k-1个元素入队到为空那个队列。然后再把不为空那个队列的元素pop掉。

代码实现

我遇到的bug
1.判断到底哪个队列是空队列,可以用假设法。假设其中一个为空,另一个不为空,然后再做调整。这样后续就方便了。

 //假设后调整     Queue* emptyQ = &obj->q1;    Queue* nonEmptyQ = &obj->q2;    if(!QueueEmpty(&obj->q1))    {        emptyQ = &obj->q2;        nonEmptyQ = &obj->q1;    }

2.移动前k-1个元素到另一个队列不能用遍历。遍历会麻烦,且每一次出队,头指针会自动移动。所以直接用算出队列的长度解决移动前k-1元素。

typedef int QDataType;typedef struct QueueNode{QDataType data;struct QueueNode* next;}QNode;typedef struct Queue{QNode* head;QNode* tail;//size_t size;}Queue;void QueueInit(Queue* pq);void QueueDestory(Queue* pq);void QueuePush(Queue* pq, QDataType x);void QueuePop(Queue* pq);bool QueueEmpty(Queue* pq);size_t QueueSize(Queue* pq);QDataType QueueFront(Queue* pq);QDataType QueueBack(Queue* pq);void QueueInit(Queue* pq){assert(pq);pq->head = pq->tail = NULL;}void QueueDestory(Queue* pq){assert(pq);QNode* cur = pq->head;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;}void QueuePush(Queue* pq, QDataType x){assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));assert(newnode);newnode->data = x;newnode->next = NULL;if (pq->tail == NULL){assert(pq->head == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}}void QueuePop(Queue* pq){assert(pq);assert(pq->head && pq->tail);if (pq->head->next == NULL){free(pq->head);pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}}bool QueueEmpty(Queue* pq){assert(pq);return pq->head == NULL;}size_t QueueSize(Queue* pq){assert(pq);QNode* cur = pq->head;size_t size = 0;while (cur){size++;cur = cur->next;}return size;}QDataType QueueFront(Queue* pq){assert(pq);assert(pq->head);return pq->head->data;}QDataType QueueBack(Queue* pq){assert(pq);assert(pq->tail);return pq->tail->data;}//创建两个队列typedef struct {    Queue q1;    Queue q2;} MyStack;//初始化两个队列MyStack* myStackCreate() {     MyStack* new = (MyStack*)malloc(sizeof(MyStack));     assert(new);     QueueInit(&new->q1);     QueueInit(&new->q2);     return new;}//谁不为空就在谁里面入队void myStackPush(MyStack* obj, int x){    assert(obj);    if(!QueueEmpty(&obj->q2))    {        QueuePush(&obj->q2, x);    }    else    {        QueuePush(&obj->q1, x);    }}int myStackPop(MyStack* obj) {    assert(obj);    //假设后调整     Queue* emptyQ = &obj->q1;    Queue* nonEmptyQ = &obj->q2;    if(!QueueEmpty(&obj->q1))    {        emptyQ = &obj->q2;        nonEmptyQ = &obj->q1;    }      while(QueueSize(nonEmptyQ) > 1)    {        int front = QueueFront(nonEmptyQ);        QueuePush(emptyQ, front);        QueuePop(nonEmptyQ);    }    int top = QueueFront(nonEmptyQ);    QueuePop(nonEmptyQ);    return top;}int myStackTop(MyStack* obj) {  assert(obj);    int ret = 0;  if(!QueueEmpty(&obj->q1))  {      ret = QueueBack(&obj->q1);  }  else  {      ret = QueueBack(&obj->q2);  }  return ret;}bool myStackEmpty(MyStack* obj) {     assert(obj);     return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);}void myStackFree(MyStack* obj) {    assert(obj);    QueueDestory(&obj->q1);    QueueDestory(&obj->q2);    free(obj);}
(0)

相关推荐

  • C语言循环队列的表示与实现实例详解

    1.概述: C语言的队列(queue),是先进先出(FIFO, First-In-First-Out)的线性表数据结构.在具体应用中通常用链表或者数组来实现.队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作. 循环队列可以更简单的防止伪溢出的发生,但是队列大小是固定的. 2.实例代码: /* 队列的顺序存储结构(循环队列) */ #define MAX_QSIZE 5 /* 最大队列长度+1 */ typedef struct { QElemType *base

  • 详解数据结构C语言实现之循环队列

    本文讲的是循环队列,首先我们必须明白下面几个问题 循环队列的基础知识 1.循环队列需要几个参数来确定 循环队列需要2个参数,front和rear 2.循环队列各个参数的含义 (1)队列初始化时,front和rear值都为零: (2)当队列不为空时,front指向队列的第一个元素,rear指向队列最后一个元素的下一个位置: (3)当队列为空时,front与rear的值相等,但不一定为零: 3.循环队列入队的伪算法 (1)把值存在rear所在的位置: (2)rear=(rear+1)%maxsize

  • C语言实现循环队列基本操作

    循环队列依靠取模运算,实现队列中数据元素的逻辑成环操作.其相比队列的顺序存储实现,可以避免"假溢出"的问题. 头文件声明 #include <stdio.h> #include <stdlib.h> /* * 循环队列实现 */ //数据元素上限 #define MaxSize 50 //定义数据类型 typedef int ElemType; /*结构体定义*/ typedef struct SqQueue { ElemType data[MaxSize];/

  • C语言实现循环队列

    本文实例为大家分享了C语言实现循环队列的具体代码,供大家参考,具体内容如下 注意事项: 1.循环队列,是队列的顺序表示和实现.因为是尾进头出,所以和顺序栈不同的是需要将顺序队列臆造成一个环状的空间,以便在尾部添加满之后从头部空位开始插入. 2.也可以使用数组队列,也就是不能动态增长的顺序队列,这样不需要每次取模最大值来构成环形空间.每次插入新的队列尾元素时,尾指针增1,每当删除队列头元素时,头指针增1. 3.尾指针会出现在头指针之前,由此特性,循环队列在无法预估使用大小时,不宜使用. 4.在每一

  • C语言实现顺序循环队列实例

    目录 一.队列和循环队列基本概念 二.代码实操 总结 一.队列和循环队列基本概念 队列: 和栈相反,队列是一种先进先出(FIFO)的线性表.只允许在一端插入,在另一端删除. 允许插入的叫"队尾"(rear),允许删除的叫"队头"(front). 入队操作:L->rear++;   L->data[L->rear]=x;(需要入队的元素) 出队操作:L->front++;  x=L->data[L->front]; 求队长:队长=(

  • 使用C语言来解决循环队列问题的方法

    题目描述: 大家都知道数据结构里面有一个结构叫做循环队列.顾名思义,这是一个队列,并且是循环的.但是现在,淘气的囧哥给这个循环队列加上了一些规矩,其中有5条指令: (1) Push K, 让元素K进队列. (2) Pop,对头元素出队列. (3) Query K,查找队列中第K个元素,注意K的合法性. (4) Isempty,判断队列是否为空. (5) Isfull,判断队列是否已满. 现在有N行指令,并且告诉你队列大小是M. 输入: 第一行包含两个整数N和M.1<=N,M<=100000.

  • C语言循环队列与用队列实现栈问题解析

    目录 “莫听穿林打叶声,何妨吟啸且徐行” 这里是目录 循环队列题目描述题目链接思路分析代码实现 用队列实现栈题目描述题目链接思路分析代码实现 循环队列 循环队列: 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环循环队列的好处:可以重新利用队列的空间.我们可以利用这个队列之前用过的空间.在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间.但是使用循环队列,我们能使用这些空间去存储新的值. 题目描述 设计你

  • java队列实现方法(顺序队列,链式队列,循环队列)

    双向顺序队列ArrayDeque和双向链式队列LinkedList,JDK已经包含,在此略.ArrayDeque包括顺序栈和顺序队列,LinkedList包含链式栈和链式队列.ArrayDeque和LinkedList都是线程不安全的.PriorityQueue优先队列也在JDK. 1.顺序队列的实现 package lang; import java.io.Serializable; import java.util.Arrays; /** * @ClassName: ArrayQueue *

  • C语言设计前中后队列实例代码

    目录 队列基本概念 1,数组实现  2,链表实现  总结 队列基本概念 队列是最常见的概念,日常生活经常需要排队,仔细观察队列会发现,队列是一种逻辑结构,是一种特殊的线性表.特殊在: 只能在固定的两端操作线性表 只要满足上述条件,那么这种特殊的线性表就会呈现出一种"先进先出"的逻辑,这种逻辑就被称为队列. 由于约定了只能在线性表固定的两端进行操作,于是给队列这种特殊的线性表的插入删除,起个特殊的名称: 队头:可以删除节点的一端 队尾:可以插入节点的一端 入队:将节点插入到队尾之后,函数

  • C语言近万字为你讲透栈和队列

    目录 一.栈与队列以及双端队列的概念 1.1 栈的概念及结构 1.2 队列的概念及结构 1.3 双端队列的概念及结构 二.栈的实现和模拟栈 2.1 实现一个支持动态增长的栈 2.2 数组模拟静态栈 三. 队列的实现(动态)和模拟静态队列 3.1 实现一个支持动态增长的栈 3.2 数组模拟静态队列 四.leetcode-栈实现队列和用队列实现栈 总结 一.栈与队列以及双端队列的概念 1.1 栈的概念及结构 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一

  • Python中栈、队列与优先级队列的实现方法

    前言 栈.队列和优先级队列都是非常基础的数据结构.Python作为一种"编码高效"的语言,对这些基础的数据结构都有比较好的实现.在业务需求开发过程中,不应该重复造轮子,今天就来看看些数据结构都有哪些实现. 0x00 栈(Stack) 栈是一种LIFO(后进先出)的数据结构,有入栈(push).出栈(pop)两种操作,且只能操作栈顶元素. 在Python中有多种可以实现栈的数据结构. 1.list list是Python内置的列表数据结构,它支持栈的特性,有入栈和出栈操作.只不过用lis

  • java数组实现队列及环形队列实现过程解析

    这篇文章主要介绍了java数组实现队列及环形队列实现过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 代码内容 ArrayQueue---用数组实现队列 package com.structure; import java.util.Scanner; /** * @auther::9527 * @Description: 数组模拟队列 * @program: jstl2 * @create: 2019-10-05 08:58 */ pub

  • TCP socket SYN队列和Accept队列区别原理解析

    首先我们必须明白,处于"LISTENING"状态的TCP socket,有两个独立的队列: SYN队列(SYN Queue) Accept队列(Accept Queue) 这两个术语有时也被称为"reqsk_queue","ACK backlog","listen backlog",甚至"TCP backlog",但是这篇文章中我们使用上面两个术语以免造成混淆. SYN队列 SYN队列存储了收到SYN包的连

  • Java面试必备之AQS阻塞队列和条件队列

    一.AQS入队规则 我们仔细分析一下AQS是如何维护阻塞队列的,在独占方式获取资源的时候,是怎么将竞争锁失败的线程丢到阻塞队列中的呢? 我们看看acquire方法,这里首先会调用子类实现的tryAcquire方法尝试修改state,修改失败的话,说明线程竞争锁失败,于是会走到后面的这个条件: 这个addWaiter方法就是将当前线程封装成一个Node.EXCLUSIVE类型的节点,然后丢到阻塞队列中: 第一次还没有阻塞队列的时候,会到enq方法里面,我们仔细看看enq方法 enq()方法中,我们

  • Java 单向队列及环形队列的实现原理

    目录 队列的特点 图解实现过程: 优化解决--环形队列实现思路 环形队列各步骤及各方法实现讲解 最后: 队列的特点 1.可以使用数组和链表两种方式来实现. 2.遵循先入先出(FIFO)的规则,即先进入的数据先出. 3.属于有序列表. 图解实现过程: ​1.定义一个固定长度的数组,长度为maxSize. ​2.设置两个指针first = -1(指向队列第一个数据的前一位,这样保证在添加第一个数据以后头指针为0,和数组的下标一样,且用于操作出队)和last = -1(指向队尾,用于操作入队). ​3

  • Go 实战单队列到优先级队列实现图文示例

    目录 优先级队列概述 为什么需要优先级队列 优先级队列实现原理 01 四个角色 02 队列-消费者模式 03 单队列-单消费者模式实现 3.1 队列的实现 3.2 工作单元--Job的实现 3.3 消费者Worker的实现 04 多队列-单消费者模式 05 多队列-多消费者模式 总结 优先级队列概述 队列,是数据结构中实现先进先出策略的一种数据结构.而优先队列则是带有优先级的队列,即先按优先级分类,然后相同优先级的再 进行排队.优先级高的队列中的元素会优先被消费.如下图所示: 在Go中,可以定义

随机推荐