자료구조 스택 by Python

저번에 알아본 큐에 이어 이번 포스팅에선 스택 자료구조에 관해 알아보도록 하겠다.

---

스택(Stack)

1. 의미

  사전적 의미는 적(積), 즉 쌓는다는 의미다.

자료구조에서의 스택과 개념은 살짝 다르지만 보통 "패시브 스택 쌓는다"라고 하는 표현은 많이 들어봤을 것이다.

 

2. 스택의 구조

  Lifo, Filo(Last-in/First-out, First-in/Last-out)

  가장 먼저 들어간 자료가 가장 나중에 나오는 구조이다. 

  스택의 구조를 그림으로 알아보면 다음과 같다.

자료를 입력하면 데이터중 가장 위에 위치하고, 출력할땐 가장 위의 데이터가 나오는 것이 스택 구조이며, 

여기서 Push, Pop이라는 용어가 나오는데, 각 용어는 다음과 같은 의미가 있다.

 

• Push : Stack에 데이터를 넣는 기능

• Pop : 스택에서 데이터를 꺼내는 기능

Push와 Pop을 코드로 구현해보자.

 

stack = []
 
def push(data):
    stack.append(data)
    
def pop():
    data_stack = stack[-1]
    del stack[-1]
    return data_stack
 
for i in range(10):
    push(i)
    
pop()
>> 9

 

3. 스택의 실제 사용 예

  컴퓨터 내부의 프로세스 구조의 함수 동작 방식에 쓰인다.

  다음의 재귀함수 코드 예시를 보자.

def recursive(data):
    if data < 0:
        print("ended")
    else:
        print(data)
        recursive(data-1)
        print("returned", data)
 
recursive(4)
 
>> 4
>> 3
>> 2
>> 1
>> 0
>> "ended"
>> "returned" 0
>> "returned" 1
>> "returned" 2
>> "returned" 3
>> "returned" 4

recursive(4 → 3 → 2 → 1 → 0)순서로 data값을 계속 출력한 뒤, recursive(-1)에서 "ended"가 출력된다.

그 뒤 recursive(0 → 1 → 2 → 3 → 4) 순으로 가장 "먼저" 호출된 함수가 가장 나중에 값을 출력함으로, 재귀 함수의 함수 동작 구조가 스택구조라는 것을 알 수 있다.

4. 스택의 장단점

 장점  

    1) 구조가 단순하여 구현이 쉽고 그로 인한 빠른 데이터 처리속도

 단점

    1) 데이터 최대 개수를 미리 정해야 한다(콜 스택의 한도 등). 파이썬의 경우 재귀함수는 1000번까지만 호출이 가능.

    2) 미리 최대 개수를 확보해야하는 자료구조이므로 최대 개수를 꽉 채우지 못하면 그만큼 메모리 낭비가 발생한다.

 

5. 큐와 스택의 응용

  1) 스택 두개로 큐를 만들기

stack_one = []
stack_two = []
 
def _push(stack, data):
    stack.append(data)
    print("pushed", data)
 
def _pop(stack):
    data = stack[-1]
    del stack[-1]
    return data
 
def queue_by_two_stacks(q_data):
 
    ## (1) stack_one에 차례대로 push를 해준다.
    for i in range(q_data):  
        _push(stack_one, i)
 
    ## (2) stack_one에서 넣은 것을 나중에 넣은것부터 꺼내서(pop) stack_two에 넣는다
    for i in range(q_data):
        _push(stack_two, _pop(stack_one)) 
 
    ## (3) stack_two에 넣은 데이터를 나중에 넣은 것부터 꺼내서 출력한다.
    for i in range(q_data):
        print(_pop(stack_two))  
 
queue_by_two_stacks(5)
 
>> "pushed" 0
>> "pushed" 1
>> "pushed" 2
>> "pushed" 3
>> "pushed" 4
## 여기까지가 (1)
>> "pushed" 4
>> "pushed" 3
>> "pushed" 2
>> "pushed" 1
>> "pushed" 0
## 여기까지가 (2)
>> 0
>> 1
>> 2
>> 3
>> 4
## 여기까지가 (3)이고, (1)부분과 비교해보면 먼저 입력된 숫자가 먼저 출력된걸 확인할 수 있다.
## 즉, 스택 두 개로 큐를 구현할 수 있다.
 
 

  2) 스택과 큐로 회문 검사하기

 

def is_palindrome(string):
 
    ## 문자열을 리스트로 만들어 stack과 queue에 배정해준다.
 
    stack = list(string)  
    queue = list(string)
 
    for i in range(len(string)):
 
    ## stack은 문자열의 뒷글자부터 가져오도록 하고, queue는 첫글자부터 가져와서 같은지 비교한다.
 
        print(queue[i], stack[-(i + 1)])
 
        if queue[i] != stack[-(i + 1)]: ## 서로 가져온 글자가 다르다면 회문이 아니다(False)
            return False
 
    return True  ## 전부 비교해보니 다른 글자가 없다면 회문이다(True)
 
print(is_palindrome("tomato"))
 
>> t o
 
>> False
 
print(is_palindrome("토마토"))
 
>> 토 토
>> 마 마
>> 토 토
 
>> True

 

6. 더 알아야할 것📖

스택또한 프로세스가 어쩌고 하는것이 운영체제에서 쓰인다고 하니 운영체제 공부하면서 스택 자료구조도 한번 더 짚어봐야겠다.