파이썬 스택: 정의, 구현 및 예제

홈 » Python » 파이썬 스택: 정의, 구현 및 예제

파이썬에서 스택은 실제 프로그램의 내부를 살펴보면 곳곳에서 계속해서 등장하는 핵심 개념 중 하나입니다. 함수 호출부터 에디터의 실행 취소 기능, 브라우저의 탐색 기록 처리 방식까지, 스택은 매우 다양한 기능을 제공합니다. 비록 주로 고수준 애플리케이션 코드를 작성하더라도, 스택의 작동 원리(그리고 파이썬에서 스택을 제대로 구현하는 방법)를 이해하는 것은 까다로운 문제를 디버깅하거나 효율적인 알고리즘을 설계할 때 큰 도움이 됩니다.

이 가이드에서는 스택이란 무엇인지, "후입선출(LIFO)"이 실제로 무엇을 의미하는지, 모든 스택이 지원해야 하는 연산은 무엇인지, 그리고 리스트, collections.deque, queue.LifoQueue, 단일 연결 리스트와 같은 다양한 도구를 사용하여 파이썬에서 스택을 구현하는 방법을 자세히 살펴보겠습니다.또한 성능, 메모리 동작, 스레드 안전성 및 스택이 바로 적합한 데이터 구조인 실제 시나리오에 대해서도 논의할 것입니다.

파이썬에서 스택이란 무엇인가요?

스택은 후입선출(LIFO) 규칙을 따르는 선형 데이터 구조입니다. 스택에 마지막으로 푸시된 요소가 가장 먼저 꺼내집니다.개념적으로 접시 더미, 책 더미, 옷 더미를 떠올려 보세요. 맨 위에서만 물건을 넣거나 뺄 수 있고, 중간이나 맨 아래에서는 넣거나 뺄 수 없습니다.

이 LIFO(Last In First Out) 방식은 요소를 삽입(푸시)할 때 새 요소가 이전 요소 위에 놓이고, 요소를 제거(팝)할 때는 항상 가장 최근에 추가된 요소가 제거됨을 의미합니다.위에 있는 요소들을 제거하지 않고 세 번째나 네 번째 요소에 바로 도달하기 위해 "건너뛰기"를 해서는 안 됩니다.

파이썬에서 스택은 그 자체로 내장된 이름 있는 데이터 타입이 아닙니다. 대신, 리스트, 데크, LIFO 큐 또는 사용자 정의 연결 리스트와 같은 기존 데이터 구조 위에 스택을 구현합니다.각 옵션은 성능, 메모리 사용량 및 스레드 안전성 측면에서 고유한 장단점을 가지고 있습니다.

스택에서 가장 기본적인 연산은 푸시와 팝이지만, 실제 구현에서는 피크(또는 탑), 크기 확인, 빈 스택인지 확인하는 등의 추가적인 도우미 함수들이 제공되는 경우가 많습니다.이러한 추가 연산 덕분에 실제 응용 프로그램에서 스택을 사용하는 것이 훨씬 편리해집니다.

코드를 작성하기 전에 중요한 속성을 기억해 두세요. 잘 구현된 스택은 저장된 요소의 개수와 관계없이 푸시 및 팝 연산을 상수 시간(O(1)) 내에 수행합니다.그러한 예측 가능한 성능은 스택이 알고리즘과 저수준 시스템에서 널리 사용되는 주요 이유 중 하나입니다.

코어 스택 작동 및 동작

파이썬에서 사용 가능한 모든 스택은 기본 구현 방식과 관계없이 동작을 정의하는 몇 가지 공통 연산을 중심으로 구성됩니다.이러한 점들을 이해하는 것이 각 라이브러리의 특정 메서드 이름을 암기하는 것보다 훨씬 더 중요합니다.

요소를 삽입하는 가장 일반적인 연산은 '푸시(push)'라고 합니다. 값을 가져와 기존 스택의 맨 위에 올려놓는 것입니다.푸시 작업 후, 새 요소는 다음 팝 작업에서 가장 먼저 반환될 요소가 됩니다.

요소를 제거하기 위해 `pop` 메서드를 사용합니다. `pop` 메서드는 스택의 맨 위에 있는 요소를 가져와 반환합니다.스택이 비어 있는 경우, 견고한 구현은 오류를 발생시키거나 요소가 없음을 명확하게 나타내는 특정 값을 반환해야 합니다.

