Python 데이터 구조: 스 택 과 대기 열

창고
스 택 이라는 데이터 구조 에서 데이터 의 접근 은 '선진 후 출' 원칙 에 따른다.생활 에서 가장 흔히 볼 수 있 는 예 는 서랍 을 여 는 것 이다. 만약 에 서랍 이 한 줄 씩 열 려 있다 면 우 리 는 아래 에서 위로 서랍 을 열 고 위 에서 아래로 닫 을 것 이다. '먼저 들 어간 후에 나 와' 먼저 열 린 서랍 은 마지막 에 닫 을 것 이다.그리고 예 를 들 어 사람과 장 기 를 두 면 자신 이 잘못 두 었 다 는 것 을 알 게 되 고 바둑 을 뉘 우 쳐 야 하 며 실행 하 는 것 도 스 택 작업 이다.스 택 에는 두 가지 흔히 볼 수 있 는 실현 방식 이 있 습 니 다. 목록 과 링크 입 니 다.
목록 으로 스 택 구현
top 에서 창고 의 최상 위 요 소 를 지정 합 니 다.데 이 터 를 눌 러 넣 을 때마다 top + 1 데이터 가 튀 어 나 올 때마다 top - = 1

top=-1
STACK=[None]*10
def push(STACK,top,value)
    if top==9:
        print('    ')
    else:
        top+=1
        SATCK[top]=value
    return SATCK,top
def pop(STACK,top):
    if top==-1:
        print('    ')
    else:
    p=SATCK[top]
    top-=1
    return SATCK,top,p

링크 로 스 택 실현
top 은 스 택 상단 을 가리 키 고 데 이 터 를 눌 렀 을 때 새로운 데 이 터 는 top 을 가리 키 며 top 은 새로운 데 이 터 를 가리 키 고 있 습 니 다.데이터 팝 업 시 top = top. next

class Node:
    def __init__(self):
        self.value=0
        self.next=None
head=Node()
top=head
def push(top,value):
    newnode=Node()
    newnode.value=value
    newnode.next=top
    top=newnode
    return top
def pop(top):
    p=None
    if top==None:
        print('    ')
    else:
        p=top.value
        top=top.next
    return top,p

더 자세 한 설명 과 코드 는 여 기 를 클릭 하 세 요.
대열
대열 은 창고 와 달리 선진 적 인 특징 을 가지 고 있다.우리 가 줄 을 서서 물건 을 사 는 것 처럼 먼저 줄 을 서 는 사람 이 먼저 돈 을 낸다.대기 열 역시 두 가지 실현 방식 이 있 습 니 다. 목록 과 링크 입 니 다.
목록 으로 대기 열 구현
프론트 와 rear 로 각각 대기 열의 머리 와 끝 을 지정 해 야 합 니 다.데 이 터 를 눌 렀 을 때 rear + 1 이 데 이 터 를 꺼 낼 때 front + 1

front=-1
rear=-1
queue=[None]*10
def push(queue,rear,value):
    if rear==9:
        print('    ')
    else:
        rear+=1
        queue[rear]=value
    return queue,rear
def pop(queue,front,rear):
    p=None
    if front==rear:
        print('    ')
    else:
        p=queue[front]
        front+=1
    return queue,front,p

링크 로 대기 열 을 실현 하 다.
데 이 터 를 추가 할 때 front 가 존재 하 는 지 여 부 를 판단 하고 존재 하지 않 으 면 새 대기 열 을 만들어 야 합 니 다. 존재 하면 rear. next 를 새 데 이 터 를 가리 키 고 rear 를 새 데 이 터 를 가리 킵 니 다.데 이 터 를 꺼 낼 때 front 가 존재 하 는 지 여 부 를 판단 하고 존재 하면 front 를 front. next 로 가리 킵 니 다.

class Node:
    def __init__(self):
        self.value = 0
        self.next=None
rear=None
front=None
def push(value,front,rear):
    newnode=Node()
    newnode.value=value
    if front==None:
        print('       ')
        rear=newnode
        front=newnode
    else:
        rear.next=newnode
        rear=newnode
    return front,rear
def pop(front):
    if front=None:
        print('       ')
    else:
        p=front.value
        front=front.next
    return p,front

더 자세 한 설명 과 코드 는 여 기 를 클릭 하 세 요.