最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

Python栈和队列_用两个栈实现一个队列

XAMPP案例 admin 61浏览 0评论

CA0074

【用两个栈实现一个队列】

题目描述

用两个栈来实现一个队列,完成队列的push和pop操作。队列中的元素为int类型。

思路:

首先明白栈和队列这两种不同的数据结构特点 ,栈中元素:先进后出原则,把栈想象成一个桶,先压进去的元素在桶底(栈底),后压进去的元素在桶顶(栈顶);队列元素:先进先出,像排队一样,先进来的元素优先离开。】

1) 初始化两个栈,stack1和stack2;

2) push操作(数据压入)时,stack1用来存放压入的数据;

3) 想要调用pop操作(即数据弹出),分两种情况:

    a.如果stack2不为空,则直接弹出其栈顶元素;

    b.若stack2为空,先把stack1中现有的所有的数据全部弹出,依次存放进stack2, 再从stack2中弹出栈顶数据,即完成pop操作

# -*- coding:utf-8 -*-class Solution:    def __init__(self):        self.stack1=[]        self.stack2=[]    def push(self, node):        self.stack1.append(node)    def pop(self):        if self.stack2!=[]:            return self.stack2.pop()        else:            while self.stack1 :                q=self.stack1.pop()                self.stack2.append(q)            if self.stack2==[]:                return 'All data has been popped'            return self.stack2.pop()

测试:

s=Solution()print('队列push 2')s.push(2)print('队列push 3')s.push(3)
print('队列pop操作:',s.pop())
print('队列push 4')s.push(4)print('队列push 5')s.push(5)
print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())# result:队列push 2队列push 3队列pop操作:2队列push 4队列push 5队列pop操作:3队列pop操作: 4队列pop操作: 5队列pop操作: Now all data has been popped

可以看到push数字2,3,4,5,即入队顺序是2,3,4,5,调用pop后出队顺序也是2,3,4,5,push和pop操作的顺序不影响先入先出的结果,即用两个栈完成了一个队列先入先出的功能。

【用两个栈实现一个队列】

题目描述

用两个栈来实现一个队列,完成队列的push和pop操作。队列中的元素为int类型。

思路:

首先明白栈和队列这两种不同的数据结构特点 ,栈中元素:先进后出原则,把栈想象成一个桶,先压进去的元素在桶底(栈底),后压进去的元素在桶顶(栈顶);队列元素:先进先出,像排队一样,先进来的元素优先离开。】

1) 初始化两个栈,stack1和stack2;

2) push操作(数据压入)时,stack1用来存放压入的数据;

3) 想要调用pop操作(即数据弹出),分两种情况:

    a.如果stack2不为空,则直接弹出其栈顶元素;

    b.若stack2为空,先把stack1中现有的所有的数据全部弹出,依次存放进stack2, 再从stack2中弹出栈顶数据,即完成pop操作

# -*- coding:utf-8 -*-class Solution:    def __init__(self):        self.stack1=[]        self.stack2=[]    def push(self, node):        self.stack1.append(node)    def pop(self):        if self.stack2!=[]:            return self.stack2.pop()        else:            while self.stack1 :                q=self.stack1.pop()                self.stack2.append(q)            if self.stack2==[]:                return 'All data has been popped'            return self.stack2.pop()

测试:

s=Solution()print('队列push 2')s.push(2)print('队列push 3')s.push(3)
print('队列pop操作:',s.pop())
print('队列push 4')s.push(4)print('队列push 5')s.push(5)
print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())print('队列pop操作:',s.pop())# result:队列push 2队列push 3队列pop操作:2队列push 4队列push 5队列pop操作:3队列pop操作: 4队列pop操作: 5队列pop操作: Now all data has been popped

可以看到push数字2,3,4,5,即入队顺序是2,3,4,5,调用pop后出队顺序也是2,3,4,5,push和pop操作的顺序不影响先入先出的结果,即用两个栈完成了一个队列先入先出的功能。

转载请注明:XAMPP中文组官网 » Python栈和队列_用两个栈实现一个队列