堆栈stack & 队列queue(I)

  1. Stack

    Stack ADT: A list with the restriction that insertion and deletion can be performed only from one end, called Top

    举几个简单的例子来理解一下堆栈的property「 Last In First Out

    食堂的餐盘,放在最上面的最先被拿走 以及 输入编辑器里面的Undo (撤销) 操作

    我们来看一下push (x) & pop ( ) 的伪代码和示意图,来加深对这两个操作的理解。

    1
    2
    3
    4
    5
    6
    7
    # push
    if Top = MaximumSize:
    return ("Stack is full")
    else:
    Top = Top + 1
    ArrayStack(Top) = new
    item

    1

    1
    2
    3
    4
    5
    # pop 
    if Top = 0:
    return ("Stack is empty")
    else:
    Top = Top - 1

2

然后我们再来看一下堆栈的应用,

应用1: Infix Expression to Postfix Expression。「参考这个视频进行整理哒」。

也就是把a op b 变成 ab op

栗子🌰 Infix: A + B C - D E Postfix: ABC + DE -

栗子🌰 Infix: ((A + B)C - D) E Postfix: AB+C D - E

堆栈里面的操作符(operator)的push和pop是和其precedence(优先级)相关。通俗点讲就是先乘除后加减🐶

用python来实现一下这个东西。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Stack:
def __init__(self):
self.items = []
self.length = 0

def push(self, val):
self.items.append(val)
self.length += 1

def empty(self):
return self.length == 0

def pop(self):
if self.empty():
return None
self.length -= 1
return self.items.pop()

def peek(self):
if self.empty():
return None
return self.items[0]

def __str__(self):
return str(self.items)


precedence = {'*':3,'/':3,'+':2,'-':2,'(':1} # dict to store the operators # 数字越大,优先级越高


def convert(expression):
print(__convert(expression.split()))

def __convert(tokens):
stack = Stack()
res = []
for token in tokens:
if token.isalpha():
res.append(token)
elif token == '(':
stack.push(token)
elif token == ')':
while True:
temp = stack.pop()
if temp is None or temp == '(':
break
elif not temp.isalpha():
res.append(temp)
else:
if not stack.empty():
temp = stack.peek()
while not stack.empty() and precedence[temp] >= precedence[token] and token.isidentifier():
res.append(stack.pop())
temp = stack.peek()
stack.push(token)

while not stack.empty():
res.append(stack.pop())
return res


convert("A * ( B + C ) + D")
# ['A', 'B', 'C', '+', 'D', '+', '*']

应用2: Depth First Search (DFS) 。「参考这个网站 进行整理哒」。

DFS traverses a graph in depthward motion and uses a stack to remember to get the next vertex to start a search , when a dead end occurs in any iteration.

Rule:

Step 1: Visit the adjacent unvisited vertex. Mark it as visited, display it and push it in stack. Then we explore each adjacent vertex that is not included in the visited set.

Step 2: If no adjacent vertex is found, pop up a vertex from the stack.

Step 3: Repeat Step 1 & Step 2 until the stack is empty.

然后我们再用python来实现一下dfs这个思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# non-recursive
def dfs_iterative(graph, start):
visited, stack = set(), [start] # set to keep track of visited vertices
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited

# recursive
def dfs_recursive(graph, start, visited = None):
if visited is None:
visited = set()
visited.add(start)
for n in graph[start] - visited:
dfs_recursive(graph, n, visited)
return visited
  1. Queue

    Queue ADT: a queue is open at both its end.{个人觉得这句话特别重要,stack只有一边开的,所以后面进来的先出去。而queue就不一样了,两边都是开的,所以也才有First In First Out 这个property}. One end is always used to insert data ,也就是rear or tail 这一端进行enqueue这个操作。The other is used to remove data,也就是front or head 这一端进行dequeue这个操作。举个生活中的例子:比如在机场外面打的士的时候,先来的先走呀~🐶

    2

    3

Breath First Search algorithm traverses a graph in a breathward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration.

---------------------- 本文结束----------------------