用两个栈模拟实现队列

2017-05-01 18:29 阅读 667 次 评论 0 条

队列是一种非常重要的数据结构,和栈不同的是,队列的特点是先进先出,而栈是先进后出,这也就固定了队列具有双向开口,而栈仅有一个开口进行操作。今天我们使用栈的特性来模拟实现队列的基本操作。

设计要求

用两个栈实现一个队列。队列的声明如下,实现它的两个函数appendTaildeleteHead,分别完成在队列尾部插入节点,和在队列头部删除节点的功能。

设计思路

此题的意图在于用两个"先进后出"的栈实现一个"先进先出"的队列

①我们暂且设两个栈分别为S1,S2,入栈时栈与队列都是栈顶(尾部)入栈,因此不需要改变,直接将元素压入S1中。

②然后将S1中的元素逐个出栈压入S2中,直到S1为空,现在S2栈内元素的顺序恰好与S1之前的顺序相反,当我们进行删除操作时,栈顶元素恰好是最先压入S1中的元素。

源代码及注释

版权声明:本文著作权归原作者所有,欢迎分享本文,谢谢支持!
转载请注明:用两个栈模拟实现队列 | 术与道的分享
分类:编程素养 标签:, ,
1024do.com导航_术与道导航平台

发表评论


表情