대부분의 스택 구현체는 peek 또는 top 연산을 제공하여 스택에서 요소를 제거하지 않고 현재 맨 위에 있는 요소를 확인할 수 있도록 합니다.이는 특히 다음 값을 검사해야 하지만 나중에 사용할 수 있도록 해당 값을 유지해야 하는 알고리즘에 유용합니다.

자주 접하게 될 두 가지 추가 도우미 연산으로는 스택에 요소가 있는지 여부와 요소 개수를 확인하는 isempty(또는 isEmpty)와 size가 있습니다. 이 연산들은 스택에 요소가 있는지 여부와 요소 개수를 확인합니다.파이썬에서는 내장 함수 len()과 불리언 검사를 내부적으로 재사용하여 최소한의 코드로 이러한 도우미 함수를 구현할 수 있습니다.

시간 복잡도 측면에서, 제대로 설계된 스택은 push, pop, peek 및 isEmpty 메서드가 모두 상수 시간 O(1)에 실행되도록 보장하며, 크기는 구현 방식에 따라 길이를 별도의 필드로 저장하는지 여부에 따라 O(1) 또는 O(n)이 될 수 있습니다.결정적으로, 스택은 배열처럼 임의의 위치에 효율적으로 무작위 접근을 지원하지 않습니다.

스택은 언제, 왜 사용해야 할까요?

스택은 나중에 "되감기"하거나 단계가 수행된 정확한 역순으로 탐색해야 하는 프로세스를 다룰 때 특히 유용합니다."이 작업을 마지막 순서에서 처음 순서로 되돌려야겠다"라고 자연스럽게 생각하게 되는 모든 상황은 스택을 만들기에 적합한 후보입니다.

실제 세계에서 흔히 볼 수 있는 비유는 기계를 분해하는 것입니다. 나사와 부품을 특정한 순서대로 제거하고, 제대로 재조립하려면 정확히 반대 순서로 다시 넣어야 합니다.이러한 부품들을 쌓아서 보관하는 방식은 해당 작업 흐름과 완벽하게 맞아떨어집니다.

소프트웨어에서 스택의 가장 기본적인 용도 중 하나는 함수 호출 스택입니다. 함수가 다른 함수를 호출할 때마다 매개변수, 지역 변수 및 반환 주소가 메모리의 스택에 푸시됩니다.함수가 반환되면 해당 프레임이 제거되어 호출자의 상태가 복원됩니다.

텍스트 편집기, 그림 도구, IDE 및 기타 여러 응용 프로그램의 실행 취소 및 다시 실행 메커니즘은 일반적으로 작업 또는 상태의 스택에 의존합니다.각 사용자 동작은 실행 취소 스택에 추가됩니다. Ctrl+Z를 누르면 애플리케이션은 가장 최근 동작을 스택에서 꺼내어 되돌립니다.

스택은 그래프에서의 깊이 우선 탐색(DFS)과 같은 알고리즘, 표현식 평가(괄호, 연산자 및 피연산자 구문 분석), 백트래킹, 그리고 방문한 페이지를 저장하고 "뒤로" 키를 눌러 마지막 페이지를 꺼내는 브라우저 방문 기록 구현 등에서 널리 사용됩니다.이러한 시나리오는 스택이 강제하고 핵심과 연관시키는 자연스러운 LIFO 규율의 이점을 누립니다. 프로그래밍 논리.

파이썬 리스트를 이용한 스택 구현

파이썬에서 스택을 만드는 가장 간단한 방법은 내장 리스트 타입을 사용하는 것입니다. append() 메서드를 활용하여 요소를 추가하고 pop() 메서드를 사용하여 마지막 요소를 제거할 수 있습니다.리스트는 내부적으로 동적 배열이며 스택에 필요한 모든 기본 기능을 제공합니다.

리스트 기반의 최소한의 스택은 create_stack, push, pop, isempty, show (또는 top, size 등)와 같은 헬퍼 함수를 ​​제공할 수 있으며, 이러한 함수들은 모두 내부적으로 일반 파이썬 리스트 인스턴스를 조작합니다.예를 들어 create_stack은 빈 리스트를 반환할 수 있으며, isempty는 len(stack) == 0으로 정의할 수 있습니다.

