Python数据结构——栈、队列的实现(一)

栈(Stack)是限制插入和删除操作只能在一个位置进行的表，该位置是表的末端，称为栈的顶(top)。栈的基本操作有PUSH(入栈)和POP(出栈)。栈又被称为LIFO(后入先出)表。

1.1 栈的实现

class Stack(object):
    def __init__(self):
        self.stack=[]
    def isEmpty(self):
        return self.stack==[]
    def push(self,item):
        self.stack.append(item)
    def pop(self):
        if self.isEmpty():
            raise IndexError,&＃39;pop from empty stack&＃39;
        return self.stack.pop()
    def peek(self):
        return self.stack[-1]
    def size(self):
        return len(self.stack)

1.2 栈应用

1.2.1 检查程序中成对的符号

程序的语法错误经常是由缺少一个符号造成的。可用栈来检查符号是否成对。做一个空栈，如果字符是开放符号(&＃39;({[&＃39;)则将其push栈中。如果符号是个闭合符号(&＃39;)]}&＃39;),则当栈空时报错，对应&＃39;()}&＃39;的错误。否则，将栈pop，如果弹出的符号不是对应的开放符号，则报错，对应&＃39;(}&＃39;的错误。文件末尾，如果栈为空，则报错，对应&＃39;({}&＃39;的错误。

def match(i,j):
    opens=&＃39;([{&＃39;
    closes=&＃39;)]}&＃39;
    return opens.index(i)==closes.index(j)
def syntaxChecker(string):
    stack=Stack()
    balanced=True
    for i in string:
        if i in &＃39;([{&＃39;:
            stack.push(i)
        elif i in &＃39;)]}&＃39;:
            if stack.isEmpty():
                balanced=False
                break
            else:
                j=stack.pop()
                if not match(j,i):
                    balanced=False
                    break
    if not stack.isEmpty():
        balanced=False
    return balanced

1.2.2 进制转换

十进制转换二进制：把十进制转成二进制一直分解至商数为0。从最底左边数字开始读，之后读右边的数字，从下读到上。

来自《PRoblem Solving with Algorithms and Data Structures》的图片：

代码：

def decimal_to_bin(dec):
    stack=Stack()
    cur=dec
    while cur>0:
        a=cur%2
        cur=cur/2
        stack.push(a)
    binstr=&＃39;&＃39;
    while not stack.isEmpty():
        binstr+=str(stack.pop())
    return binstr

1.2.3 后缀记法

后缀记法(postfix)，使用一个栈，见到一个数时入栈，遇到一个运算符时就作用于从栈弹出的两个元素，将结果弹入栈中。

(7+8)/(3+2)可以写作7 8 + 3 2 + /

来自《Problem Solving with Algorithms and Data Structures》的图片：

def infixtoPostfix(infix):
    a={}
    a[&＃39;*&＃39;]=3
    a[&＃39;/&＃39;]=3
    a[&＃39;+&＃39;]=2
    a[&＃39;-&＃39;]=2
    a[&＃39;(&＃39;]=1
    stack=Stack()
    post=&＃39;&＃39;
    for i in infix:
        if i not in a and i!=&＃39;)&＃39;:
            post+=i
        elif i==&＃39;(&＃39;:
            stack.push(i)
        elif i==&＃39;)&＃39;:
            top=stack.pop()
            while top!=&＃39;(&＃39;:
                post+=top
                top=stack.pop()
        else:          
            while not stack.isEmpty() and a[i]<=a[stack.peek()]:
                post+=stack.pop()
            stack.push(i)
    while not stack.isEmpty():
        post+=stack.pop()
    return post
                   
def postfixExp(postfix):
    stack=Stack()
    postlist=postfix.split()
    for i in postlist:
        if i not in &＃39;+-*/&＃39;:
            stack.push(i)
        else:
            a=stack.pop()
            b=stack.pop()
            result=math(i,b,a)
            stack.push(result)
    return stack.pop()
def math(x,y,z):
    if x==&＃39;+&＃39;:
        return float(y)+float(z)
    if x==&＃39;-&＃39;:
        return float(y)-float(z)
    if x==&＃39;*&＃39;:
        return float(y)*float(z)
    if x==&＃39;/&＃39;:
        return float(y)/float(z)

2 队列

队列(queue)也是表，使用队列时插入和删除在不同的端进行。队列的基本操作是Enqueue(入队)，在表的末端(rear)插入一个元素，还有出列(Dequeue)，删除表开头的元素。

class Queue(object):
    def __init__(self):
        self.queue=[]
    def isEmpty(self):
        return self.queue==[]
    def enqueue(self,x):
        self.queue.append(x)
    def dequeue(self):
        if self.queue:
            a=self.queue[0]
            self.queue.remove(a)
            return a
        else:
            raise IndexError,&＃39;queue is empty&＃39;
    def size(self):
        return len(self.queue)

以上就是Python数据结构——栈、队列的实现(一)的内容，更多相关文章请关注PHP中文网（www.php1.cn）！