Python의 스택 구현 이해

by

데이터 구조는 프로그래밍 세계에서 중요한 역할을 합니다. 효율적으로 사용할 수 있는 방식으로 데이터를 구성하는 데 도움이 됩니다. 스택은 가장 단순한 데이터 구조 중 하나입니다.

스택과 파이썬에서의 구현에 대해 알아봅시다.

스택이란 무엇입니까?

스택은 실생활에서 책, 의자 등의 더미와 비슷합니다. 그리고 LIFO(Last-in/First-out) 원칙을 따릅니다. 가장 간단한 데이터 구조입니다. 실제 사례를 통해 시나리오를 살펴보겠습니다.

다음과 같은 책 더미가 있다고 가정해 봅시다.

위에서 세 번째 책을 원할 때 세 번째 책을 꺼내기 위해 맨 위에서 처음 두 권의 책을 제거해야 합니다. 여기에서 맨 위에 있는 책이 맨 마지막에 있고 더미 맨 앞에 옵니다. 데이터 구조 스택은 프로그래밍에서 동일한 LIFO(후입선출) 원칙을 따릅니다.

스택 작업

스택에는 주로 두 가지 작업이 있습니다.

1. 푸시(데이터)

스택에 데이터를 추가하거나 푸시합니다.

2. 팝()

스택에서 최상위 요소를 제거하거나 팝합니다.

푸시 및 팝 작업에 대한 아래 그림을 참조하십시오.

스택에 대한 자세한 정보를 얻는 데 도움이 되는 몇 가지 도우미 함수를 작성할 것입니다.

그들을 보자.

몰래 엿보다()

스택에서 최상위 요소를 반환합니다.

비었다()

스택이 비어 있는지 여부를 반환합니다.

스택 데이터 구조의 개념적 측면이 충분합니다. 더 이상 고민하지 않고 구현으로 넘어가겠습니다.

온라인 컴파일러를 사용해 볼 수 없다면 PC에 Python이 설치되어 있다고 가정합니다.

스택 구현

스택 구현은 다른 데이터 구조 구현에 비해 가장 쉬운 것입니다. Python에서 여러 가지 방법으로 스택을 구현할 수 있습니다.

모두 하나씩 살펴보겠습니다.

#1. 목록

우리는 클래스의 목록을 사용하여 스택을 구현할 것입니다. 스택의 단계별 구현을 살펴보겠습니다.

1단계: Stack이라는 클래스를 작성합니다.

class Stack:
	pass

2단계: 데이터를 목록으로 유지해야 합니다. 이름 요소가 있는 Stack 클래스에 빈 목록을 추가해 보겠습니다.

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

3단계: 요소를 스택에 푸시하려면 메서드가 필요합니다. 데이터를 인수로 받아 요소 목록에 추가하는 푸시 메서드를 작성해 보겠습니다.

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

	def push(self, data):
		self.elements.append(data)
		return data

4단계: 마찬가지로 스택에서 맨 위 요소를 꺼내는 pop 메서드를 작성해 보겠습니다. 목록 데이터 유형의 pop 메소드를 사용할 수 있습니다.

class Stack:
	## ...
	def pop(self):
		return self.elements.pop()

필요한 작업으로 스택 구현을 완료했습니다. 이제 스택에 대한 자세한 정보를 얻기 위해 도우미 함수를 추가해 보겠습니다.

5단계: 음수 인덱스를 사용하여 스택에서 최상위 요소를 가져올 수 있습니다. 코드 요소[-1]은 목록의 마지막을 반환합니다. 우리의 경우 스택의 최상위 요소입니다.

class Stack:
	## ...

	def peek(self):
		return self.elements[-1]

6단계: 요소 목록의 길이가 0이면 스택이 비어 있습니다. 요소가 비어 있는지 여부를 반환하는 메서드를 작성해 봅시다.

class Stack:
	## ...
	def is_empty(self):
		return len(self.elements) == 0

목록 데이터 유형을 사용하여 스택 구현을 완료했습니다.

  Windows에서 Caps Lock을 수정 키로 사용하는 방법

오! 방금 구현했습니다. 그러나 그것을 사용하는 방법을 보지 못했습니다. 그럼 어떻게 사용하나요?

그것을 구현하는 방법을 보자. Stack 클래스가 사용할 객체를 만들어야 합니다. 큰 문제가 아닙니다. 먼저 해봅시다.

class Stack: 
    ## ...

if __name__ == '__main__':
    stack = Stack()

