본문 바로가기
STUDY/코딩공부

[Python] Stack과 Queue

by 램플릿 2025. 4. 2.

 

개념

 

구분 Stack (Last-in, First-out) Queue (First-in, First-out)
리스트의 종류 Array List Linked List
활용 페이지 뒤로가기(이전상태 되돌리기), 수식의 괄호 검사 프린터 인쇄 대기열, 운영체제 작업 스케줄링
명칭 Top(또는 Peek) : 가장 마지막에 들어온 상단의 데이터
Pop : 데이터 제거
Push(또는 Append) : 데이터 추가		 front와 rear : 큐의 데이터가 위치한 머리부분을 프론트, 꼬리부분을 리어라고 한다.
enqueue와 dequeue : 데이터가 들어오는 곳을 인큐, 제거되는 곳을 디큐라고 한다.

 

* Queue를 만들 때 Array를 쓰지 않는 이유 : 데이터의 삭제 시 삭제 작업과 데이터를 앞으로 당겨주는 재배치 작업까지 총 2번을 작업해야 하므로 시간복잡도가 비효율적으로 되기 때문이다.

#스택 선언
stack = []

#push
stack.append(1)
stack.append(2)
stack.append(4)

#pop
stack.pop()

 

 

파이썬의 데크(Deque) : 양끝 어느 쪽에서든 데이터의 추가/삭제가 가능한 자료구조

from collecitons import deque

#queue 선언
queue = deque()

#enqueue
queue.append(1)
queue.append(2)
queue.append(4)

#dequeue
queue.popleft()

 

 

문제 풀이

 

[문제] 괄호 유효성 검사 () {} []

문자열 s가 주어지면 (1)열린 괄호가 동일한 유형의 괄호로 닫혔는지, (2)올바른 순서로 닫혔는지 검사하여 true/false를 출력한다.

 

==== 테스트케이스 ====

test_cases = [
    "()",
    "()[]{}",
    "(]",
    "([)]",
    "{[]}"
]
#예상결과 : T T F F T

 

==== 함수 정의 ====

class Solution(object):
  def isValid(self, s):
    stack = []	#stack 선언, 빈 리스트로 초기화
    #괄호 쌍을 저장한 pairs딕셔너리
    pairs = {
      '(':')',
      '{':'}',
      '[':']'
    }

    for bracket in s:	#문자열 s에서 문자를 하나씩 꺼내어 bracket에 저장
      if bracket in pairs:	#bracket이 여는 괄호인지 체크
        stack.append(bracket)	#여는 괄호를 스택에 추가
      elif len(stack) == 0 or bracket != pairs[stack.pop()]:
      #스택 길이가 0이거나(예:스택에 여는괄호가 없는데 닫는괄호만 올 경우),
      #유효하지 않은(짝이 안맞는) 닫는괄호라면 False를 반환
      #stack.pop() - 가장 최근에 저장된 키값(여는 괄호)
      #pairs[stack.pop()] - 여는 괄호와 짝이 맞는 닫는 괄호
        return False

    return len(stack) == 0
    #스택이 비어있다면 len(stack)==0는 True,
    #스택에 여는 괄호가 남아있다면 len(stack)==0는 False를 반환

 

==== 출력 ====

sol = Solution()
for s in test_cases:
  print(f"'{s}':{sol.isValid(s)}")

 

 

 

- 스택이 비어 있다는 것은 모든 여는 괄호에 대해 짝이 맞는 닫는 괄호가 존재했다는 뜻이다. 즉, 괄호 쌍이 올바르게 짝을 이뤘다는 의미이다. → True 반환
- 만약 스택에 여는 괄호가 남아 있으면, 그만큼 짝이 맞지 않은 괄호가 있다는 의미로 False가 반환된다.

 

 

 

파이썬 문법 알아보기

 

  def - 함수 정의 키워드. 사용자 정의 함수를 작성하기 위해 사용된다.


  self - 이 함수가 클래스 안에 정의되어 있을 때, 메서드가 속한 객체 자신(=클래스의 인스턴스) 을 가리키는 참조. this와 비슷한 느낌으로 이해하면 된다.

 

  f-string - 파이썬의 문자열 포매팅 방법. 문자열 안에 변수를 직접 삽입할 수 있게 해준다.

self는 왜 필요한가?

self를 사용함으로써 각 인스턴스가 자기 자신을 참조할 수 있습니다. 클래스에서 정의된 속성(인스턴스 변수)이나 메서드를 인스턴스별로 다르게 사용할 수 있도록 만들어줍니다.

self와 클래스의 관계

  • self는 인스턴스 메서드를 정의할 때 그 메서드가 호출된 객체를 가리킵니다.
  • 클래스 자체의 속성에 접근하려면 cls를 사용하는 클래스 메서드를 사용합니다. self는 인스턴스 메서드에서만 사용됩니다.

클래스와 인스턴스 메서드

  • 인스턴스 메서드는 인스턴스를 기반으로 동작합니다. self를 통해 인스턴스의 속성에 접근하고 변경할 수 있습니다.
  • 클래스 메서드는 cls를 첫 번째 인자로 받으며, 클래스 자체에 대한 작업을 할 수 있습니다. 이 메서드는 인스턴스 없이 클래스에서 호출할 수 있습니다.
  • ↓ 예시: 클래스 메서드
class MyClass:
    count = 0  # 클래스 변수

    def __init__(self, name):
        self.name = name
        MyClass.count += 1  # 클래스 변수에 접근

    @classmethod
    def get_count(cls):  # 'cls'는 클래스를 참조
        return cls.count

obj1 = MyClass("Alice")
obj2 = MyClass("Bob")

print(MyClass.get_count())  # 2가 출력됩니다. 클래스 변수 'count'는 2

 

