关于算法:剑指offer5使用2个栈实现队列JavaPython

应用 2 个栈实现队列

1. 题目形容

用两个栈来实现一个队列，实现队列的 Push 和 Pop 操作。队列中的元素为 int 类型。

1. 示例

无 须要先明确 2 点：队列是先进先出的，栈是先进后出的

1. 解题思路

须要两个栈 Stack1 和 Stack2，push 的时候间接 push 进 Stack1。pop 须要判断 Stack1 和 Stack2 中元素的状况，Stack1 空的话，间接从 Stack2 pop，Stack1 不空的话，把 Stack1 的元素 push 进入 Stack2，而后 pop Stack2 的值。

1.push: 间接 push 进 stack1。须要 pop 全副 stack2，才开始将 stack1 元素放进 stack2 中

2.pop：if stack2 不为空，间接 pop stack2；if stack2 为空，须要将 stack1 元素全副放入 stack2 中，而后 pop

1. Java 实现

import java.util.Stack;
 
public class Solution {Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {stack1.push(node);
        
    }
    
    public int pop() {if (stack1.isEmpty() && stack2.isEmpty()){return -1;}
        
        if (stack2.isEmpty()){while (!stack1.isEmpty()){stack2.push(stack1.pop());
            }
        }
        return stack2.pop();}
}

1. Python 实现

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        # write code here
        self.stack1.append(node)
        
    def pop(self):
        # return xx
        if not self.stack1 and not self.stack2: 
            return 
        
        if not self.stack2: #如果 stack2 为空
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()   

如果您感觉本文有用，请点个“在看”