Python에서 스택 및 대기열 구현 방법 - 첫 번째 섹션: 스택

|
View Solution on GitHub
나는 당신이 Repl에 따라 조작하는 것을 강력히 건의합니다.이것은 너 자신의 것이다.물론 면접 때의 화이트보드에서 문법을 돋보이게 하지는 않지만, 당신이 처음 공부할 때, 나는 이것이 사물을 이해하는 데 도움이 된다고 생각한다!
여러분, 월요일 잘 보내세요!우리는 데이터 구조로 데이터 구조와 알고리즘에 관한 시리즈를 시작할 것이다. 이것은 정말 놀랍다.정확히 말하면 창고와 대열이다.대부분의 백판 문제와 마찬가지로, 아마도 당신은 영원히 공업에서 그것을 사용할 필요가 없을 것이다. 그러나 그것들은 좋은 방식이며, 당신에게 어떻게 실현하는지를 보여줄 수 있다. 즉, "한 가지 일을 하고, 당신이 알려준 일을 해라."
창고와 대기열의 개념은 상대적으로 간단하다.쌓는 것은 접시 한 무더기와 같다. 너는 항상 위의 하나를 가져가고 마지막을 잘 놓아라.너는 후진에서 먼저 이 단어를 들을 수 있을 것이다.대기열은 정반대입니다. 대기열의 첫 번째 항목은 삭제할 첫 번째 항목입니다.스타벅스에서 줄을 설 때 첫 번째 주문을 하는 고객은 항상 첫 번째로 커피를 받는 사람이라고 상상해 보세요.

IRL 스택 및 대기열(출처: insideoutstyleblog.com,koreatimes.co.kr)

파이썬으로 스택 만들기

기술 면접에서 무엇을 물어볼 수 있는지 간단하게 예를 들어 봅시다.만약 네가 집에서 따라다닌다면, Repl을 열 때가 되었다.그것

# Implement a stack that has the following methods:
# 1. push(item), which pushes an element onto the stack
# 2. pop(), which pops off and returns the topmost element of the stack. If there are no elements in the stack, then it should throw an error or return null.
# Each method should run in constant time.

그것은 단어'implement'로 시작하는데, 이것은 그들이 하나의 종류를 원한다는 것을 의미한다.만약 클래스를 사용하는 것에 익숙하지 않다면, 그것들은 본질적으로 대상의 청사진이다.클래스 Stack 로 새 대상을 초기화할 때, 클래스를 만들 때 정의된 모든 속성과 방법을 가지고 있습니다.
우리는 정의 클래스부터 시작해서 __init__ 방법을 추가할 것이다.또한 빈 방법 pop() 과 push() 을 추가합니다.키워드pass는 파이썬이 우리가 빈 방법이 있다고 불안해하지 않도록 하기 위한 것이다.

class Stack:
    def __init__():
        pass

    def pop():
        pass

    def push():
        pass

좋아, 지금 우리는 Stack반이 하나 있어.초기화할 때 창고의 모든 속성을 확인하는 __init__ 방법을 정의합니다.1. 예를 들어 새로운 창고가 탄생할 때마다 우리는 그것을 준다.뭐 공부 해요?
스택은 본질적으로 특수한 속성을 가진 목록입니다. (Python에서 그룹을'목록'이라고 부른다는 것을 기억하십시오.) 가장 가까운 요소만 추가하거나 삭제할 수 있습니다.그래서 우리는 그것을 하나의 목록으로 표시한다. 나는 stack라고 부른다.파이썬에서 클래스의 속성을 정의하기 위해 self 키워드를 사용합니다.키워드에 액세스하려면 매개변수로 전달해야 합니다.

def __init__(self):
    self.stack = []

네, 계속 push() 방법을 봅시다.이것 또한 self 을 매개 변수로 받아들일 것이기 때문에 우리는 방금 정의한 stack 변수에 접근할 수 있다.또한 스택 상단에 추가할 item 하나를 포함합니다.

def push(self, item):
    pass

창고에서 항목을 추가하고 삭제하기 위해서, 목록의 끝을 맨 위로 상상합니다.이것은 Python의 일을 간단하게 합니다. 왜냐하면 우리는 다음과 같이 목록의 끝에 항목을 추가할 수 있기 때문입니다.

def push(self, item):
    self.stack.append(item)

.append() 방법은 유사할 것이다.Python에는 목록의 마지막 요소를 삭제하는 데 사용되는 pop() 방법이 있습니다.실용적이 방법은 삭제된 요소를 되돌려주기 때문에 .pop() 라는 국부 변수에 저장하고 되돌려줍니다.

