数据结构
2017-09-16 本文已影响0人
谁吃了我的薯条
—— 栈 AND 列
A、栈
栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为栈顶。咖啡厅内的一摞盘子是现实世界中常见的栈的例子。只能从最上面取盘子，盘子洗净后，也只能摞在这一摞盘子的最上面。栈被称为一种后入先出（LIFO，last-in-first-out）的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问。为了得到栈底的元素，必须先拿掉上面的元素。
对栈的两种主要操作是将一个元素压入栈和将一个元素弹出栈。入栈使用push()方法，出栈使用pop()方法。下图演示了入栈和出栈的过程。
栈演示
另一个常用的操作是预览栈顶的元素。pop()方法虽然可以访问栈顶的元素，但是调用该方法后，栈顶元素也从栈中被永久性地删除了。peek()方法则只返回栈顶元素，而不删除它。
为了记录栈顶元素的位置，同时也为了标记哪里可以加入新元素，我们使用变量top，当向栈内压入元素时，该变量增大；从栈内弹出元素时，该变量减小。
push()、pop()和peek()是栈的3个主要方法，但是栈还有其他方法和属性。
Stack() # 建立一个空的栈对象
push() # 把一个元素添加到栈的最顶层
pop() # 删除栈最顶层的元素，并返回这个元素
peek() # 返回最顶层的元素，并不删除它
isEmpty() # 判断栈是否为空
size() # 返回栈中元素的个数
python 实现stack的模拟实现：
class stack(object): # define 类
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[-1]
def size(self):
return len(self.items)
Leetcode实例
20. Valid Parentheses
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.
解题思路：
- 创建一个空栈，用来存储尚未找到的左括号；
- 便利字符串，遇到左括号则压栈，遇到右括号则出栈一个左括号进行匹配；
- 在第二步骤过程中，如果空栈情况下遇到右括号，说明缺少左括号，不匹配；
- 在第二步骤遍历结束时，栈不为空，说明缺少右括号，不匹配；
源码如下：
class stack(object):
def __init__(self):
self.items=[]
def isEmpty(self):
return len(self.items)==0
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
if not self.isEmpty():
return self.items[-1]
def size(self):
return len(self.items)
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
LEFT = ['(', '[', '{']
RIGHT = [')', ']', '}']
t=stack()
for i,st in enumerate(s):
if st in LEFT:
t.push(st)
elif st in RIGHT:
if not t or not 1 <= ord(st) - ord(t.peek()) <= 2:#查看ASCII码
return False
t.pop()
return t.isEmpty()
result = Solution().isValid('[(){([)}]')
print(result)
#------------示例如下---------#
result = Solution().isValid('[(){([)}]')
print(result)
##result##
Flase
42. Trapping Rain Water
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
队列主要应用与顺序操作问题上，比如打印机进程缓冲、计算机进程以及银行排队等；
对象的抽象数据类型，主要操作有Enqueue（入队），Dequeue(出队)，GetLength(获取队列长度)等操作；
其结构代码如下：
class Queue(object):
def __init__(self): #使用list模拟队列
self.items=[]
def isEmpty(self):
return len(self.items)==0
def Enqueue(self,item): #入队
self.items.append(item)
def Dequeue(self): #出队
return self.items.pop(0)
def Getlength(self): #获取队列长度
return len(self.items)
举例
621. Task Scheduler
Given a char array representing tasks CPU need to do. It contains
capital letters A to Z where different letters represent different
tasks.Tasks could be done without original order. Each task could
be done in one interval. For each interval, CPU could finish one
task or just be idle.
However, there is a non-negative cooling interval n that means
between two same tasks, there must be at least n intervals that
CPU are doing different tasks or just be idle.
You need to return the least number of intervals the CPU will take
to finish all the given tasks.
Example
Input: tasks = ['A','A','A','B','B','B'], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
Note
1、The number of tasks is in the range [1, 10000].
2、The integer n is in the range [0, 100].
