数据结构和算法（4）

一、物理结构和逻辑结构

物理结构是内存中实实在在的存储结构，就相当于人的血肉和骨骼。

逻辑结构是抽象的概念，依赖于物理结构而存在，就好比人的精神。

栈和队列都属于逻辑结构，它们的物理实现既可以利用数组，也可以利用链表来完成。

二、栈

1.栈的定义

栈（stack）是一种线性数据结构，它就像一个放乒乓球的圆筒容器，栈中的元素只能先入后出。最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶（top）。

栈这种数据结构既可以用数组来实现，也可以用链表来实现。

数组实现：

链表实现：

2.栈的基本操作

a.入栈

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶。

以数组实现为例：

b.出栈

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

在Python中，列表很好地实现了栈的功能，append方法相当于入栈，pop方法相当于出栈。

三、队列

1.队列的定义

队列（queue）是一种线性数据结构，它就相当于排队。与排队的特点一样，队列中的元素先入先出。队列的出口端叫作队头（front），队列的入口端叫作队尾（rear）。

与栈类似，队列这种数据结构既可以用数组来实现，也可以用链表来实现。

用数组实现时，为了入队操作的方便，把队尾位置规定为最后入队元素的下一个位置 。

数组实现：

链表实现：

2.队列的基本操作

a.入队

入队（enqueue）就是把新元素放入队列中，只允许在队尾的位置放入元素，新元素的下一个位置将会成为新的队尾。

b.出队

出队操作（dequeue）就是把元素移出队列，只允许在队头一侧移出元素，出队元素的后一个元素将会成为新的队头。

这时候问题来了，随着不断的出队，队头左边的空间会失去作用，队列的容量会越来越小。而用数组实现的队列可以采用循环队列的方式来维持队列容量的恒定。

如下图的例子，剩下的2个元素分布于数组的末尾，这时有一个新元素要入队。

这时可以利用已出队元素留下的空间，让队尾指针重新指回数组的首位。这样一来，整个队列的元素就“循环”起来了。一直到（队尾下标+1）%数组长度=队头下标时，代表此队列真的已经满了。

需要注意的是，队尾指针指向的位置永远空出1位，所以队列最大容量比数组长度小1。

用Python实现一个队列：

 1 class MyQueue:
 2     def __init__(self, capacity):
 3         self.list = [None] * capacity
 4         self.front = 0
 5         self.rear = 0
 6         
 7     def enqueue(self, element):
 8         if (self.rear+1) % len(self.list) == self.front:
 9             raise Exception("队列已满！")
10         self.list[self.rear] = element
11         self.rear = (self.rear+1) % len(self.list)
12         
13     def dequeue(self):
14         if self.rear == self.front:
15             raise Exception("队列已满！")
16         dequeue_element = self.list[self.front]
17         self.front = (self.front+1) % len(self.list)
18         return dequeue_element
19     
20     def output(self):
21         i = self.front
22         while i != self.rear:
23             print(self.list[i])
24             i = (i+1) % len(self.list)
25             
26 myQueue = MyQueue(6)
27 myQueue.enqueue(3)
28 myQueue.enqueue(5)
29 myQueue.enqueue(6)
30 myQueue.dequeue()
31 myQueue.dequeue()
32 myQueue.dequeue(2)
33 myQueue.dequeue(4)
34 myQueue.output()

四、栈和队列的应用

1.栈的应用

栈的输出顺序和输入顺序相反，所以栈通常用于对“历史”的回溯，也就是逆流而上追溯“历史”。

例如实现递归的逻辑，就可以用栈来代替，因为栈可以回溯方法的调用链。

栈还有一个著名的应用场景是面包屑导航，使用户在浏览页面时可以轻松地回溯到上一级或更上一级页面。

2.队列的应用

队列的输出顺序和输入顺序相同，所以队列通常用于对“历史”的回放，也就是按照“历史”顺序，把“历史”重演一遍。

例如在多线程中，争夺公平锁的等待队列，就是按照访问顺序来决定线程在队列中的次序的。

再如网络爬虫实现网站抓取时，也是把待抓取的网站URL存入队列中，再按照存入队列的顺序来依次抓取和解析的。

3.双端队列

既可以先入先出，也可以先入后出的数据结构叫作双端队列（deque）。

对双端队列来说，从队头一端可以入队或出队，从队尾一端也可以入队或出队。

4.优先队列

还有一种队列，它遵循的不是先入先出，而是谁的优先级最高，谁先出队。这种队列叫作优先队列。

优先队列已经不属于线性数据结构的范畴了，它是基于二叉堆来实现的。

算法和数据结构

数据结构和算法（4）

相关

标签