def pop(self):
    removed = self.stack.pop()
    return removed

근데 잠깐만!문제가 있습니다.만약 창고에 삭제할 항목이 없다면 어떻게 해야 합니까?다행히도 힌트는 우리에게 이 잠재적인 함정을 일깨워 주었다.

# If there are no elements in the stack, then it should throw an error or return null.

그래서 우리가 해야 할 일은 조건문을 추가해서 이 가장자리 상황을 검사하는 것이다.이를 위해, 목록을 실행하기 removed 전에, 창고가 비어 있는지 확인하기 위해if문장을 추가하면 됩니다.Python에서 유일한null 형식은 .pop 이기 때문에 이 예에서 우리는 그것을 되돌려 줍니다.

def pop(self):
    if len(self.stack) == 0:
        return None
    removed = self.stack.pop()
    return removed

이렇게!개요:
창고회사 명

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, item):
        self.stack.append(item)

    def pop(self):
        if len(self.stack) == 0:
            return None
        removed = self.stack.pop()
        return removed

또 하나 주의해야 할 것은 우리의 해결 방안은 모든 방법이 정해진 시간 O(1)에서 실행되는 제약을 따른다는 것이다.이것은 창고의 길이가 어떻든지 간에 그것들이 같은 시간에 운행한다는 것을 의미한다.예를 들어, 순환 목록이 필요한 경우 시간 복잡도는 O(N), N은 목록의 길이입니다.하지만 우리는 없다. 그래서 우리는 매우 좋다.

우리의 창고를 테스트하다

Repl에서 계속 팔로우하고 있을 수 있습니다.지금까지 잘했어.하지만 이 프로그램을 실행하면 아무 일도 일어나지 않는다는 것을 알게 될 것이다.

(출처: imgur.com)
내가 말한 바와 같이 유형은 대상의 청사진과 같다.우리는 대상을 만들어서 그것을 테스트하도록 청사진을 그렸다.Python 셸(Repl.it의 터미널 출력)이나 스택 아래에서 이 작업을 수행할 수 있습니다.py 파일.간단하게 보기 위해서, 나는 창고를 None 라고 명명했다.

>>> s = Stack()

이제 창고에 숫자를 추가해서 우리가 작성한 예쁜 s 방법을 테스트해 봅시다.

>>> s.push(1)
>>> s.push(2)
>>> s.push(3)

만약 우리가 인쇄 push() 를 한다면, 우리는 반드시 s.stack 를 받아야 한다.너무 좋아요.우리 [1, 2, 3] 방법을 시험해 봅시다.

>>> s.pop()

현재, 만약 우리가 인쇄 pop() 를 한다면, 우리는 반드시 s.stack 를 받아야 한다.마지막 항목만 삭제되고 값 3이 반환되었습니다.그러나 만약 우리가 계속 원소를 삭제한다면 무슨 일이 일어날까요?우리는 같은 명령을 여러 번 실행한 후에 되돌아오는 값을 인쇄해서 우리의 방법이 되돌아오는지 테스트할 수 있다[1, 2].

>>> s.pop()
>>> s.pop()
>>> print(s.pop())

이것이 바로 Python으로 이루어진 창고입니다.첫 번째 데이터 구조를 정식으로 배웠습니다.

이점: 통합 max() 방법

내가 발견한 견본 문제는 분명히 아마존과의 인터뷰에서 제기된 것이다. 이것은 별도의 방법이 필요하다.

# 3. max(), which returns the maximum value in the stack currently. 
# If there are no elements in the stack, then it should throw an error or return null.

Stack 클래스가 제대로 작동하려면 Stack 클래스를 변경해야 합니다.None부터 시작합시다.스택의 최대 값을 추적하기 위해 변수 __init__ 를 추가합니다.창고가 비어 있으면null 값을 되돌려줍니다. 따라서 max 로 초기화합니다.

def __init__(self):
    self.stack = []
    self.max = None

쿨, 이제 None 방법을 업데이트합시다.우리는 두 가지 상황을 검사해야 한다.

스택에 추가할 첫 번째 항목인 경우이 예에서 push() 은 현재 max 이며, 추가할 첫 번째 값으로 초기화해야 합니다.

만약 None 값이 이미 있다면, 우리는 그것을 추가하고 있는 항목과 비교하고 업데이트해야 한다.

이 두 가지 상황에서, 우리는 추가 중인 항목에 대해 새로운 max 값을 설정할 것입니다.따라서 한 줄max 문장으로 이 점을 할 수 있다.

