数据结构之队列的基本操作以及栈和队列的OJ题画图详解

队列

文章目录

  • 队列
    • 队列的概念
    • 队列的实现
      • 文件的创建
      • 队列结构的定义
      • 队列初始化
      • 队列的销毁
      • 队列的打印
      • 队列的插入
      • 队列的删除
      • 队列的大小
      • 取队头元素
      • 取队尾元素
      • 判断是否是空队列
      • 源代码
    • 栈和队列的OJ题
      • 用队列实现栈
      • 设计循环队列
      • 两个栈实现队列

队列的概念

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

入队列:

进行插入操作的一端称为队尾

出队列:

进行删除操作的一端称为队头先进先出

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第1张图片

典型应用

  • 队列实际中要保证公平排队的地方都可以用它

比如在银行我们以前是排队,比如有三个窗口依次排队,但是有的窗口快,有的窗口慢,就有点不公平,后面出现了叫号机,而这个叫号机的系统就是队列的应用,满足了先到先办理业务,很公平,也是队列的特性先进先出的体现。

  • 广度优先遍历

数据结构中图的广度优先遍历也是用队列实现的。

队列的实现

队列的实现既可以用数组的结构实现,也可以用链表的结构实现,那么哪一种更好呢?

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第2张图片

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第3张图片

经过上面的分析,发现链表的结构实现对应更优

那么我们就用链表的结构来实现队列:

首先我们创建文件

文件的创建

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第4张图片

Queue.h对相关头文件的包含,以及实现队列的结构和函数的声明

Queue.c对实现队列操作的函数进行定义

test.c文件进行队列相关函数和单链表功能的测试

队列结构的定义

创建好文件后,我们首先来看队列结构的定义

typedef int QDataType;
//队列的链式结构结点的结构
typedef struct QueueNode
{
	QDataType data;
    struct QueueNode* next;
}QueueNode;

结点的结构

我们知道我们队列的插入数据在队尾插入,而插入需要找尾,我们不妨设一个指向尾的指针,然后将头指针和它封装成一个结构体:

typedef struct Queue
{
    QueueNode* phead;
    QueueNode* ptail;
}Queue;

接下来我们来看队列的下面操作:

//队列初始化
void QueueInit(Queue *pq);
//队列的销毁
void QueueDestory(Queue *pq);
//队列的插入
void QueuePush(Queue *pq,QDataType x);//队尾
//队列的删除
void QueuePop(Queue *pq);//队头
//队列的大小
int QueueSize(Queue *pq);
//取队头元素
QDataType QueueFront(Queue *pq);
//取队尾元素
QDataType QueueBack(Queue *pq);
//判队列是否为空
bool QueueEmpty(Queue *pq);

首先是队列的初始化:

队列初始化

//队列的初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = pq->ptail = NULL;
}

image-20210806222447900

我们调试发现我们已经将phead和ptail置空

队列的销毁

//队列的销毁
void QueueDestory(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->phead;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

我们首先断言一下pq不能为空,然后将phead赋给cur,开始迭代free,free前将cur的next保存下来,最后再将phead和ptail都置为空

队列的打印

//队列的打印
void QueuePrint(Queue* pq)
{
	assert(pq);
	QueueNode* cur = pq->phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

我们也是将phead赋给cur,然后利用cur进行迭代打印数据

队列的插入

//队列的插入
void QueuePush(Queue* pq, QDataType x)//队尾
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return;
	}
	if (pq->phead == NULL)//没有结点时
	{
		pq->phead = pq->ptail = newnode;
	}
	else//有结点时
	{
		pq->ptail->next = newnode;
		pq->ptail = newnode;
	}
}

因为我们插入元素只有这里能用到,所以我们就不将它写成和我们之前写的单链表那样单独写一个函数创建结点,我们开辟好一个结点,当队列没有结点时,我们将newnode赋给phead和ptail,有结点时我们直接将newnode赋给ptail的next,将newnode更新成尾

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第5张图片

可以看到我们插入成功了

队列的删除

//队列的删除
void QueuePop(Queue* pq)//队头
{
	assert(pq);
	assert(!QueueEmpty(pq));//队列不为空
	if (pq->phead->next == NULL)//只有一个结点时
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	QueueNode* next = pq->phead->next;
	free(pq->phead);
	pq->phead = next;
	//当队列中只剩下一个结点时,删除只是将phead置NULL了,
	//但是ptail并没有置空,此时它是野指针,故我们前面需考虑只剩一个结点时的情况
}