흔히 사용되는 패턴 중 하나는 리스트의 끝을 스택의 맨 위로 간주하는 것입니다. 따라서 `stack.append()`는 리스트를 스택에 추가하고 `stack.pop()`은 리스트에서 항목을 제거하는 역할을 합니다.이렇게 하면 두 작업 모두 평균적으로 상수 시간 내에 완료되고 코드는 매우 읽기 쉽고 간결해집니다.

보다 구조화된 코드를 선호한다면, 리스트를 캡슐화하고 push(), pop(), peek(), is_empty(), size()와 같은 명확한 메서드를 제공하는 사용자 정의 Stack 클래스로 이 동작을 감쌀 수 있습니다.캡슐화를 통해 나중에 추가적인 검사나 로깅을 추가하여 스택을 확장하는 것이 더 쉬워집니다.

리스트는 각 요소가 다음 노드를 가리키는 포인터 없이 값을 직접 저장하기 때문에 메모리 효율성이 비교적 높습니다. 연결 리스트에서는 이러한 포인터가 필요 없습니다.게다가 많은 파이썬 개발자들이 이미 리스트 의미론에 매우 익숙하기 때문에 이 접근 방식은 가르치고 유지 관리하기가 쉽습니다.

하지만 중요한 주의사항이 있습니다. 리스트는 연속적인 메모리 영역에 저장되므로, 리스트의 크기가 예약된 공간을 초과하면 파이썬은 더 큰 새 메모리 블록을 할당하고 요소들을 복사해야 합니다.대부분의 경우 이러한 재할당은 분산되어 눈에 띄지 않지만, 때때로 단일 append() 작업이 다른 작업보다 눈에 띄게 느릴 수 있습니다.

또 다른 단점은 파이썬 리스트가 여러 스레드에서 동시에 수정하는 것에 대해 스레드 안전성이 보장되지 않는다는 점입니다. 이는 멀티스레드 프로그램에서 스택을 사용하려는 경우 문제가 될 수 있습니다.이러한 상황에서는 일반 리스트 대신 queue.LifoQueue와 같은 대안을 고려해야 합니다.

collections.deque를 스택으로 사용하기

파이썬의 collections 모듈은 deque(양방향 큐)를 제공하는데, 이는 빈번한 추가 및 삭제 작업이 필요할 때 리스트보다 더 적합한 경우가 많습니다.데크는 양쪽 끝에서 빠른 추가 및 제거가 가능하도록 최적화되어 있습니다.

데크를 스택으로 사용할 때는 일반적으로 append() 메서드를 사용하여 항목을 추가하고 pop() 메서드를 사용하여 항목을 제거합니다. 이때 스택의 오른쪽 끝을 스택의 맨 위로 간주합니다.내부적으로 deque는 블록의 이중 연결 리스트로 구현되어 리스트에서 종종 발생하는 대규모 재할당을 방지합니다.

deque를 사용하여 스택을 생성하는 것은 간단합니다. deque()를 호출하여 빈 컨테이너를 얻은 다음, 스택에 item을 추가하는 push(stack, item)와 스택이 비어 있지 않은지 확인하고 비어 있지 않으면 pop(stack)을 호출하는 pop(stack)과 같은 연산을 정의합니다.show(stack)과 같은 추가 도우미 함수는 현재 내용을 간단히 출력할 수 있습니다.

deque는 양쪽 끝에서의 효율적인 삽입 및 삭제에 특화되어 있기 때문에, 구조체의 크기가 커지더라도 push 및 pop 연산은 일관된 O(1) 성능을 유지합니다.이러한 이유로 대규모 스택이나 사용량이 많은 스택의 경우 리스트보다 데크가 더 적합할 수 있습니다.

단일 스레드 코드에서 deque는 파이썬으로 스택을 구현할 때 일반적으로 가장 좋은 기본 선택지 중 하나입니다. deque는 뛰어난 성능, 깔끔한 API, 그리고 용량 제한에 대한 예상치 못한 문제가 없다는 장점을 모두 갖추고 있기 때문입니다.또한 스택 크기가 매우 커질 때 타이밍 측면에서 더 예측 가능한 동작을 보입니다.

