首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构笔记(二):栈、队列

数据结构笔记(二):栈、队列

作者头像
free赖权华
发布2020-05-21 00:03:02
2430
发布2020-05-21 00:03:02
举报
文章被收录于专栏:赖权华的笔记赖权华的笔记

(一)栈

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
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-05-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档