当队列中只剩下一个结点时,删除只是将phead置NULL了,但是ptail并没有置空,此时它是野指针,故我们前面需考虑只剩一个结点时的情况。当只有一个结点时,我们free phead,然后将phead和ptail都置为空

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第6张图片

上图是测试结果

队列的大小

//队列的大小
int QueueSize(Queue* pq)
{
	assert(pq);
	int size = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{
		size++;
		cur = cur->next;
	}
	return size;
}

取队头元素

//取队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->phead->data;
}

断言队列不能为空,phead就是队头,返回它的数据。

取队尾元素

//取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));
	return pq->ptail->data;
}

ptail是尾,返回它的数据

判断是否是空队列

//判断是否是空队列
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->phead == NULL && pq->ptail == NULL;
}

phead和ptail为空时,队列为空

链表,栈,队列的操作实现时,关于函数传参传什么的问题:

  • 传二级指针(头指针可以在函数里面解引用改变)

  • 返回值(接收返回值改变)

  • 带哨兵位的头结点(不会改变头指针)

  • 结构体包一起(用结构体指针改变)

下面是队列实现的源代码:

源代码

Queen.h

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

typedef struct Queue
{
    QueueNode* phead;
    QueueNode* ptail;
}Queue;

void QueueInit(Queue *pq);
void QueueDestory(Queue *pq);
void QueuePush(Queue *pq,QDataType x);//队尾
void QueuePop(Queue *pq);//队头
int QueueSize(Queue *pq);
QDataType QueueFront(Queue *pq);
QDataType QueueBack(Queue *pq);
bool QueueEmpty(Queue *pq);

Queen.c

void QueueInit(Queue *pq)
{
    assert(pq);
    pq->phead = pq->ptail = NULL;
    
}
void QueueDestory(Queue *pq)
{
    assert(pq);

    QueueNode* cur = pq->phead;
    while(cur)
    {
        QueueNode* next=cur->next;
        free(cur);
        cur=next;
    }
    pq->phead=pq->ptail=NULL;
}
void QueuePush(Queue *pq,QDataType x)//队尾
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if(newnode==NULL)
    {
        perror("malloc");
        return;
    }
    newnode->data=x;
    newnode->next=NULL;
    
    if(pq->ptail==NULL)
    {
        pq->phead=pq->ptail=newnode;
    }

    else
    {
        pq->ptail->next = newnode;
        pq->ptail = newnode;
    }
    
}
bool QueueEmpty(Queue *pq)
{
    assert(pq);
    return pq->ptail==NULL && pq->phead==NULL;
}
void QueuePop(Queue *pq)//队头
{
    assert(pq);
    //删数据
    assert(!QueueEmpty(pq));
    if(pq->phead->next==NULL)
    {
        free(pq->phead);
        pq->phead=pq->ptail=NULL;
    }
    else
    {
        QueueNode* next=pq->phead->next;
    	free(pq->phead);
    	pq->phead=next;
    //如果被删空了,ptail指向的结点已经free了 但是它没有置空
    //ptail是个野指针
    }
}
int QueueSize(Queue *pq)
{
    assert(pq);
    //如果频繁调用这个接口函数,将size也放进Queue结构体中
    QueueNode* cur = pq->phead;
    int size=0;
    while(cur)
    {
        size++;
        cur=cur->next;
    }
    return size;
}
QDataType QueueFront(Queue *pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->phead->data;
}
QDataType QueueBack(Queue *pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->ptail->data;
}

test.c

int main()
{
    Quenu q;
    QueueInit(&q);
    QueuePush(&q,1);
    QueuePush(&q,2);
    QueuePush(&q,3);
    QueuePush(&q,4);
    
    return 0;
}

栈和队列的OJ题

用队列实现栈

题目描述:

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

实现 MyStack 类:

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。

题目来源:用队列实现栈

思路:

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第7张图片

我们在用两个队列实现栈,队列是先进先出,而栈是先进后出,我们现在进去的顺序是1、2、3、4,而要实现栈的功能,我们出栈则应该要4先出,那么怎么样才能让4出呢?我们接着往下看思路

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第8张图片

那么我们入数据怎么入呢?

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第9张图片

入数据在不为空的队列入,我们想一想栈是后进先出,那么下次出数据操作,我们按照上面的操作,不就是出的5嘛,所以我们入数据在不为空的队列

我们来总结一下思路:

  • 一个队列有数据,一个队列没数据
  • 入数据在不为空的那个队列入
  • 出数据,把不为空的队列的前n-1个导入到空队列中,pop掉最后剩下的一个数据

代码如下:

//栈的结构--两个队列
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;