결론

  • self는 인스턴스 메서드를 정의할 때 필수적으로 사용되는 매개변수입니다. self는 클래스의 현재 인스턴스를 참조하는 역할을 합니다.
  • self라는 이름은 파이썬의 관례이기 때문에, 반드시 self를 사용해야 합니다. 그러나 다른 이름을 사용하더라도 파이썬은 이를 허용합니다. 다만, 일관성을 위해 self를 사용하는 것이 좋습니다.

f-string의 사용법:

f-string을 사용하려면 문자열 앞에 f를 붙입니다. 그리고 중괄호 {} 안에 변수나 표현식을 넣으면, 해당 값이 문자열 안에 삽입됩니다.

예시:

name = "Alice"
age = 25
print(f"Name: {name}, Age: {age}")

 

출력 결과:

Name: Alice, Age: 25

f-string의 장점:

  1. 가독성: 문자열 안에 변수를 삽입할 때 다른 방법들보다 더 직관적이고 가독성이 좋습니다.
  2. 편리함: 중간에 변수를 넣거나 복잡한 표현식을 쉽게 삽입할 수 있습니다.

f-string 외의 다른 문자열 포매팅 방법:

% 연산자 (구식 방식):이 방식은 파이썬 2에서 유래한 방법으로, %s는 문자열, %d는 숫자 등을 의미합니다.

name = "Alice"
age = 25
print("Name: %s, Age: %d" % (name, age))

 

str.format() (파이썬 2.7 이상에서 사용 가능):

name = "Alice"
age = 25
print("Name: {}, Age: {}".format(name, age))

 

f-string을 사용한 코드 예시:

test_case = "()[]{}"
print(f"Input: {test_case} -> Valid: {isValid(test_case)}")

이 예시에서:

  • f"Input: {test_case} -> Valid: {isValid(test_case)}"는 test_case와 isValid(test_case)의 값을 문자열 안에 바로 넣을 수 있게 해주는 f-string입니다.
  • {test_case}는 test_case 변수의 값 ()[]{} 을, {isValid(test_case)}는 isValid(test_case) 함수의 반환값 True 을 그 자리에 삽입합니다.

결론:

f는 문자열 포매팅을 편리하게 하기 위해 사용되며, 변수를 문자열에 삽입할 때 가독성 좋고 효율적인 방법을 제공합니다.

class Solution(object):과 class Solution:의 차이점

먼저, class Solution(object):와 class Solution:은 사실상 차이가 있을 수 있습니다, 그러나 대부분의 경우 이 두 가지 구문은 동일하게 동작합니다. 이 차이점은 주로 Python 2.x와 Python 3.x의 차이점에 관련이 있습니다.

 

1. class Solution(object): 의 의미:

class Solution(object):는 Python 2.x와 Python 3.x에서의 차이점 때문입니다. object를 명시적으로 상속받으면, 클래스가 새로운 스타일 클래스로 정의됩니다.

  • 새로운 스타일 클래스 (New-style class)는 Python 2.x에서 도입되었으며, Python 3.x에서는 기본적으로 새로운 스타일 클래스를 사용합니다.
  • object를 상속받은 클래스는 여러 가지 내장 메서드(예: __new__, __init__, __del__, __str__, __repr__, 등)나 메타클래스를 사용할 수 있는 장점이 있습니다.

따라서, class Solution(object):는 Python 3.x에서도 가능하지만, Python 2.x에서는 object를 상속받지 않으면 구식 스타일 클래스 (old-style class)로 동작하므로, object를 명시적으로 상속받는 것이 좋습니다.

2. class Solution: 의 의미:

class Solution:에서 object를 명시하지 않으면, Python 3.x에서는 기본적으로 새로운 스타일 클래스가 되기 때문에, 실제로 object를 상속하지 않더라도 class Solution:은 Python 3에서 새로운 스타일 클래스와 동일하게 동작합니다. 하지만 Python 2.x에서는 object를 명시적으로 상속받지 않으면 구식 스타일 클래스가 됩니다.

따라서 Python 3.x에서는 class Solution:만 써도 새로운 스타일 클래스가 되지만, Python 2.x에서는 object를 명시적으로 상속해야 새로운 스타일 클래스로 동작합니다.

3. 차이점:

  • Python 3.x에서는 class Solution:과 class Solution(object):이 실질적으로 동일하게 동작합니다. object를 명시적으로 상속하지 않아도 새로운 스타일 클래스가 됩니다.
  • Python 2.x에서는 class Solution:만 작성하면 구식 스타일 클래스가 됩니다. 이 경우, object를 상속하여 class Solution(object):로 작성해야 새로운 스타일 클래스로 동작합니다.

4. Python 3에서 왜 object를 사용하는가?

Python 2는 2020년 1월 1일에 공식 지원이 종료되었기 때문에, 많은 개발자가 Python 3으로 마이그레이션을 해야 했습니다. Python 3에서 object를 명시적으로 상속하는 것은 호환성과 일관성을 위해 사용되며, 코드의 가독성을 높이고, Python 2.x에서 Python 3.x로의 마이그레이션을 고려할 때 유용합니다.

결론:

  • Python 3.x에서는 class Solution:만 사용해도 동일한 결과를 얻을 수 있지만, class Solution(object):를 사용하는 것이 호환성과 일관성을 유지하는 데 좋습니다.
  • Python 2.x에서는 object를 명시적으로 상속해야 새로운 스타일 클래스를 사용할 수 있습니다.

따라서, class Solution(object):는 Python 2.x에서 새로운 스타일 클래스를 정의하기 위한 방법이고, Python 3.x에서는 단순히 class Solution:만 써도 동일한 결과를 얻습니다.

티스토리툴바