堆栈与队列

说起堆栈都会考虑到两个方面,一是指进程中的堆和栈,二是指数据结构中的堆和栈。

一、进程的堆和栈

栈主要是用来存放局部函数的参数和局部变量的值,由系统自动分配释放,具体的操作和数据结构的栈一样,即先进后出,通常是和线程相关的,栈里存的是栈帧,每个栈帧包括栈帧地址和栈顶地址;而堆是由程序员自动分配释放(malloc,calloc等),如果不释放,就会由操作系统自动回收,操作类似于链表。不过在运行中仍然可以申请。最多可以申请一个进程内堆的最大值。

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

如果是使用C语言编写代码的,是很容易出现缓冲区溢出的,之前在1988年就发生了利用该漏洞进行攻击的事件。简单解释缓冲区溢出,就是我们分配了一个固定大小的数组,但是有人恶意写入超过数组边界的字符串,然而C语言是不做边界检测的,所以就导致向上写入,如果攻击者在函数返回地址中写入其他的返回地址,可能导致意想不到的事情发生。具体可参考: 缓冲区溢出原理

在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,LIFO。
类比: 往纸箱里放书,只能往最上面放,或者从最顶上拿
基本操作:顶端放入新元素(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()

队列是比较常见的一种数据结构,在很多编程语言以及中间件都有使用,比如Java,Python啊, 中间件RocketMQ,Redis等等。甚至Linux,TCP中都有队列的概念。TCP中有半连接队列,全连接队列。Linux中也有消息队列,用于进程间通信的一种方式。

看一下JAVA中的队列:

JAVA的队列应用场景更广泛一些,不同的队列支持多种使用场景,尤其是线程池中。

ArrayBlockingQueue:是一个数组结构的有界阻塞队列,此队列按照先进先出原则对元素进行排序。

LinkedBlockingQueue:是一个单向链表实现的阻塞队列,此队列按照先进先出排序元素,吞吐量通常要高于ArrayBlockingQueue。静态工厂方法Executors.newFixedThreadPool使用了这个队列。

SynchronousQueue :一个不存储元素的阻塞队列,每个插入操作必须等到另外一个线程调用移除操作,否则插入操作一直处理阻塞状态,吞吐量通常要高于LinkedBlockingQueue,Executors.newCachedThreadPool使用这个队列。这个有点像golang中的channel。newCachedThreadPool可以无限创建多个线程(当然有一个上限是Integer。Max_VALUE)。

PriorityBlockingQueue:优先级队列,是基于数组的堆结构,进入队列的元素按照优先级会进行排序。这个实际上就是比较特殊的队列了,或者说并不是队列,而是堆的结构。

上述这几个队列都是应用在线程池中,通过Lock接口的锁来实现线程安全,此外支持阻塞,如果没有数据,则消费者可阻塞等待;如果队列已满,则阻塞等待。阻塞的实现主要是借助于Condition接口。具体可看我之前写的文章:

Java并发同步之阻塞队列与Condition接口

关于线程池的介绍可以看: Java并发编程之基本使用

说完栈和队列,现在看看如何使用两个栈实现一个队列。
栈是先进后出,队列是先进先出。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是一个很重要的函数,它用来比较父节点和左右两个子节点的值的,满足一定条件是要交换的。

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

堆可以用来解决TopK的问题,最大K个值或者最大K个值。

在Java中的,优先级队列就使用了堆的结构。Timer、ScheduleTheadPool都有使用。其会根据延迟时间来排序。具体可以看DelayQueue,DelayWorkerQueue,PriorityQueue等源码。

参考资料:

进程地址空间的布局

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