/** Initialize your data structure here. */

//栈的创建
MyStack* myStackCreate() {
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    if(pst==NULL)
    {
        perror("malloc MyStack");
        return NULL;
    }
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    
    return pst;
}

/** Push element x onto stack. */
//进栈
void myStackPush(MyStack* obj, int x) {
    assert(obj);
    /*Queue* emptyQ=&obj->q1;//假设q1为空
    Queue* nonemptyQ=&obj->q2;//假设q2不为空
    if(!QueueEmpty(&obj->q1))//如果q1不为空则
    {
        emptyQ=&obj->q2;
        nonemptyQ=&obj->q1;
    }
    QueuePush(nonemptyQ,x);//在不为空的队列里入数据*/
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1,x);
    }
    else
    {
        QueuePush(&obj->q2,x);

    }

}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}
/** Removes the element on top of the stack and returns that element. */
//出栈
int myStackPop(MyStack* obj) {
    assert(obj);
    
    Queue* emptyQ=&obj->q1;//假设q1为空
    Queue* nonemptyQ=&obj->q2;//假设q2不为空
    if(!QueueEmpty(&obj->q1))//如果q1不为空则
    {
        emptyQ=&obj->q2;
        nonemptyQ=&obj->q1;
    }
    while(QueueSize(nonemptyQ)>1)
    {
        QueuePush(emptyQ,QueueFront(nonemptyQ));//将队列的队头入到空队列中
        QueuePop(nonemptyQ);//pop数据
    }
    int front = QueueFront(nonemptyQ);
    QueuePop(nonemptyQ);

    return front;
}

/** Get the top element. */
int myStackTop(MyStack* obj) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    else
    {
        return QueueBack(&obj->q2);
    }
}

/** Returns whether the stack is empty. */


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

设计循环队列

题目描述:

设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

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

题目来源:设计循环队列

在看完题目之后,我们可以知道它是这样的结构:

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第10张图片

我们这样设计:front和rear分别指向头和尾的下一个元素,循环队列的结构既可以用链表结构也可以用顺序表结构,链表结构最后一个元素的next指向头,顺序表等到rear到达边界时,让他回到下标为0的地方,这样我们的顺序表和链表达到了循环的目的。

那么怎么插入数据和删除数据呢?

插入数据:

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第11张图片

可以看到插入数据将rear后移,当front等于rear时,队列为满

删除数据:

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第12张图片

删除数据我们直接让front移动,数据不用管,front和rear直接的数据才是有效数据,可以看到删除数据将front后移,当front等于rear时,队列为空

那么我们来看这样一个问题:

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第13张图片

那么这里我们考虑到将空间加一个单位:

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第14张图片

多增加一个单位空间,如上图顺序表中,队列的长度为7,但是我们实际最多只存储6个数据,当rear的下一个存储空间等于front时,我们就说队列是满的

我们假设k是实际存储的数据个数,则只要(rear+1)%(k+1)==front时,队列是满的,那么front==rear时,队列是空的。

下面我们开始写代码,我们这道题用顺序表结构来写,这里我建议大家用顺序表写,因为顺序表缓存利用率高,而且不用一直开辟节点。

首先我们创建循环队列的结构体:

typedef struct{
  	int *a;//指向动态开辟的内存的指针,这块内存用来存储数据
    int front;//队头的下标
    int rear;//队尾的下一个元素的下标
    int k;//数据的个数
}MyCircularQueue;

我们创建了指向动态开辟的内存的指针a,队头的下标,队尾的下一个元素的下标,数据的个数k

接下来我们来看循环队列的创建初始化函数:

MyCircularQueue* myCircularQueueCreate(int k) {
    MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int*)malloc((k+1)*sizeof(int));//需要开辟k+1个存储数据的空间,实际存储k个
    q->front=q->rear=0;
    q->k=k;
    
    return q;
}

我们先对循环队列开辟一块空间,需要开辟k+1个存储数据的空间,实际存储k个,然后初始化循环队列。

接下来是判空函数:

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    assert(obj);
    return obj->front==obj->rear;
}

我们前面已经提到了,当front和rear相等时,队列为空

接下来是判满函数:

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    assert(obj);
    return (obj->rear+1)%(obj->k+1)==obj->front;
}

判满我们前面也用图片解释过了,当rear+1=front时是满的,但是当rear到达顺序表末尾时,此时rear+1我们需要回到顺序表下标为0的地方,故我们这里写成(obj->rear+1)%(obj->k+1)==obj->front;,此时就满足条件了。

