南宁武鸣区建设局网站,上海58同城招聘网最新招聘,最美logo图案大全,深圳网络公司推广公司全文目录引言用栈实现队列题目介绍思路简述实现栈的部分队列的部分创建队列判断队列是否为空在队列尾入在队列头出访问队头元素释放队列总结引言
在上一篇文章中#xff0c;我们了解了用两个队列实现栈。在这篇问章中将继续介绍用两个栈实现队列的OJ练习#xff1a; 用栈实现…
全文目录引言用栈实现队列题目介绍思路简述实现栈的部分队列的部分创建队列判断队列是否为空在队列尾入在队列头出访问队头元素释放队列总结引言
在上一篇文章中我们了解了用两个队列实现栈。在这篇问章中将继续介绍用两个栈实现队列的OJ练习 用栈实现队列OJ链接
在本文中可能会需要借鉴到栈与队列的实现 戳我看栈详解哦 戳我看队列详解哦
用栈实现队列
题目介绍 题目描述很简单 通过两个栈实现队列存储数据的特点即先进先出
我们需要实现基本的队列操作push、pop、top、empty、free void push(int x) 将元素 x 推到队列的末尾 int pop() 从队列的开头移除并返回元素 int peek() 返回队列开头的元素 bool empty() 如果队列为空返回 true 否则返回 false。
思路简述
与上一道题相同这道题的难点同样在于结构 如何实现pop时移除栈底的元素。由于栈是先进后出所以栈底的元素是无法直接移除的。
我们就可以使用第二个栈将栈中的元素依次取出存入第二个栈中。由于栈是先进后出所以当将一个栈中的元素依次取出放进另一个栈中时数据的顺序就会颠倒这时在栈顶的元素就是最先入栈的元素将这个元素移除即可 也就是说这个栈中栈顶的元素永远是最先入栈的元素所以在这个栈中的元素没有全部移除之前是不能在这个栈中再插入元素了只能在原来的那个栈中插入 我们发现用两个栈来实现队列时有一个栈只用于插入元素有一个栈只用于移除元素所以我们可以直接将前一个栈命名为push后一个命名为pop 如果pop栈为空又需要移除元素时才需要将push栈中的元素倒到pop栈中
实现
栈的部分
在用两个栈实现队列之前我们首先需要实现栈的接口。在需要用到栈的操作时直接复用即可。于栈的实现这里就不再赘述了在前面的文章中已经详细的介绍过了。这里直接把前面实现过的栈的各种接口拷贝过来包括用于定义队列的结构体
typedef int STDataType;typedef struct Stack //表示栈
{STDataType* a;int top;int capacity;
}ST;//栈的部分
//初始化栈
void STInit(ST* ps)
{assert(ps);ps-a (STDataType*)malloc(10 * sizeof(STDataType));assert(ps);ps-capacity 10;ps-top 0;
}
//判断栈是否为空
bool STEmpty(ST* ps)
{assert(ps);if (ps-top){return 0;}else{return 1;}
}
//压栈
void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity){STDataType* ptr (STDataType*)realloc(ps-a, (ps-capacity 10) * sizeof(STDataType));assert(ptr);ps-a ptr;ps-capacity 10;}ps-a[ps-top] x;ps-top;
}
//出栈
void STPop(ST* ps)
{assert(ps STEmpty(ps) 0);ps-top--;
}
//计算栈中元素个数
int STSize(ST* ps)
{assert(ps);return ps-top;
}
//访问栈顶元素
STDataType STTop(ST* ps)
{assert(ps STEmpty(ps) 0);return ps-a[ps-top - 1];
}
//销毁栈
void STDestroy(ST* ps)
{assert(ps);free(ps-a);ps-capacity 0;ps-top 0;ps-a NULL;
}队列的部分
有了栈的实现后我们首先应该创建两个栈pushst与popst用于插入与移除元素。并将这两个栈存放到一个结构体中方便管理
typedef struct //表示实现队列的两个栈
{ST pushst;ST popst;
} MyQueue;创建队列
创建队列时可以直接为前面声明的用于存放两个栈的结构体类型MyQueue动态开辟一块空间然后再分别复用STInit初始化其中的两个栈即可
//创建队列
MyQueue* myQueueCreate()
{MyQueue* pmq (MyQueue*)malloc(sizeof(MyQueue));assert(pmq);STInit(pmq-pushst);STInit(pmq-popst);return pmq;
}判断队列是否为空
队列为空即两个栈均为空。 所以我们直接复用判断栈是否为空函数STEmpty当两个栈均为空即两个函数的返回值均为真时返回真否则返回假
//判断队列是否为空若为空返回true非空返回false
bool myQueueEmpty(MyQueue* obj)
{assert(obj);if (STEmpty(obj-pushst) STEmpty(obj-popst))//当两个队列全为空即全为非0才为空返回1{return true;}else{return false;}
}在队列尾入
任何时候插入元素时在pushst栈中插入即可 //在队列尾入
void myQueuePush(MyQueue* obj, int x)
{assert(obj);STPush(obj-pushst, x);
}在队列头出
在队列头出时永远从popst的栈顶移除即可移除栈顶的元素时复用STPop函数即可 但是当popst为空时就需要将pushst栈中的元素全部依次移动到popst栈中我们可以通过复用STPush与STTop函数将pushst栈顶的元素插入到popst中然后再STPop移除pushst栈顶的元素即可。然后再pop掉popst的栈顶元素
//从队列头出
int myQueuePop(MyQueue* obj)
{assert(obj myQueueEmpty(obj) 0);STDataType ret 0;if (STEmpty(obj-popst))//当pop栈为空时才将push栈中的元素转移过去{while (STEmpty(obj-pushst) 0){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}ret STTop(obj-popst);STPop(obj-popst);return ret;
}访问队头元素
访问队头元素时只需要复用STTop函数访问popst栈顶的元素即可 但是当popst栈为空时就需要将pushst中的元素全部倒过去后再访问
//返回队列开头的元素
int myQueuePeek(MyQueue* obj)
{assert(obj myQueueEmpty(obj) 0);//当pop为空时只能转移后访问它pop非空时可以直接访问pop的栈顶元素if (STEmpty(obj-popst)){while (STEmpty(obj-pushst) 0){STPush(obj-popst, STTop(obj-pushst));STPop(obj-pushst);}}return STTop(obj-popst);
}释放队列
释放队列时分别释放两个栈即可。 当然动态开辟的MyQueue型结构体也需要被释放
//释放队列
void myQueueFree(MyQueue* obj)
{STDestroy(obj-pushst);STDestroy(obj-popst);free(obj);
}总结
到此关于用两个栈实现队列的题目就介绍完了相信通过这两道题目大家对于栈与队列的结构都有了更好的理解 下一篇文章中将会介绍循环队列的实现欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
