[数据结构与算法]基本数据结构-栈和队列，排序与搜索

栈

定义

后进先出（LIFO）的线性表，只有一端可以操作

实现

1. 创建容器(空列表)

class Stack(object):
    """栈"""
    def __init__(self):
         self._list = [] #建立为私有，不允许更改

2. 判断是否为空

    def is_empty(self):
        return self.items == []
	
		#也可以是return not self.__list
	

3. 压栈

    def push(self, item):
        self.__list.append(item) #添加元素到栈顶

4. 弹出元素

	def pop(self):
       return self.__list.pop() #弹出栈顶元素

5. 返回栈顶元素

	def peek(self):
   	if self.__list:
       	return self.__list[-1] #栈从栈底开始计数
   	else:
   		return None
   	

6. 返回栈的大小

	def size(self):
        return len(self.__list)

7. 测试

if __name__ == "__main__":
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("itcast")
    print stack.size()
    print stack.peek()
    print stack.pop()
    print stack.pop()
    print stack.pop()

队列

定义

先进先出的(FIFO)的线性表，只允许在一端进行插入操作，而在另一端进行删除操作

实现

1. 创造队列

class Queue(object):
   """队列"""
   def __init__(self):
       self.items = [] #创造list作为容器

2. 判空

    def is_empty(self):
        return self.items == []

3.进队列

    def enqueue(self, item):        
        self.items.append(item)   #尾部添加
		#self.items.insert(0,item) #头部添加

4. 出队列

    def dequeue(self):    
        return self.items.pop(0) #头部出，要输出元素
		#return self.items.pop() #尾部出

5. 返回大小

    def size(self):
        return len(self.items)

6. 测试

if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    print q.size()
    print q.dequeue()
    print q.dequeue()
    print q.dequeue()

双端队列

• 两个栈底部合在一起

实现

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.items == []

    def add_front(self, item):
        """在队头添加元素"""
        self.items.insert(0,item)

    def add_rear(self, item):
        """在队尾添加元素"""
        self.items.append(item)

    def remove_front(self):
        """从队头删除元素"""
        return self.items.pop(0)

    def remove_rear(self):
        """从队尾删除元素"""
        return self.items.pop()

    def size(self):
        """返回队列大小"""
        return len(self.items)


if __name__ == "__main__":
    deque = Deque()
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print deque.size()
    print deque.remove_front()
    print deque.remove_front()
    print deque.remove_rear()
    print deque.remove_rear()

排序

• 算法稳定性：排序之后相同的子序列位置不变

(4，1)(3，1)(3，7)(5，6)

(3，1)(3，7)(4，1)(5，6) (维持次序)
(3，7)(3，1)(4，1)(5，6) (次序被改变)

冒泡排序

1. 定义
   它重复地遍历要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
2. 顺序表实现

• 稳定

def bubble_sort(alist)
	n = len(alist)
	for j in range(n-1):#控制要走多少次
		count = 0
		for i in range(0,n-1-j): #游标i一次从到位的遍历和比较
			if alist[i]>alist[i+1]:
				alist[i],alist[i+1] = alist[i+1],alist[i]
				count += 1
		if 0 == count:
			return

def bubble_sort(alist):
    for j in range(len(alist)-1,0,-1):
        # j表示每次遍历需要比较的次数，是逐渐减小的
        for i in range(j):
            if alist[i] > alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]
			
		

选择排序

• 找到后面子数列里最小的放到前面
• 不稳定

def select_sort(alist)
	n = len(alist)
	for j in range(0,n-1): #j:0~n-2
		min_index = j
		for i in range(j+1,n):
			if alist(min_index)>alist[i]:
				min_index = i
		alist[j],alist[min_index] = alist[min_index],alist[j]

插入算法

• 稳定

def insert_sort(alist):
	n = len(alist)
	for j in range(1,n): #从右侧无序序列中取出多少数
		i = j  #起始值
		while i > 0:
			if alist[i]<alist[i-1]:
				alist[i],alist[i-1]=alist[i-1],alist[i]
			    i-=1
			else：         #已经有序的特殊状况
				break