LintCode 492 [Implement Queue by

原题

实现一个队列的操作

样例

enqueue(1)
enqueue(2)
enqueue(3)
dequeue() # return 1
enqueue(4)
dequeue() # return 2

解题思路

• 简单基础的一道题，用链表实现列队
• 注意，dequeue的时候如果是下面这种情况，head指向dummyNode，tail指向5。把5删除之后要记得将tail重新指向head所指向的node

DummyNode -> 5 -> Null

完整代码

class Node():
    def __init__(self, _val):
        self.next = None
        self.val = _val
        
class MyQueue(object):

    def __init__(self):
        # do some intialize if necessary
        self.head = Node(0)
        self.tail = self.head
        self.size = 0

    # @param {int} item an integer
    # @return nothing
    def enqueue(self, item):
        # Write yout code here
        self.tail.next = Node(item)
        self.tail = self.tail.next
        self.size += 1

    # @return an integer
    def dequeue(self):
        # Write your code here
        res = self.head.next.val
        self.head.next = self.head.next.next
        self.size -= 1
        if self.size == 0:
            self.tail = self.head
        return res