編寫一個類，具有棧和隊列的功能。實現以下4個方法：

shit()?????? 返回并刪除列表中第一個元素

unshit()?? 在列表的頭部‘壓入’一個新的元素

push()??? 在列表尾部增加一個元素

pop()????? 返回并刪除最后一個元素

outAllData() 輸出所有的數據

class stackAndQueue(object):data = []def isEmpty(self):return len(self.data)==0def shift(self):if stackAndQueue.isEmpty(self):print 'the operator is illegal'else :ret = self.data[0]del self.data[0]return retdef unshift(self, val):self.data.insert(0, val)def push(self, val):self.data.append(val)def pop(self):if stackAndQueue.isEmpty(self):print 'the operator is illegal' else : return self.data.pop()def outAllData(self):print ' '.join( map(str, self.data) )

快速排序：

def quickSort(num):if num == []:return []n = len(num)return quickSort([num[i] for i in xrange(1, n) if num[i]<=num[0] ]) + [num[0]] + quickSort([num[i] for i in xrange(1, n) if num[i]>num[0] ])def main():l1 = [9, 8, 7, 5, 4, 1, 7, 56, 34]l2 = quickSort(l1)print l1print l2if __name__ == '__main__':main()

?選擇排序：

def selection_sort(L):Len = len(L)for i in xrange(Len):smallest = find_min(L, i)L[i], L[smallest] = L[smallest], L[i]def find_min(L, b):smallest = bLen = len(L)for i in xrange(b, Len):if L[i] < L[smallest]:smallest = ireturn smallestdef main():l1 = [6, 5, 4, 3, 2, 2, 9, -3, 56]print 'before sort ', l1selection_sort(l1)print 'after sort ',l1if __name__ == '__main__':main()

?插入排序

def insertion_sort(L):Len = len(L)for i in xrange(1,Len):insert(L, i)def insert(L, b):Len = len(L)i = bwhile (L[i-1] > L[i]) and (i-1>=0):L[i-1], L[i] = L[i], L[i-1]i-= 1def main():l1 = [6, 5, 4, 3, 2, 2, 9, -3, 56]print 'before sort ', l1insertion_sort(l1)print 'after sort ',l1if __name__ == '__main__':main()

另外一個版本，使用bisect模塊實現。bisect模塊有以下幾個方法: 這些方法返回的都是位置信息

bisect(x) 默認是bisect_right(a, x)

bisect_left(a, x)? 在有序序列里查找第一個大于x的位置，如果有與x相同的元素，則返回與x相等元素中最左邊的那個位置

bisect_right(a, x) 在有序序列里查找第一個大于x的位置，如果有與x相同的元素，則返回與x相等元素中最右邊的那個位置

insort 默認是insort_right(a, x)

insort_left(a, x)?? 在有序序列里插入x，如果有與x相同的元素，則當前元素插入在這些相同元素的最左邊

insort_right(a, x) 在有序序列里插入x，如果有與x相同的元素，則當前元素插入在這些相同元素的最右邊

import bisect
def bin_sort(values):'''sort values , creating a new list'''result = []for v in values:bisect.insort_left(result, v)return resultdef main():l1 = [6, 5, 4, 3, 2, 2, 9, -3, 56]print 'before sort ', l1l1=bin_sort(l1)print 'after sort ',l1if __name__ == '__main__':main()

合并排序(遞歸版)

def mergesort(L):if len(L) < 2: return Lmid = (len(L))>>1L1 = mergesort(L[:mid])L2 = mergesort(L[mid:])return merge(L1, L2)def merge(L1, L2):newL = []i1 = i2 =0Len1, Len2 =len(L1), len(L2)while i1!=Len1 and i2!=Len2:if L1[i1] <= L2[i2]:newL.append(L1[i1])i1 += 1else :newL.append(L2[i2])i2 += 1newL.extend(L1[i1:])newL.extend(L2[i2:])return newLdef main():l1 = [6, 5, 4, 3, 2, 2, 9, -3, 56]print 'before sort ', l1l1=mergesort(l1)print 'after sort ',l1if __name__ == '__main__':main()

合并排序(非遞歸版)

def mergesort(L):

''' segNum 未合并的序列數 segLength 每個序列的長度，不包括最后那段 lastSegLength 最后那短的長度，這個是不確定的 '''segNum, segLength, lastSegLength = len(L), 1, 1while segNum > 1:tmp_segNum = segNumsegNum >>= 1tmp_segLength = segLength<<1if tmp_segNum&1:j = 0for i in xrange(segNum):merge(L, j, j+segLength,j+tmp_segLength)j += tmp_segLengthj = len(L)-lastSegLength-tmp_segLength+1merge(L, j, j+tmp_segLength, len(L))else :j = 0for i in xrange(segNum):if i != (segNum-1):merge(L, j, j+segLength, j+tmp_segLength)else :merge(L, j, j+segLength, len(L))j += tmp_segLengthlastSegLength += segLengthsegLength = tmp_segLengthdef merge(L, s, mid, t): tmp = []i1, i2 = s, midwhile i1!=mid and i2!=t:if L[i1]<=L[i2]:tmp.append(L[i1])i1 += 1else :tmp.append(L[i2])i2 += 1tmp.extend(L[i1:mid])tmp.extend(L[i2:t])for i in xrange(t-1, s-1, -1):L[i] = tmp.pop()def main():l1 = [6, 5, 4, 3, 2, 2, 9, -3, 56]print 'before sort ', l1mergesort(l1)print 'after sort ', l1if __name__ == '__main__':main()

?表達式的計算，帶括號：

ss = raw_input().strip() Len = len(ss) info, sign = [], []def isdigit(x):return True if ord('0')<=ord(x)<=ord('9') else Falsedef count():b, a = info.pop(), info.pop()op = sign.pop()if op=='+': a += belif op=='-': a -= belif op=='*': a *= belif op=='/': a /= binfo.append(a)i = 0 while i < Len:if isdigit(ss[i] ):tmp = 0while i<Len and isdigit(ss[i]) : tmp = tmp*10 + ord(ss[i])-ord('0'); i+=1i-=1; info.append(tmp)elif ss[i]=='(': sign.append(ss[i])elif ss[i]==')':while sign and sign[-1]!='(': count()sign.pop()elif ss[i]=='+' or ss[i]=='-':while sign and sign[-1]!='(': count()sign.append(ss[i])elif ss[i]=='*' or ss[i]=='/':while sign and sign[-1]!='(' and sign[-1]!='+' and sign[-1]!='-': count()sign.append(ss[i])i += 1while sign: count() print info[0]

?

?

轉載于:https://www.cnblogs.com/TengXunGuanFangBlog/archive/2013/05/19/python_lian_xi.html

總結

以上是生活随笔為你收集整理的python 栈和队列 排序 初级数据结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。