乐趣区

关于算法:剑指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()   

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

退出移动版