python数据结构之栈、队列与堆

1. 栈与队列的基础知识

栈(stacks)是一种只能通过访问其一端来实现数据存储与检索的线性数据结构，具有后进先出(last in first out，LIFO)的特征
队列(queue)是一种具有先进先出特征的线性数据结构，元素的增加只能在一端进行，元素的删除只能在另一端进行。能够增加元素的队列一端称为队尾，可以删除元素的队列一端则称为队首。python库from collections import deque可以实现，popleft()。

2. 使用队列实现栈 (LeetCode 225 Implement Stack using Queues)

2.1题目

Implement the following operations of a stack using queues.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
empty() – Return whether the stack is empty.
Notes:
You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).

2.2思路

栈是后进先出，队列是先进先出，队列在python中要使用collections.dequeue()
要用队列表示栈，则在元素入栈时对栈元素的顺序进行调整，将最后元素之前的元素按顺序移动到最后一个元素的后面，使最后一个进入的元素位于队列的前面。

2.3代码

class MyStack(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.stack = collections.deque([])


    def push(self, x):
        """
        self.stack = []
        Push element x onto stack.
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        q = self.stack
        for i in range(len(q) - 1):
            q.append(q.popleft())


    def pop(self):
        """
        Removes the element on top of the stack and returns that element.
        :rtype: int
        """
        return self.stack.popleft()


    def top(self):
        """
        Get the top element.
        :rtype: int
        """
        return self.stack[0]

    def empty(self):
        """
        Returns whether the stack is empty.
        :rtype: bool
        """
        if len(self.stack) == 0:
            return True
        else:
            return False

3. 使用栈实现队列 (LeetCode 232)

3.1题目

Implement the following operations of a queue using stacks.

push(x) – Push element x to the back of queue.
pop() – Removes the element from in front of queue.
peek() – Get the front element.
empty() – Return whether the queue is empty.
Notes:
You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

3.2思路

栈是后进先出，队列是先进先出
可以使用2个栈来表示，一个表示入栈，还有一个表示出栈，出栈的顺序与入栈的顺序相反

3.3代码

class MyQueue(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.input = []
        self.output = []

    def push(self, x):
        """
        Push element x to the back of queue.
        :type x: int
        :rtype: void
        """
        self.input.append(x)

    def pop(self):
        """
        Removes the element from in front of queue and returns that element.
        :rtype: int
        """
        self.peek()
        return self.output.pop()


    def peek(self):
        """
        Get the front element.
        :rtype: int
        """
        if self.output == []:
            while self.input:
                self.output.append(self.input.pop())
        return self.output[-1]

    def empty(self):
        """
        Returns whether the queue is empty.
        :rtype: bool
        """
        return self.input == [] and self.output == []

4. 包含min函数的栈(LeetCode 155 Min Stack)

4.1题目

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) – Push element x onto stack.
pop() – Removes the element on top of the stack.
top() – Get the top element.
getMin() – Retrieve the minimum element in the stack.
Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

4.2思路

使用2个列表，一个用于表示栈，用来压入数据和弹出数据，还有一个表示最小数的列表minstack，当minstack==[]或者当前元素小于minstack的栈顶元素时，则将该元素压入minstack，从而保证minstack的最后一个元素是当前所有元素中最小的。弹栈时注意栈顶元素与minstack的栈顶元素是否相等，若相等，则将两个列表的栈顶元素都弹出，否则只弹出数据栈的栈顶元素

4.3代码

class MinStack(object):

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.minstack = []


    def push(self, x):
        """
        :type x: int
        :rtype: void
        """
        self.stack.append(x)
        if self.minstack == [] or x <= self.minstack[-1]:
            self.minstack.append(x)



    def pop(self):
        """
        :rtype: void
        """
        if self.stack != []:
            if self.stack[-1] == self.minstack[-1]:
                self.minstack.pop()
            self.stack.pop()


    def top(self):
        """
        :rtype: int
        """
        if self.stack != []:
            return self.stack[-1]
        else:
            return None


    def getMin(self):
        """
        :rtype: int
        """
        if self.minstack != []:            
            return self.minstack[-1]
        else:
            return None

5. 合法的出栈序列

5.1题目

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4，5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

5.2思路

新创建一个栈用于模仿栈的压入和弹出，若弹出序列正确，则这个新创建的栈应该为空

5.3代码

Class Solution:
    def IsPopOrder(self, pushV, popV):
        if pushV == [] or popV == []:
            return False
        stack = []
        for i in pushV:
            stack.append(i)
            while len(stack) and stack[-1] == popV[0]:
                stack.pop()
                popV.pop(0)
        if stack != []:
            return False
        else:
            return True

6. 堆的必备基础知识

二叉堆：是一棵特殊的完全二叉树，其特点：

二叉树中的所有的父节点的值都不大于/不小于其子节点；
根节点的值必定是所有节点中最小/最大的

将父节点的值不大于子节点且根节点值最小的称为最小堆，反之称为最大堆。堆是一种高级的数据结构，在python中有相应的模块deapq

7. 数组中的第K大的数 (LeetCode 215 Kth Largest Element in an Array)

7.1题目

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.**

7.2思路

思路1：先对数组排序，再求解第k个元素
思路2：使用最小堆做，第k大的数即len(q)-k小的元素

7.3代码

#排序法
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        return nums[-k]
#最小堆法
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        heap = []
        for num in nums:
            heapq.heappush(heap, num)
        for i in range(len(nums) - k):
            heapq.heappop(heap)
        return heapq.heappop(heap)

8. 寻找中位数(LeetCode 295 Find Median from Data Stream)

8.1题目

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:
[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

8.2思路

维护两个堆，一个是大顶堆，一个是小顶堆,使用python内置库heapq。
这里写图片描述
如上图所示，每次添加元素时保证 $0 <= l e n (m a x h e a p) - l e n (m i n h e a p) <= 1$ ，且 $m a x <= m i n$
因为heap[0]表示的是堆中最小的元素，所以要使heap[0]表示的是堆中最大的元素，则将加入该堆的所有元素取负。添加元素时，首先将该元素取负加入maxheap中，然后对maxheap和minheap进行调整：如果maxheap中的最大元素比minheap中的最小元素要大或者 $l e n (m a x h e a p) > l e n (m i n h e a p) + 1$ ，弹出maxheap中的最大元素加入minheap中；如果 $l e n (m a x h e a p) < l e n (m i n h e a p)$ ，则将minheap中的最小元素加入maxheap中。
求中位数时，如果数组长度为奇数，则返回 $m a x$ ，是偶数，则返回 $(m a x + m i n) / 2$

8.3代码

from heapq import *
class MedianFinder(object):
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.minHeap = []
        self.maxHeap = []

    def addNum(self, num):
        """
        :type num: int
        :rtype: void
        """
        heappush(self.maxHeap, -num)
        minTop = self.minHeap[0] if len(self.minHeap) else None
        maxTop = self.maxHeap[0] if len(self.maxHeap) else None
        if minTop < -maxTop or len(self.minHeap) + 1 < len(self.maxHeap):
            heappush(self.minHeap, -heappop(self.maxHeap))
        if len(self.maxHeap) < len(self.minHeap):
            heappush(self.maxHeap, -heappop(self.minHeap))
    def findMedian(self):
        """
        :rtype: float
        """
        if len(self.minHeap) < len(self.maxHeap):
            return -1.0 * self.maxHeap[0]
        else:
            return (self.minHeap[0] - self.maxHeap[0]) / 2.0