Python 데이터 구조 - 스택 및 큐 구현 (1)

1. 스택

스택은 삽입 및 삭제 작업을 한 위치로만 제한하는 테이블입니다. 이 위치는 테이블의 끝이며 스택의 상단이라고 합니다. 스택의 기본 작업은 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,'pop from empty stack'
        return self.stack.pop()
    def peek(self):
        return self.stack[-1]
    def size(self):
        return len(self.stack)

1.2 스택 응용

1.2.1 프로그램에서 쌍을 이루는 기호를 확인하세요.

프로그램의 구문 오류는 다음과 같습니다. 종종 기호 누락으로 인해 발생합니다. 스택을 사용하여 기호가 쌍을 이루는지 확인할 수 있습니다. 빈 스택을 만듭니다. 문자가 열린 기호('({['))인 경우 해당 기호가 닫힌 기호(')]}')인 경우 스택에 오류가 보고됩니다. 비어 있으며 '()}' 오류에 해당합니다. 그렇지 않으면 팝된 기호가 해당 열린 기호가 아닌 경우 '(}' 오류에 해당하는 오류가 보고됩니다. 파일 끝에서 스택이 비어 있으면 오류가 발생합니다. '({}' 오류에 해당합니다.

def match(i,j):
    opens='([{'
    closes=')]}'
    return opens.index(i)==closes.index(j)
def syntaxChecker(string):
    stack=Stack()
    balanced=True
    for i in string:
        if i in '([{':
            stack.push(i)
        elif i in ')]}':
            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이 될 때까지 십진수를 이진수로 변환합니다. 읽기 시작 왼쪽 아래 숫자부터 읽어보세요.

알고리즘을 이용한 문제 해결에서 시작해서 오른쪽 숫자를 읽어보세요. 데이터 구조" 그림:

코드:

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

1.2.3 접미사 표기

후위 표기법(postfix)은 ​​스택을 사용합니다. 숫자를 보면 스택에 푸시됩니다. 연산자를 만나면 스택에서 팝된 두 요소에 대해 작동하고 결과를 스택에 팝합니다.

(7+8)/(3+2)는 7 8 + 3 2 + /

"알고리즘 및 데이터 구조를 사용한 문제 해결"의 그림:

중위에서 접미사로 변환: 피연산자를 읽으면 출력에 넣습니다. 연산자 (+,-,*,/)를 읽을 때 스택이 비어 있으면 스택에 푸시하고, 그렇지 않으면 스택 요소를 팝하여 우선 순위가 낮은 요소를 찾을 때까지 출력에 넣습니다. '('를 읽은 후 스택에 푸시하고, ')'를 읽으면 스택 요소를 팝하고 '('를 찾을 때까지 출력으로 보냅니다. 마지막에는 스택이 빌 때까지 스택 요소를 팝합니다.

"알고리즘과 데이터 구조를 이용한 문제 해결"의 사진:

def infixtoPostfix(infix):
    a={}
    a['*']=3
    a['/']=3
    a['+']=2
    a['-']=2
    a['(']=1
    stack=Stack()
    post=''
    for i in infix:
        if i not in a and i!=')':
            post+=i
        elif i=='(':
            stack.push(i)
        elif i==')':
            top=stack.pop()
            while top!='(':
                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

Queue(queue)도 테이블, 사용 큐 삽입과 삭제는 서로 다른 끝에서 수행됩니다. 큐의 기본 작업은 테이블 끝(후면)에 요소를 삽입하는 Enqueue(enqueue)와 해당 요소를 삭제하는 Dequeue(Dequeue)입니다. 🎜>

위는 Python 데이터 구조 - 스택 및 큐 구현 내용입니다. (1) 관련 기사를 더 보려면 PHP 중국어 웹사이트(www.php.cn)를 참고하세요. )

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,'queue is empty'
    def size(self):
        return len(self.queue)