接下来是进队列操作:

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    assert(obj);
    //判满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->rear] = value;
    obj->rear++;
    if(obj->rear==obj->k+1)
    {
        obj->rear=0;
    }
    //obj->rear %= (obj->k+1);
    return true;
}

进队列操作,我们再前面动态展示进数据,其实就是将数据放在rear下标处,然后rear++,需要注意的是rear到达边界时的处理情况rear等于k+1时我们需要让他回到起点

接下来我们来看出队列的函数:

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

我们前面动态也演示过删除数据,即将front++即可,注意还需要考虑边界的情况,front等于k+1时我们需要让他回到起点

接下来我们来看取队头的操作

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

首先判断是不是空,依照题意要求,为空需要返回-1,最后返回头的下标front的数据

接下来我们来看取队尾的操作

int myCircularQueueRear(MyCircularQueue* obj) 
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int prevrear=obj->rear-1;
    if(obj->rear==0)
    {
        prevrear = obj->k;
    }
    return obj->a[prevrear];
}

首先判断是不是空,依照题意要求,为空需要返回-1,最后返回尾的数据,这里要注意rear是尾的下一个位置的下标,故这里需要-1,需要注意的是当rear等于0时,队尾元素下标并不是0-1,而它的下标为k,这里需要特别处理,总而言之还是边界的问题

下面我们看最后一个销毁函数:

void myCircularQueueFree(MyCircularQueue* obj) 
{
    assert(obj);
    if(obj->a)
    {
        free(obj->a);
        obj->a=NULL;
    }
    free(obj);
    obj=NULL;
}

这道题的完整代码:

typedef struct{
  	int *a;//指向动态开辟的内存的指针,这块内存用来存储数据
    int front;//队头的下标
    int rear;//队尾的下一个元素的下标
    int k;//数据的个数
}MyCircularQueue;

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

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    assert(obj);
    return obj->front==obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    assert(obj);
    return (obj->rear+1)%(obj->k+1)==obj->front;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    assert(obj);
    //判满
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }
    obj->a[obj->rear] = value;
    obj->rear++;
    if(obj->rear==obj->k+1)
    {
        obj->rear=0;
    }
    //obj->rear %= (obj->k+1);
    return true;
}

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

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

int myCircularQueueRear(MyCircularQueue* obj) 
{
    assert(obj);
    if(myCircularQueueIsEmpty(obj))
    {
        return -1;
    }
    int prevrear=obj->rear-1;
    if(obj->rear==0)
    {
        prevrear = obj->k;
    }
    return obj->a[prevrear];
}

void myCircularQueueFree(MyCircularQueue* obj) 
{
    assert(obj);
    if(obj->a)
    {
        free(obj->a);
        obj->a=NULL;
    }
    free(obj);
    obj=NULL;
}

两个栈实现队列

题目描述:

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty):

实现 MyQueue 类:

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false

题目来源:两个栈实现队列

思路:

前面我们是用两个队列实现栈,这里是两个栈实现队列,那么想一想我们怎么实现呢?

数据结构之队列的基本操作以及栈和队列的OJ题画图详解_第15张图片

栈是先进后出,队列是先进先出,我们发现我们将栈1的数据依次出栈1,进栈2,栈2的出栈顺序就对应着队列的出队顺序了,所以我们入数据就在栈1,出数据就在栈2

我们不妨对栈1取名为pushst,栈2取名为popst

那么我们的思路为:

  • 入数据进pushst
  • 出数据看popst是不是空,如果为空,先把pushst的数据倒过来,然后出数据,如果不为空直接出数据

代码如下:

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

/** Initialize your data structure here. */

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

    return q;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    //
    StackPush(&obj->pushst,x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    assert(obj);
    //
    /*if(StackEmpty(&obj->popst))//如果popst为空,则在pushst中将数据倒过来
    {
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    int top = StackTop(&obj->popst);
    StackPop(&obj->popst);
    return top;*/
    int front = myQueuePeek(obj);//可以复用取队头的函数
    StackPop(&obj->popst);
    return front;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(StackEmpty(&obj->popst))//如果popst为空,则在pushst中将数据倒过来
    {
        while(!StackEmpty(&obj->pushst))
        {
            StackPush(&obj->popst,StackTop(&obj->pushst));
            StackPop(&obj->pushst);
        }
    }
    return StackTop(&obj->popst);
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {

    assert(obj);
    return StackEmpty(&obj->pushst)&&StackEmpty(&obj->popst);
}

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

以上就是队列概念与实现以及栈和队列的OJ题讲解,如果觉得有帮助,点个赞吧,欢迎大家互相学习

你可能感兴趣的