循环队列 + 用队列实现栈 ——纯C

简介: 循环队列 + 用队列实现栈 ——纯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
0
0
0
1
分享
相关文章
java实现队列数据结构代码详解
本文详细解析了Java中队列数据结构的实现,包括队列的基本概念、应用场景及代码实现。队列是一种遵循“先进先出”原则的线性结构,支持在队尾插入和队头删除操作。文章介绍了顺序队列与链式队列,并重点分析了循环队列的实现方式以解决溢出问题。通过具体代码示例(如`enqueue`入队和`dequeue`出队),展示了队列的操作逻辑,帮助读者深入理解其工作机制。
111 1
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
24 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。
|
6月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
301 77
|
5月前
|
STL——栈和队列和优先队列
通过以上对栈、队列和优先队列的详细解释和示例,希望能帮助读者更好地理解和应用这些重要的数据结构。
82 11
☀☀☀☀☀☀☀有关栈和队列应用的oj题讲解☼☼☼☼☼☼☼
### 简介 本文介绍了三种数据结构的实现方法:用两个队列实现栈、用两个栈实现队列以及设计循环队列。具体思路如下: 1. **用两个队列实现栈**: - 插入元素时,选择非空队列进行插入。 - 移除栈顶元素时,将非空队列中的元素依次转移到另一个队列,直到只剩下一个元素,然后弹出该元素。 - 判空条件为两个队列均为空。 2. **用两个栈实现队列**: - 插入元素时,选择非空栈进行插入。 - 移除队首元素时,将非空栈中的元素依次转移到另一个栈,再将这些元素重新放回原栈以保持顺序。 - 判空条件为两个栈均为空。
|
6月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
222 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
6月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
165 7
|
8月前
|
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
756 9
|
8月前
|
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
186 59
登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问