[TOC]

栈（Stack）类，用于模拟一种具有后进先出（LIFO）特性的数据结构

#!/usr/bin/python3
#功能：模拟Stack（栈）- 后进先出(LIFO)

class Stack:
    def __init__(self,start = []):
        self.stack = []
        for i in start:
            self.push(i)  #压栈
    #判断当前栈是否为空（返回 True 或 False）
    def isEmpty(self):
        return not self.stack

    #往栈的顶部压入一个数据项
    def push(self,obj):
        self.stack.append(obj)

    #从栈顶弹出一个数据项（并在栈中删除）
    def pop(self):
        if not self.stack:
            print('警告, Stack 已空！')
        else:
            self.stack.pop()  #弹栈

    #显示当前栈顶的一个数据项
    def top(self):
        if not self.stack:
            print('警告, Stack 已空！')
        else:
            return self.stack[-1]  #显示栈顶

    #显示当前栈底的一个数据项
    def bottom(self):
        if not self.stack:
            print('警告, Stack 已空！')
        else:
            return self.stack[0]

demo = Stack([1,2,3,4,5])
print(demo.top(),demo.bottom())  #显示栈顶/栈底

栈和队列数据结构

• 栈
  • 先进后出
• 队列
  • 先进先出

你还能复述出“迭代”的概念吗？

所谓迭代，是重复反馈过程的活动，其目的通常是为了接近并到达所需的目标或结果。每一次对过程的重复被称为一次“迭代”，而每一次迭代得到的结果会被用来作为下一次迭代的初始值。

为什么这么说呢？不要忘了，递归的实现可以是函数自个儿调用自个儿，每次函数的调用都需要进行压栈、弹栈、保存和恢复寄存器的栈操作，所以在这上边是非常消耗时间和空间的。

另外，如果递归一旦忘记了返回，或者错误的设置了返回条件，那么执行这样的递归代码就会变成一个无底洞：只进不出！所以在写递归代码的时候，千万要记住口诀：递归递归，归去来兮！出来混，总有一天是要还的！
递归必须满足哪两个基本条件？
答：
一、函数调用自身
二、设置了正确的返回条件

1. 请聊一聊递归的优缺点（无需官方陈词，想到什么写什么就可以）

答：

优点：

1）递归的基本思想是把规模大的问题转变成规模小的问题组合，从而简化问题的解决难度（例如汉诺塔游戏）。

2）有些问题使用递归使得代码简洁易懂（例如你可以很容易的写出前中后序的二叉树遍历的递归算法，但如果要写出相应的非递归算法就不是初学者可以做到的了。）

缺点：

1）由于递归的原理是函数调用自个儿，所以一旦大量的调用函数本身空间和时间消耗是“奢侈的”（当然法拉利也奢侈，但还是很多人趋之若鹜）。

2）初学者很容易错误的设置了返回条件，导致递归代码无休止调用，最终栈溢出，程序崩溃。

1.计算闰年与平年

定义闰年的原理:能被4整除但不能被100整除,或者能被400整除都是闰年。

//############# python ###############
#!/usr/bin/python
year = input("请输入一个年份：")
while not year.isdigit():
    year = input("输入错误请重新输入年份：")
year = int(year)

if (year % 400 == 0):
    print(year," 年是闰年！")  # 注意不同类型 的不能进行 + 拼接
else:
    if (year % 4 == 0) and (year % 100 != 0):
        print(year," 年是闰年！")
    else:
        print(year," 年是平年！")

2.水仙花数

如果一个 3 位数等于其各位数字的立方和，则称这个数为水仙花数。例如：153 = 1^3 + 5^3 + 3^3，因此 153 就是一个水仙花数;

############# python ###############
#!/usr/bin/python
for i in range(100, 1000):
    sum = 0
    temp = i
    while temp:
        sum = sum + (temp%10) ** 3
        temp //= 10         # 注意这里要使用地板除哦~ （即 从最低取开始取值）
    if sum == i:
        print(i)

欧几里德算法

#!/usr/bin/python
#辗转相除法（欧几里德算法|计算大数效率高）

#方式1：
def gcd(x,y):
    while 1:
        temp = x % y
        if temp == 0:
            return y
        x, y = y, temp
temp = input("输入除数与被除数利用,分割如( 319,377 ):")
temp = temp.split(',')
x = int(temp[0])
y = int(temp[1])
print("%d 与 %d 的最大公约数：" %(x,y),gcd(x,y))

#方式2：递归求出最大公约数（比较耗费资源）
def gcd(x,y):
    if y:
        return gcd(y, x % y)  #精辟呀
    else:
        return x

##############计算结果###############
# 输入除数与被除数利用,分割如( 112,145 ):112,106
# 112 与 106 的最大公约数： 2

编码

13. 编写一个将十进制转换为二进制的函数，要求采用“除2取余”（脑补链接）的方式，结果与调用bin()一样返回字符串形式。

    def Dec2Bin(dec):  
        temp = []
        result = ''
        
        while dec:          #如当desc 10
            quo = dec % 2
            dec = dec // 2
            temp.append(quo)  # [0,0,0,1]
    
        while temp:
            result += str(temp.pop()) #pop是弹栈 1000 (默认是弹出列表得最后一个元素)
        
        return result
    
    print(Dec2Bin(62))

---

4.约瑟夫环

描述: 将多个人排出一个圆圈并且为每一个人的所站进行编号,当那个人的编号是3的倍数的时候将被剔除,直至剩下最后一人;

package com.weiyigeek.Collection;
import java.util.ArrayList;
public class Demo9_ArrayList {
  public static void main(String[] args) {
    // 1.约瑟夫环
    System.out.println("幸运人的编号 : " + getLuckly(8));
  }
  /**
	 * getLuckly : 实现约瑟夫环算法
	 * @param i : 人数
	 * @return Integer
	 */
  private static Integer getLuckly(int i) {
    ArrayList<Integer> list = new ArrayList<Integer>(); //创建存储1到num的对象
    for(int num = 1; num <= i; num ++){ //注意位置号从1开始到i结束
      list.add(num); //将每一个人进行标位置号
    }
    
    int count = 1; // 计算器如果是3的倍数的人将被剔除
    for(int num = 0; list.size() != 1; num++)
    {
      if(num == list.size()){
        num = 0;  //如果当索引值等于列表总的个数的时候,重置为0进行下一轮比较剔除
      }
      
      if(count % 3 == 0) {
        list.remove(num--); //非常注意这里因为ArrayList删除列表元素后，后面的元素会向前补齐(索引这里需要要索引移动回到删除的位置)
      }
      count++;
    }
    return list.get(0); //最后只剩下1人打印其的位置号
  }
}

//幸运人的编号 : 7