queue.LifoQueue를 사용하여 스택 구현하기

스레드 안전성이 중요해질 때, 파이썬에서 스택을 구현하는 데에는 `queue` 모듈의 `LifoQueue` 클래스가 가장 적합한 선택입니다.LifoQueue는 기본적으로 잠금 메커니즘이 내장된 스레드 안전 스택입니다.

새로운 LifoQueue 기반 스택을 생성하려면 선택적 maxsize 매개변수를 사용하여 LifoQueue 인스턴스를 생성합니다. maxsize 매개변수는 스택이 저장할 수 있는 최대 요소 수를 나타냅니다.내부적으로 큐는 스택이 가득 찼거나 비어 있을 경우 스레드 간 대기, 차단 및 신호 처리를 담당합니다.

LifoQueue 스택에 요소를 추가하는 작업은 put(item) 메서드를 사용하며, 스택이 이미 최대 용량에 도달한 경우 이 메서드가 차단될 수 있습니다.요소를 꺼낼 때는 get() 메서드를 사용하는데, 스택이 비어 있으면 새 항목이 준비될 때까지 get() 메서드가 차단될 수 있습니다.

qsize(), full(), empty()와 같은 추가 헬퍼 메서드를 사용하면 스레드 안전한 방식으로 스택의 현재 상태를 검사할 수 있습니다.예를 들어, full()은 더 이상 요소를 추가할 수 없는지 알려주고, empty()는 제거할 요소가 있는지 여부를 나타냅니다.

LifoQueue를 사용할 때 가장 큰 단점은 성능입니다. 스레드 안전성을 확보하기 위해 필요한 모든 동기화 작업으로 인해 오버헤드가 발생하여 리스트나 데크를 사용하는 것보다 연산 속도가 느려집니다.CPU 사용량이 많고 고성능이 요구되는 시나리오에서는 그러한 오버헤드가 중요할 수 있지만, 많은 멀티스레드 애플리케이션의 경우 안전성과 정확성이 훨씬 더 중요합니다.

파이썬의 스레딩은 전역 인터프리터 잠금(GIL)으로 인해 스레드가 자동으로 서로 다른 CPU 코어에서 실행된다는 것을 의미하지는 않지만, LifoQueue는 공유 스택을 경쟁 조건 및 일관성 없는 상태로부터 보호합니다.코어 간 진정한 병렬 처리를 위해서는 멀티프로세싱이나 다른 접근 방식이 필요하지만, 스레드 안전 스택 개념은 I/O 집약적이거나 협업적인 워크로드에 여전히 유효합니다.

단일 연결 리스트를 사용한 스택 구현

파이썬에서 스택을 구축하는 보다 "고전적인" 컴퓨터 과학적 방법은 단일 연결 리스트를 사용하는 것입니다. 단일 연결 리스트의 각 노드는 값과 다음 노드를 가리키는 포인터(참조)를 저장합니다.이 접근 방식은 연속적인 메모리에 의존하지 않는 동적으로 크기가 조정되는 스택을 제공합니다.

일반적으로 값과 다음 참조에 대한 속성을 가진 Node 클래스를 정의한 다음, 헤드 노드와 크기 카운터를 추적하는 Stack 클래스를 구현합니다.스택이 비어 있을 때 예외적인 상황을 단순화하기 위해 더미 헤드 노드가 종종 사용됩니다.

이 설계에서 스택의 최상단은 헤드 바로 다음 노드로 표현됩니다.값을 추가하려면 새 노드를 생성하고, 해당 노드의 다음 참조를 현재 head.next로 설정한 다음, head.next를 새 노드를 가리키도록 업데이트하고, 이 과정에서 크기를 증가시키면서 진행합니다.

스택에서 요소를 제거하는 과정은 스택이 비어 있는지 확인한 후, `head.next`가 가리키는 노드를 가져오고, `head.next`를 다음 노드로 이동시키고, 스택 크기를 줄인 다음 제거된 값을 반환하는 것입니다.이 연산은 포인터 업데이트가 두 번만 필요하므로 상수 시간 복잡도를 갖습니다.

