堆栈与队列

 

堆,栈主要包括两个方面,一是指内存中的堆和栈,二是指数据结构中的堆和栈。

一、内存中的堆和栈

在C语言中,栈主要是用来存放局部函数的参数和局部变量的值,由系统自动分配释放,具体的操作和数据结构的栈一样,即先进后出;而堆是由程序员自动分配释放(malloc,calloc等),如果不释放,就会由操作系统自动回收,操作类似于链表。

栈中分配局部变量空间,堆区是向上增长的用于分配程序员申请的内存空间。另外还有静态区是分配静态变量,全局变量空间的;只读区是分配常量和程序代码空间的;以及其他一些分区。

在Python中,一切皆为对像,且Python是由C实现的,Python中所有的对象都是存在堆中,它的分配器会根据对象的大小来决定选择哪种,对于大于512KB(可以设置更改)的对象,使用 Python 原生内存分配器(Python’s raw memory allocator)进行分配,它的本质也是调用 C 标准库中的malloc/realloc/free等 函数;对于小于等于 512KB 的对象,内存分配主要由 Python 对象分配器(Python’s object allocator)实施,也就是本文中所要介绍的 pymalloc 机制;对于一些内置类型,如 int/dict/list/string 等,又会有单独的针对这些内置类型的分配器实现。比如管理 int 类型就使用一个简单的 free list。

二、数据结构中的堆,栈和队列。

1、栈

特别:后进先出 Last In First Out
类比: 往纸箱里放书,只能往最上面放,或者从最顶上拿
应用:之前讲到的函数调用函数的调用栈,最外层的main函数最先执行,最后退出。
注意:只能对栈顶进行操作
基本操作:顶端放入新元素(push),顶端移除元素(pop)
栈上溢:当试图向一个满栈中插入一个元素时,会出现栈上溢。
栈下溢:当试从一个空栈中获得一个元素时,就出现栈下溢。
栈也用来各种程序的局部变量。
用栈计算四则运算表达式。
需要一个数字栈,一个操作符栈,一直从左向右读取,读到右括号。

一个基本例子

class Stack(object):

    def __init__(self,size):
        self.size = size
        self.stack = []

    def isEmpty(self):
        return True if len(self.stack) == 0 else False

    def isFull(self):
        return True if len(self.stack) == self.size else False


    def push(self,a):
        #the last one of list stack is the bottom of Stack
        assert(not self.isFull())
        self.stack.append(a)

    def pop(self):
        assert not self.isEmpty()
        self.stack.pop()

    def get_top(self):
        assert not self.isEmpty()
        return self.stack[-1]


    def clear(self):
        while not self.isEmpty():
            self.pop()


if __name__ == "__main__":

    stack = Stack(3)
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.clear()
     print stack.get_top()

上述代码实现了基本的栈的功能。

这里要说一下Flask框架,因为在Flask中就使用了栈这种数据结构。

Flask中的请求上下文以及应用上下文都存储在栈中,定义如下:

_request_ctx_stack = LocalStack()
_app_ctx_stack = LocalStack()

具体可见Flask源码,以及我写过的一篇博客 Flask上下文

再说一下队列。

队列与栈正好相反,队列是FIFO,即先入先出,下面实现了一个基本队列。

class Full(Exception):
    pass


class Empty(Exception):
    pass



class Queue:

    def __init__(self,maxsize):
        self.maxsize = maxsize
        self.queue = []

    def push(self,obj):
        if len(self.queue) >= self.maxsize:
            raise Full
        else:
            self.queue.append(obj)

    def isEmpty(self):
        return True if len(self.queue) else False

    @property
    def size(self):
        return len(self.queue)

    def pop(self):
        if len(self.queue) == 0:
            raise Empty
        else:
            return self.queue.pop(0)

    def peek(self):
        return self.queue[0]


s=Queue(3)
s.push(3)
s.push(4)
s.push(6)



print s.pop()
print s.pop()
print s.pop()

说完栈和队列,现在看看如何使用两个栈实现一个队列。
栈是先进后出,队列是先进先出。push数据就往第一个栈中放入数据,pop数据时,将栈1中的数据都pop出来,并push到栈中,在栈1中先进后出的,到了栈2再经过一次先进后出,就变成了整体的先进先出。下面是具体代码:

class Stack2Queue:

    def __init__(self,size1,size2):
        self.stack1 = Stack(size1)
        self.stack2 = Stack(size2)


    def push(self,a):
        self.stack1.push(a)

    def pop(self):
        if not self.stack2.isEmpty():
            self.stack2.pop()
        else:
            while not self.stack1.isEmpty():
                self.stack2.push(self.stack1.pop())

用两个栈能实现一个队列,那两个队列也可以实现一个栈。push数据同样是向队列1中push数据,pop数据时,队列1中的数据,除了末尾的一个,全部都放到队列2中,此时队列1就是末尾的一个元素了,现在队列1 pop的数据就是最先进入的元素了。此时还没完,还要把队列2中的数据再返回队列1中,因为还要进行下一次的pop操作。

class Queue2Stack:

    def __init__(self,size1,size2):
        self.queue1 = Queue(size1)
        self.queue2 = Queue(size2)

    def push(self,data):
        self.queue1.push(data)

    def pop(self):
        while self.queue1.size!=1:
            self.queue2.push(self.queue1.pop())
        result = self.queue1.pop()
        while not self.queue2.isEmpty():
            self.queue1.push(self.queue2.pop())
        return result

3、堆

上面说完了栈和队列,再说下堆。

堆是一种特殊的结构,分为最大堆(也叫大根堆)和最小堆(也叫小根堆)。这里就拿最小堆来说了。

在Python中有内置的heapq堆模块,在里面,有这样一个定义:堆是一个数组,且满足一个条件:当前位置k,a[k]<=a[2*k+1] and a[k]<=a[2*k+2]。

有了上面的条件,那对于一个列表,我们可以很轻松滴将其转换为最小堆。具体代码:

def heapify(array,index):
    """
    as for every index,we compare parent and two children:left and right

    the parent is the index.

    the heapify is for minheap

    """
    leftchild = lambda x:2*x + 1
    rightchild = lambda x:2*x + 2

    end = len(array) - 1
    while True:
        if index > end:
            break
        left = leftchild(index)

        if left > end:
            break

        right = rightchild(index)
        # get the more smaller.
        child = right if right <= end and array[right] < array[left] else left
        print child,array[left],array[right]
        #if the smaller of the children is smaller than arrray[index],no need to exchange any more
        if array[child] >= array[index]:
            break
        else:
            #should recurise until break.
            array[child],array[index] = array[index],array[child]
            index = child




def list_2_heapq(array):
    length = len(array)
    for index in range((length-1)/2,-1,-1):
        heapify(array,index)
    
array=[3,6,5,7,4,8,1]

list_2_heapq(array)

 

我在上面代码中也都写了注释,应该很好理解。heapify是一个很重要的函数,它用来比较父节点和左右两个子节点的值的,满足一定条件是要交换的。

比如现在有一个现成的堆,我现在要插入一个元素,那肯定要放到正确的位置。就从根节点开始比较呗,如果我比两个子节点都小,就把子节点最小的那个和这个节点交换。并把当前位置下移动刚才交换元素的位置。再进行上述操作,直到达到最小堆的底部。

 

 

 

 

--------EOF---------
本文微信分享/扫码阅读