栈是一种先进后出的数据结构.栈上的插入操作被称为push,删除操作被称为pop.现实生活中摞盘子就是一种栈,先摞的盘子最后才能拿出来,而最后摞进来的盘子最先被拿出去.

python中可以使用列表模拟栈操作:

A = [1,2,3]
A.append(4)
print(A) # [1, 2, 3, 4]
print(A.pop()) # 4
print(A)       # [1, 2, 3]
print(A.pop()) # 3
print(A)       # [1, 2]

队列

队列是一种先进先出的数据结构.经常用在业务的排队处理上.

队列是用指针实现的,我们用列表模拟的话性能会下降,python中使用queue库可以实现队列功能:

import queue

q = queue.Queue()

for i in range(5):
    q.put(i)

while not q.empty():
    print(q.get())

链表

链表就像一个铁链子一样,前一个节点的next指向后一个节点,如果是双向链表,后一个节点的prev指向前一个节点.

image.png

class ListNode:
    def __init__(self, x):
        self.val = x
        self.prev = None
        self.next = None

图有两种表示方法,一种是邻接链表的组合,另一种是使用邻接矩阵的方式。

下图是一个无向图的表示:
image.png

邻接链表是一个包含n条链表组成的数组AdjAdj[n]包含所有与其相连的节点。有的时候为了方便,常常使用数组或集合代替链表:

G = [[1,2,5],
     [2,1,5,3,4],
     [3,2,4],
     [4,2,5,3],
     [5,4,1,2]]

邻接矩阵是一个n \times n的二维矩阵A,其中A[i][j] = 1表示节点i与节点j相连,A[i][j] = 0表示节点i与节点j不相连。

G = [[0,1,0,0,1],
     [1,0,1,1,1],
     [0,1,0,1,0],
     [0,1,1,0,1],
     [1,1,0,1,0]]

有向图于无向图类似:
image.png

posted @ 2019-02-08 14:39:49
评论加载中...

发表评论