getSize(), isEmpty(), peek()와 같은 추가 메서드는 이 구조를 사용하면 쉽게 구현할 수 있습니다. 크기는 정수로 관리되고, isEmpty는 크기가 0인지 확인하며, peek는 스택이 비어 있지 않으면 head.next.value를 반환합니다.또한 스택의 모든 요소를 ​​포함하는 읽기 쉬운 문자열을 생성하는 __str__ 메서드를 정의할 수도 있습니다.

연결 리스트 기반 스택의 장점으로는 재할당 없이 동적으로 크기가 증가할 수 있고, 구조가 커지더라도 push와 pop 연산에 대해 예측 가능한 O(1) 성능을 제공한다는 점이 있습니다.메모리는 노드별로 할당되므로 메모리가 분산된 시스템에서 유용할 수 있습니다.

단점으로는 포인터로 인한 추가적인 메모리 오버헤드(각 노드는 적어도 하나의 참조를 저장함)와 리스트나 데크에 비해 더 장황하고 복잡한 코드가 필요하다는 점입니다.대부분의 일반적인 파이썬 프로그램에서는 이러한 비용이 이점에 비해 크지 않지만, 해당 기법을 이해하는 것은 여전히 ​​가치가 있으며 특정 저수준 또는 교육적 시나리오에 이상적일 수 있습니다.

스택의 특성, 효율성 및 한계

개념적으로 스택은 맨 위에 있는 요소만 접근할 수 있는 객체들의 더미와 같습니다. 즉, 항상 가장 최근에 추가된 요소부터 먼저 상호 작용하게 됩니다.이러한 제약 조건은 스택에 강력한 힘과 한계를 부여합니다.

제대로 구현될 경우, 최상위 요소를 읽고, 새 요소를 삽입하고, 최상위 요소를 제거하는 모든 작업은 상수 시간 O(1) 연산입니다.이처럼 일관된 성능은 수천 또는 수백만 번의 푸시 및 팝 작업이 필요한 알고리즘을 설계할 때 매우 유용합니다.

한 가지 중요한 제약 사항은 스택의 중간에 있는 임의의 요소에 효율적으로 접근하려면 그 위에 있는 모든 요소를 ​​제거해야 한다는 것입니다.만약 무작위 접근이 자주 필요한 상황이라면, 배열처럼 사용되는 리스트와 같은 다른 데이터 구조가 더 적합할 수 있습니다.

메모리 사용량과 할당 패턴은 구현 방식에 따라 크게 달라집니다. 배열(리스트)은 연속적인 메모리 공간을 사용하며 재할당이 필요할 수 있고, 덱(deque)은 메모리 블록을 관리하여 대량 복사를 방지하며, 연결 리스트는 노드를 사용 가능한 메모리 위치에 분산시킵니다.각 접근 방식은 오버헤드, 지역성 및 용량 동작 간의 균형을 다르게 조정합니다.

디자인 관점에서 볼 때, 스택은 의도적으로 단순하게 설계되었습니다. 맨 위 부분만 보이고, 중간에 삽입하거나 인덱싱하는 개념이 없습니다.이러한 단순함은 의도치 않은 오용 가능성을 줄이고 LIFO 워크플로를 명시적으로 모델링하는 코드를 작성하도록 장려합니다.

파이썬 스택 및 스레딩 고려 사항

파이썬 프로그램이 단일 스레드로 실행될 경우, 성능과 편의성을 고려하여 리스트와 덱 중에서 스택 구현 방법을 안전하게 선택할 수 있습니다.두 기능 모두 푸시 및 팝 기능을 제공하며 일반 코드에 쉽게 통합할 수 있습니다.

스택을 공유하는 여러 스레드를 도입하면 상황이 훨씬 더 복잡해집니다. 파이썬 수준에서는 원자적으로 보이는 작업들이 예상치 못한 방식으로 뒤섞여 내부 상태를 손상시킬 수 있습니다.일반 리스트와 데크는 공유 가변 스택으로 사용될 때 완전한 스레드 안전성을 보장하도록 설계되지 않았습니다.

데크는 매우 절제된 방식으로, 한쪽 끝에서만 append()와 pop()을 신중하게 통제하여 사용한다면 비교적 안전합니다.하지만 외부 동기화 없이 여러 스레드가 동시에 읽고 쓰는 경우 미묘한 문제와 경쟁 조건이 발생할 수 있습니다.