스택 객체를 생성하고 사용할 준비가 되었습니다. 아래 단계에 따라 스택 작업을 테스트해 보겠습니다.

  • is_empty 메서드를 사용하여 스택이 비어 있는지 확인합니다. True를 반환해야 합니다.
  • 푸시 방법을 사용하여 숫자 1, 2, 3, 4, 5를 스택에 푸시합니다.
  • is_empty 메서드는 False를 반환해야 합니다. 확인해 봐.
  • peek 메서드를 사용하여 최상위 요소를 인쇄합니다.
  • pop 메서드를 사용하여 스택에서 요소를 팝합니다.
  • 엿보기 요소를 확인하십시오. 요소 4를 반환해야 합니다.
  • 이제 스택에서 모든 요소를 ​​팝합니다.
  • is_empty 메서드는 True를 반환해야 합니다. 확인해 봐.

위의 단계를 모두 통과하면 스택 구현이 완료된 것입니다. 위의 단계에 대한 코드를 작성해 보십시오.

코드를 작성했습니까? 아니요, 걱정하지 마세요. 아래 코드를 확인하세요.

class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
    
    def pop(self): 
        return self.elements.pop() 
        
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

if __name__ == '__main__':
    stack = Stack()
    
    ## checking is_empty method -> true
    print(stack.is_empty())

    ## pushing the elements
    stack.push(1)
    stack.push(2)
    stack.push(3)
    stack.push(4)
    stack.push(5)

    ## again checking is_empty method -> false
    print(stack.is_empty())

    ## printing the topmost element of the stack -> 5
    print(stack.peek())

    ## popping the topmost element -> 5
    stack.pop()

    ## checking the topmost element using peek method -> 4
    print(stack.peek())

    ## popping all the elements
    stack.pop()
    stack.pop() 
    stack.pop() 
    stack.pop() 

    ## checking the is_empty method for the last time -> true
    print(stack.is_empty())

만세! 목록 데이터 유형을 사용하여 처음부터 스택 구현을 완료했습니다. 위의 코드를 실행하면 아래와 같이 출력되는 것을 볼 수 있습니다.

True
False
5
4
True

목록 데이터 유형을 스택으로 직접 사용할 수 있습니다. 위의 스택 구현은 다른 프로그래밍 언어에서도 스택 구현을 이해하는 데 도움이 됩니다.

이 목록 관련 기사를 확인할 수도 있습니다.

스택으로 작동할 수 있는 컬렉션 내장 모듈의 내장 deque를 살펴보겠습니다.

  Google 스프레드시트에서 중복을 찾고 제거하는 방법

#2. 컬렉션에서 데크

양방향 대기열로 구현됩니다. 양쪽 끝에서 요소 추가 및 제거를 지원하기 때문입니다. 따라서 스택으로 사용할 수 있습니다. 스택의 LIFO 원리를 따르도록 만들 수 있습니다.

이중 연결 목록이라는 다른 데이터 구조를 사용하여 구현됩니다. 따라서 요소 삽입 및 삭제 성능이 일관됩니다. 중간 연결 목록에서 요소에 액세스하는 데 O(n) 시간이 걸렸습니다. 스택에서 중간 요소에 액세스할 필요가 없으므로 스택으로 사용할 수 있습니다.

스택을 구현하기 전에 큐를 사용하여 스택을 구현하는 데 사용되는 메서드를 살펴보겠습니다.

  • append(data) – 데이터를 스택에 푸시하는 데 사용
  • pop() – 스택에서 최상위 요소를 제거하는 데 사용

peek 및 is_empty에 대한 대체 방법은 없습니다. 엿보기 방법 대신 전체 스택을 인쇄할 수 있습니다. 다음으로 len 메소드를 사용하여 스택이 비어 있는지 여부를 확인할 수 있습니다.

collections 모듈에서 deque를 사용하여 스택을 구현해 봅시다.

from collections import deque

## creating deque object
stack = deque()

## checking whether stack is empty or not -> true
print(len(stack) == 0)

## pushing the elements
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(4)
stack.append(5)

## again checking whether stack is empty or not -> false
print(len(stack) == 0)

## printing the stack
print(stack)

## popping the topmost element -> 5
stack.pop()

## printing the stack
print(stack)

## popping all the elements
stack.pop()
stack.pop() 
stack.pop() 
stack.pop() 

## checking the whether stack is empty or not for the last time -> true
print(len(stack) == 0)

그게 다야. 컬렉션 내장 모듈에서 deque를 사용하여 스택을 구현하는 방법을 배웠습니다. 위의 프로그램을 실행하면 아래와 같은 결과를 얻을 수 있습니다.

True
False
deque([1, 2, 3, 4, 5])
deque([1, 2, 3, 4])
True

지금까지 스택을 구현하는 두 가지 방법을 살펴보았습니다. 스택을 구현하는 다른 방법이 있습니까? 응! 이 튜토리얼에서 스택을 구현하는 마지막 방법을 살펴보겠습니다.