def push(self, item):
    self.stack.append(item)
    if len(self.stack) == 1 or item > self.max:
        self.max = item

다음은 우리 or 를 봅시다.마찬가지로 우리는 두 가지 상황을 검사해야 한다.

제거할 항목이 스택의 마지막입니다.현재 창고가 비어 있으니, pop() 를 max 로 설정해야 합니다.

삭제하려는 항목이 최대값과 같으면 목록을 훑어보고 새 값을 찾아야 합니다.

첫 번째 상황은 간단하다.목록에 있는 None 을 호출한 후에 길이가 현재 0인지 확인합니다.

if len(self.stack) == 0:
    self.max = None

두 번째 상황에 대해 우리는 .pop() 순환을 사용할 것이다.우리는 먼저 for 스택에 이미 존재하는 값을 알기 위해 설정합니다. 첫 번째 값입니다.그리고 이 목록을 순환해서 대조해서 값을 검사하고 업데이트합니다.

elif removed == self.max:
  self.max = self.stack[0]
  for value in self.stack:
    if value > self.max:
      self.max = value

마지막으로, 우리는 창고에서 삭제한 값을 되돌려줍니다.이 방법은 다음과 같습니다.

def pop(self):
    if len(self.stack) == 0:
        return None
    removed = self.stack.pop()
    if len(self.stack) == 0:
        self.max = None
    elif removed == self.max:
        self.max = self.stack[0]
        for value in self.stack:
            if value > self.max:
                self.max = value
    return removed

마지막으로 광고에서 언급한 max 방법을 실현합시다.이 방법의 목적은 단지 우리가 정의한 max() 값을 되돌려 주는 것이다.그러나 Python에서는 클래스 정의 이외의 값을 호출할 수 있습니다 max.왜 우리는 그것을 되돌릴 온전한 방법을 작성해야 합니까?
이것은 Java에서 대상을 대상으로 프로그래밍하는 또 다른 문제입니다.전통적으로 모든 변수를 사유화하는 것이 가장 좋다.만약 네가 라디오를 만들고 있다면, 너는 사용자가 안의 전선을 어지럽히는 것을 원하지 않을 것이다. 단지 바깥의 스위치와 단추를 어지럽히고 싶을 뿐이다.Java에서는 키워드s.max 초기화max 필드를 사용할 수 있습니다.그런 다음 private 또는 max 이라는 방법을 만들어서 값을 되돌려줍니다. 그렇지 않으면 이 값에 접근하는 유일한 방법입니다.
변수를Python에서 사유화할 수 있는 방법은 두 개의 밑줄 ('dunder'가 당신의 책벌레에게) 으로 정의하기만 하면 된다.get_max().이것은 네가 이렇게 하려고 하느냐 안 하느냐에 달려 있다.면접에서 가장 좋은 방법은 면접관에게 무엇을 원하는지 물어보는 것이다.사실, 당신의 요구는 당신이 똑똑하고 통찰력이 있다는 것을 의미하며, 그리고 그들에게 원하는 것을 줄 수 있다는 것을 의미한다.
개요:
창고회사 명

class Stack:
  def __init__(self):
    self.stack = []
    self.max = None

  def pop(self):
    if len(self.stack) == 0:
      return None
    removed = self.stack.pop()
    if len(self.stack) == 0:
      self.max = None
    elif removed == self.max:
      self.max = self.stack[0]
      for value in self.stack:
        if value > self.max:
          self.max = value
    return removed

  def push(self, item):
    self.stack.append(item)
    if len(self.stack) == 1 or item > self.max:
      self.max = item

  def get_max(self):
    return self.max

여기 있다!max가 올바르게 업데이트되었는지 확인하기 위해 요소를 추가하고 삭제하는 것을 테스트할 수 있습니다.

>>> s = Stack()
>>> s.push(1)
>>> s.push(2)
>>> s.push(3)
>>> s.max
3
>>> s.pop()
3
>>> s.max
2

자, 여러분, 이번 주까지 여기까지.파이썬에서 정의한 클래스의 작업 방식을 깊이 있게 이해하고 데이터 구조를 이해할 수 있기를 바랍니다.우리는 다음 주에 대열을 실현하기 위해 돌아올 것이다.읽어줘서 고마워요. 그때 봐요!
|
View Solution on GitHub
Sheamus Heikkila는 예전에 시애틀 대회의 조교였다.이 블로그는 GA와 무관합니다.