여러 스레드가 동시에 푸시 및 팝 작업을 수행하는 강력한 멀티스레드 시나리오에서는 queue.LifoQueue 스택 구현을 권장합니다.내장된 잠금 및 차단 의미론은 동시 접근이 스택을 손상시키지 않도록 보장합니다.

물론, LifoQueue를 사용할 때 스레드 간의 추가적인 조정이 필요하기 때문에 (put 및 get 연산)은 일반 리스트나 데크 방식보다 속도가 느리다는 단점이 있습니다.그러한 오버헤드가 중요한지는 애플리케이션의 성능 요구 사항과 스택에 액세스하는 빈도에 따라 다릅니다.

또한 파이썬의 스레딩 모델은 여전히 ​​전역 인터프리터 잠금(GIL) 하에서 실행되므로, 스레드 안전 스택을 사용하더라도 CPU 집약적인 작업에 대해 완벽한 CPU 병렬 처리를 자동으로 얻을 수는 없다는 점을 염두에 두어야 합니다.하지만 I/O 중심 프로그램이나 순수 병렬 처리보다는 동시성에 의존하는 설계의 경우, 스레드 안전 스택은 필수적인 구성 요소입니다.

적합한 파이썬 스택 구현 선택하기

이러한 모든 옵션을 고려할 때, 파이썬에서 "최적의" 스택 구현은 사용 환경에 따라 크게 달라집니다. 단일 스레드인지 멀티 스레드인지, 성능 민감도, 메모리 사용량, 코드 가독성 등이 모두 중요한 역할을 합니다.모든 상황에 완벽하게 맞는 단 하나의 선택지는 없습니다.

간단하고 스레드를 사용하지 않는 스크립트나 학습 환경에서는 리스트를 스택처럼 사용하는 것만으로도 충분한 경우가 많습니다. append()와 pop() 메서드는 직관적이고 대부분의 작업 부하에서 빠르며, 거의 반복적인 코드가 필요하지 않습니다.교육적인 목적에서, 목록은 인쇄 및 내용 검토를 용이하게 해줍니다.

스택 사용량이 많고 잠재적으로 많은 요소를 저장할 수 있으며, 메모리 재할당과 관련된 예상치 못한 상황을 최소화하면서 일관되게 빠른 푸시/팝 속도를 원하는 경우, collections.deque가 가장 실용적인 선택인 경우가 많습니다.해당 API는 리스트와 매우 유사하므로 마이그레이션은 일반적으로 수월합니다.

스택에 여러 스레드가 접근할 것이라는 사실을 처음부터 알고 있다면, 특히 푸시와 팝 작업이 동시에 발생할 경우, `queue.LifoQueue`가 가장 안전한 선택입니다.속도는 느릴 수 있지만, 자체 잠금 프로토콜을 구현할 필요가 없고 까다로운 경쟁 조건을 피하는 데 도움이 됩니다.

단일 연결 리스트 방식은 데이터 구조의 내부를 탐구하거나 가르치려는 경우, 또는 특정 제약 조건 때문에 연속 배열이나 데크를 사용하는 것이 적합하지 않은 경우에 이상적입니다.또한, 더 많은 코드를 작성해야 하고 약간의 정신적 부담이 따르지만, 노드 레이아웃과 동작을 완벽하게 제어할 수 있습니다.

어떤 구현 방식을 선택하든 기본 아이디어는 동일합니다. 즉, 요소를 서로 겹쳐 저장하고 가장 최근에 추가된 항목에 빠르고 예측 가능한 접근을 제공하는 후입선출(LIFO) 구조를 모델링하는 것입니다.이 모델에 익숙해지면 스택이 자연스럽게 적용되는 알고리즘과 시스템 동작에 대해 생각하는 것이 훨씬 쉬워집니다.

스택의 작동 방식, 지원하는 연산, 일반적인 파이썬 구현 방식, 그리고 성능 및 스레딩 관련 장단점을 이해하면 프로젝트 요구 사항에 가장 적합한 버전을 자신 있게 선택하고 구현할 수 있으며, 시간이 지나도 효율적이고 이해하기 쉬운 코드를 작성할 수 있습니다..