#삼. LifoQueue

LifoQueue라는 이름 자체는 LIFO 원칙을 따른다고 말합니다. 따라서 의심의 여지 없이 스택으로 사용할 수 있습니다. 내장 모듈 큐에서 가져온 것입니다. LifoQueue는 스택 구현에 유용한 몇 가지 편리한 메서드를 제공합니다. 그들을 보자

  • put(data) – 데이터를 대기열에 추가하거나 푸시합니다.
  • get() – 대기열에서 최상위 요소를 제거하거나 꺼냅니다.
  • empty() – 스택이 비어 있는지 여부를 반환합니다.
  • qsize() – 대기열의 길이를 반환합니다.

큐 모듈에서 LifoQueue를 사용하여 스택을 구현해 봅시다.

from queue import LifoQueue

## creating LifoQueue object
stack = LifoQueue()

## checking whether stack is empty or not -> true
print(stack.empty())

## pushing the elements
stack.put(1)
stack.put(2)
stack.put(3)
stack.put(4)
stack.put(5)

## again checking whether stack is empty or not -> false
print(stack.empty())

## popping all the elements
print(stack.get())
print(stack.get())
print(stack.get())

## checking the stack size
print("Size", stack.qsize())

print(stack.get())
print(stack.get())

## checking the whether stack is empty or not for the last time -> true
print(stack.empty())

위의 프로그램을 변경하지 않고 실행하면 아래와 같은 결과를 얻을 수 있습니다.

True
False
5
4
3
Size 2
2
1
True

스택의 적용

이제 스택에 대한 지식이 충분하여 프로그래밍 문제에 적용할 수 있습니다. 문제를 보고 스택을 사용하여 해결해 봅시다.

  2020년 최고의 패치 관리 도구 및 소프트웨어

표현식이 주어졌을 때 괄호, 중괄호, 중괄호의 균형이 맞는지 확인하는 프로그램을 작성하세요.

몇 가지 예를 살펴보겠습니다.

입력: “[{}]([])”

출력: 균형

입력: “{[}]([])”

출력: 균형이 맞지 않음

스택을 사용하여 위의 문제를 해결할 수 있습니다. 문제를 해결하는 단계를 살펴보겠습니다.

  • 문자를 저장할 스택을 만듭니다.
  • 식의 길이가 홀수이면 식은 균형이 맞지 않습니다.
  • 주어진 표현식을 반복합니다.
    • 현재 문자가 ( 또는 { 또는 [, then push it to stack.
    • Else if the current character is a closing bracket ) or } or ]그런 다음 스택에서 팝합니다.
    • 팝된 문자가 시작 대괄호와 일치하면 계속하고 그렇지 않으면 대괄호가 균형을 이루지 않습니다.
  • 반복 후 스택이 비어 있으면 방정식이 균형을 이루고 그렇지 않으면 방정식이 균형을 이루지 않습니다.

대괄호 일치 확인을 위해 설정된 데이터 유형을 사용할 수 있습니다.

## stack
class Stack: 
    def __init__(self): 
        self.elements = [] 
    
    def push(self, data): 
        self.elements.append(data) 
        return data 
        
    def pop(self): 
        return self.elements.pop() 
    
    def peek(self): 
        return self.elements[-1] 
        
    def is_empty(self): 
        return len(self.elements) == 0

def balance_check(expression):
    ## checking the length of the expression
    if len(expression) % 2 != 0:
        ## not balanced if the length is odd
        return False
    
    ## for checking
    opening_brackets = set('([{') 
    pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) 
    
    ## stack initialization
    stack = Stack()
    
    ## iterating through the given expression
    for bracket in expression:

        ## checking whether the current bracket is opened or not        
        if bracket in opening_brackets:
            ## adding to the stack 
            stack.push(bracket)
        else:
            ## popping out the last bracket from the stack
            popped_bracket = stack.pop()
        
            ## checking whether popped and current bracket pair
            if (popped_bracket, bracket) not in pairs:
                return False
    
    return stack.is_empty()

if __name__ == '__main__':
    if balance_check('[{}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")
    
    if balance_check('{[}]([])'):
        print("Balanced")
    else:
        print("Not Balanced")

스택을 사용하여 더 많은 문제를 해결할 수 있습니다. 위의 문제는 그 중 하나입니다. 자신에게 가장 적합하다고 생각되는 곳에 스택 개념을 적용해 보십시오.

결론

야아! 튜토리얼을 완료했습니다. 나는 당신이 그것을 만드는 동안 내가하는만큼 튜토리얼을 즐겼기를 바랍니다. 튜토리얼은 여기까지입니다.

행복한 코딩 🙂 👨‍💻