(一)栈
1、栈是一种后进先出,先进后出的数据结构。
2、栈是一种操作受限的线性表,只允许在一端插入和删除数据。
3、栈主要包含2个操作,入栈和出栈
4、栈可以用数组实现,也可以用链表实现。用数组实现的栈叫做顺序栈,用链表实现的栈叫做链式栈。
例如:
现在有一个空瓶子。
1、我们依次放入多个苹果
2、从瓶子中取苹果的时候,最后放进去的苹果会最先取出来,最先放进去的苹果最后取出来。
3、只能从瓶口放入或取出苹果。(只允许在一端插入和删除数据)
用数组实现一个栈:(这里用列表代替了)
1 class ArrayStack():
2
3 ITEMS = [] # 这里用列表代替了
4 COUNT = 0 # 栈中的元素个数
5 N = 10 # 栈的大小
6
7 def push(self ,item):
8 """
9 入栈
10 :param item:
11 :return:
12 """
13 if len(self.ITEMS) >= self.N: return False # 栈已经满了
14 self.ITEMS.append(item)
15 self.COUNT += 1
16 return True
17
18 def pop(self):
19 """
20 出栈
21 :return:
22 """
23 if len(self.ITEMS) == 0: return False # 栈为空
24 item = self.ITEMS.pop()
25 self.COUNT -= 1
26 return item
(二)队列
1、队列是一种先进先出的数据结构。例如:超市排队付款,排在前面的先付完款,然后先出去。后来的只能排队,不允许插队。
2、栈只支持2个基本操作入栈(push)和出栈(pop)。队列也只支持2个基本操作,入队 enqueue(),放一个数据到队列尾部;出队 dequeue(),从队列头部取一个元素。
3、队列和栈一样。也是一种操作受限的线性表结构。
4、跟栈一样,也可以用数组或链表实现。用数组实现的队列叫顺序队列,用链表实现的队列叫链式队列。
用数组实现一个队列(这里用列表代替了):
1 class ArrayQueue():
2
3 ITEMS = [] # 数组
4 HEAD = 0 # 队头索引
5 TAIL = 0 # 队尾索引
6
7 def __init__(self,n):
8 self.n = n # 数组大小
9
10 def enqueue(self,item):
11 """
12 入队
13 :param item:
14 :return:
15 """
16 if self.TAIL == self.n: return False # 队尾索引等于数组大小,表示队列满了
17 self.ITEMS.append(item)
18 self.TAIL += 1
19 return True
20
21 def dequeue(self):
22 """
23 出队
24 :return:
25 """
26 if self.HEAD == self.TAIL: return False # 队头索引==队尾索引,表示队列为空
27 item = self.ITEMS[self.HEAD]
28 self.ITEMS[self.HEAD] = "X" # 标识已经删除
29 self.HEAD += 1
30 return item
(三)练习题
1、leetcode 20
1 class Solution:
2 def isValid(self, s: str) -> bool:
3 the_dict = {"(":")","{":"}","[":"]","k":"k"}
4 stack = ["k"]
5 for i in s:
6 if i in the_dict: stack.append(i) # 将左括号压入栈
7 elif the_dict[stack.pop()] != i: return False # 如果字符串中的右括号不等于预期的右括号,返回false
8 return len(stack) == 1