数据结构之python

数据结构（data structure）是用来存储和组织信息的一种形式。

栈

栈（stack）：只能添加或移除最后一个元素 将元素从栈中移除，被称为出栈（popping）。 将元素放回栈中，被称为入栈（pushing）。 这种最 后一个放入的元素被第一个取出的数据结构，也被称为先进后出（LIFO）型数据结构。 栈有五个方法，is_empty，push，pop，peek和size：

class Stack: #采用驼峰法命名 def __init__(self): self.items = [] def is_empty(self): #空返回True 非空返回False return self.items == [] def push(self,item): self.items.append(item) def pop(self): return self.items.pop() def peek(self): last = len(self.items)-1 return self.items[last] def size(self): return len(self.items)

使用栈逆转字符串：

stack=Stack() conver="" for c in "Hello": stack.push(c) for c in stack: conver+=stack.pop() print(conver)

结果：

olleH

1．使用栈对字符串"yesterday"进行逆序。

stack=Stack() ss="" for c in "yesterdat": stack.push(c) for i in range(stack.size()): ss+=stack.pop() print(ss)

2．使用栈创建一个新列表，将如下列表中的元素逆序排列：[1, 2, 3, 4, 5]。

lis=[1, 2, 3, 4, 5] l=0 a=Stack() for i in lis: a.push(i) **解法一：** for j in range(a.size()): if l < len(lis): lis[l]=a.pull() l=l+1 print(lis) **解法二：** while l < len(lis): for j in range(a.size()): lis[l]=a.pull() l=l+1 print(lis)

队列

队 列是一个先进先出（FIFO）的数据结构：第一个添加的元素也是第一个移除的元素。 队列的四个方法：enqueue，dequeue，is_empty，size:

class Queue: def __init__(self): self.items = [] def is_empty(self): return self.items == [] def enqueue(self,item): self.items.insert(0,item) def dequeue(self): return self.items.pop() def size(self): return len(self.items)

购票队列：

import time import random def simulate_line(self,till_show,max_time): pq = Queue() tix_sold = [] for i in range(10): pq.enqueue("person"+str(i)) t_end=time.time()+till_show now=time.time() while now<t_end and not pq.is_empty(): now = time.time() r=random.randint(0,max_time) time.sleep(r) #模拟售票需要的时间 person=pq.dequeue() print(person) #先进先出 tix_sold.append(person) return tix_sold queue=Queue() sold=queue.simulate_line(5,1) print(sold)

结果：

person0 person1 person2 person3 person4 person5 person6 person7 person8 person9 ['person0', 'person1', 'person2', 'person3', 'person4', 'person5', 'person6', 'person7', 'person8', 'person9']

fizzbuzz

编写一个程序，打印从 1 到 100 之间的数字。碰到 3 的倍数时，不打印数字，而是 打印"Fizz"；碰到 5 的倍数时，则打印"Buzz"；如果是 3 和 5 共同的倍数，则打印 “FizzBuzz”。

def fizzbuzz(): for i in range(1,101): if i%3==0 and i%5==0: print("fizzbuzz") elif i%3==0: print("fizz") elif i%5==0: print("buzz") else: print(i) fizzbuzz()

回文词

回文词（palindrome）指的是逆序和正序拼写得出的单词都相同的词。我们可以写一 个算法检查单词是否是回文词，只需要将单词中所有的字符逆序，并检查逆序后的单词 是否与原本的单词相同即可实现。如果两个单词一模一样，那么该单词就是回文词：

def palindrome(word): word=word.lower() return word[::-1] print(palindrome("monther")) print(palindrome("Mom"))

结果：

rehtnom mom a[i:j] 表示从a[i]到a[j-1] 当i缺醒时，默认为0，a[:3]等同于a[0:3] 当j缺醒时，默认为len(a)，a[1:]等同于a[1:len(a)] 当i,j都缺醒时,a[:]相当于一份完整的a a[i:j:s] i,j与上面一样,s缺醒为1 a[i:j:1]相当于a[i:j] 当s<0,i缺醒，默认为-1，j缺醒,默认为-len(a)-1 所以a[::-1]相当于a[-1:-len(a)-1:-1] 即从最后一个元素到第一个元素复制一遍。 a[2::-1]相当于从下标为2的翻转读取。

计算字母频数

def count_character(s): count={} for c in s: if c in count: count[c]+=1 else: count[c]=1 print(count) count_character("cardiovascular")

结果：

{'c': 2, 'a': 3, 'r': 2, 'd': 1, 'i': 1, 'o': 1, 'v': 1, 's': 1, 'u': 1, 'l': 1}