剑指Offer--(6)用两个栈实现队列

title: 剑指Offer--(6)用两个栈实现队列

categories: 算法与数据结构

tags: 数据结构

题目描述

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

概念复习与解题思路

1. 队列：queue，是先进先出（FIFO,First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作。队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加。

2. 堆栈：由于堆栈数据结构只允许在一端进行操作，因而按照后进先出（LIFO, Last In First Out）的原理运作。堆栈数据结构使用两种基本操作：推入（压栈，push）和弹出（弹栈，pop）：

   • 推入：将数据放入堆栈的顶端（数组形式或串列形式），堆栈顶端top指针加一。
   • 弹出：将顶端数据数据输出（回传），堆栈顶端数据减一。

# -*- 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 self.stack2:
            return self.stack2.pop()
        elif not self.stack1:
            return None
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

其他解法

思路类似，表达上更简洁一些。

# -*- 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 self.stack2 == []:
            while self.stack1:
                a = self.stack1.pop()
                self.stack2.append(a)
        return self.stack2.pop()