C语言栈与队列面试题详解

第C语言栈与队列面试题详解MyQueue*myQueueCreate(){

MyQueue*obj=(MyQueue*)malloc(sizeof(MyQueue));//申请队列类型

assert(obj);

StackInit(obj-pushST);//初始化pushST

StackInit(obj-popST);//初始化popST

returnobj;

voidmyQueuePush(MyQueue*obj,intx){

assert(obj);

StackPush(obj-pushST,x);//不管有没有数据，都插入

intmyQueuePop(MyQueue*obj){

assert(obj);

if(StackEmpty(obj-popST))//如果popST数据为空，要从pushST里导入数据才能删除

while(!StackEmpty(obj-pushST))//pushST数据不为空，就一直向popST里导入数据

StackPush(obj-popST,StackTop(obj-pushST));//把pushST栈顶数据导到popST里

StackPop(obj-pushST);//导完后把pushST栈顶元素删掉，方便后续继续导

intfront=StackTop(obj-popST);//记录popST栈顶元素

StackPop(obj-popST);//删除popST栈顶元素，实现队列先进先出

returnfront;//返回栈顶数据

//取队头数据

intmyQueuePeek(MyQueue*obj){

assert(obj);

//如果popST数据为空，要从pushST里导入数据才能取到队头数据

if(StackEmpty(obj-popST))

while(!StackEmpty(obj-pushST))//pushST数据不为空，就一直向popST里导入数据

StackPush(obj-popST,StackTop(obj-pushST));//把pushST栈顶数据导到popST里

StackPop(obj-pushST);//导完后把pushST栈顶元素删掉，方便后续继续导

returnStackTop(obj-popST);//直接返回栈顶元素

boolmyQueueEmpty(MyQueue*obj){

returnStackEmpty(obj-pushST)StackEmpty(obj-popST);

voidmyQueueFree(MyQueue*obj){

assert(obj);

StackDestory(obj-pushST);

StackDestory(obj-popST);

free(obj);

}

4、设计循环队列

链接直达：

设计循环队列

题目：

思路：

此题可以用数组实现，也可以用链表实现，但其实是用数组更加方便些。

数组：

假设队头front和队尾tail都指向第一个数据，在队尾插入数据，tail随着数据的插入跟着移动，tail始终为最后一个数据的下一个位置。删除数据只需要将队头front往后挪即可，不需要按照之前队列的pop一样删完还挪动数据，因为是循环链表，且数据是可以重复利用的。

这样分析下来再加上画图看似没有什么缺陷，但是存在两个问题？

什么情况下数组为空？什么情况下数组满了？

问题1：

当tail=front时数组为空，看似没什么问题，但相等又要分两种情况。先画个图：

由上图得知，在情况一下，数组里确实是一个数据也没有，并且tail也是等于front的，满足数组为空的条件，但是在情况二下，数组的数据全满，此时的tail和front同样是相等的，这里数组不为空了，而是全满，由此可见，是存在问题的。

解决方案：

这里我们可以多开一个空间，不存放数据，只是用来分别数组为空或满。原理如下：当数组长度为4时，也就是说实际能存放3个有效数据，另外一个空间用来判断空或满，此时判断空或满的条件如下：

front==tail时是空tail下一个位置是front时，就是满

代码如下：

typedefstruct{

int*a;//用数组模拟环形队列

intfront;//队头

inttail;//队尾

intk;//表示存的数据长度为k

}MyCircularQueue;

boolmyCircularQueueIsFull(MyCircularQueue*obj);//前置声明

boolmyCircularQueueIsEmpty(MyCircularQueue*obj);//前置声明

MyCircularQueue*myCircularQueueCreate(intk){

MyCircularQueue*obj=(MyCircularQueue*)malloc(sizeof(MyCircularQueue));//创建环形链表结构

assert(obj);

obj-a=(int*)malloc(sizeof(int)*(k+1));//多开一个空间，便于后续区分空或满

obj-front=obj-tail=0;

obj-k=k;//队列存储有效数据长度为k

returnobj;

boolmyCircularQueueEnQueue(MyCircularQueue*obj,intvalue){

if(myCircularQueueIsFull(obj))

returnfalse;//队列已满，不能插入数据

obj-a[obj-tail]=value;//赋值

if(obj-tail==obj-k)

obj-tail=0;//当tail走到尾端

else

obj-tail++;

returntrue;

boolmyCircularQueueDeQueue(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

returnfalse;//队列为空，不能删除

if(obj-front==obj-k)

obj-front=0;//当front走到尾端

else

obj-front++;

returntrue;

intmyCircularQueueFront(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

return-1;//队列为空，取不了

returnobj-a[obj-front];//返回队头

intmyCircularQueueRear(MyCircularQueue*obj){

if(myCircularQueueIsEmpty(obj))

return-1;//队列为空，取不了

if(obj-tail==0)

returnobj-a[obj-//tail为0，队尾在长度的最后一个位置

else

returnobj-a[obj-tail-1];

boolmyCircularQueueIsEmpty(MyCircularQueue*obj){

returnobj-front==obj-tail;//front==tail时为空

boolmyCircularQueueIsFull(MyCircularQueue*obj){

if(obj-tail==obj-kobj-front==0)

retur