[5] Stack, 스택

👇🏻 최근에 나에게 감동을 선사한 짤

너는 뭐냐 멍청한 샌드위치여

---

해리포터 시리즈 책을 바닥에 1권부터 7권까지 쌓는다고 생각해보자.

 

 

가장 먼저 꺼낼 수 있는 책은 무엇인가? 가장 나중에 쌓은 7권을 가장 먼저 빼낼 수 있다. 

이것이 스택의 자료형이다.

 

스택(Stack, 쌓다) : 가장 나중에 넣은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조
스택을 LIFO 방식이라고 얘기하는데 Last In First Out (가장 나중에 들어가고 가장 먼저 나온다, 후입선출)라는 뜻이다. 

 

파이썬에서 우리가 사용하는 list로 이미 스택은 구현되어 있으며 내장함수를 이용해 사용하면 된다.

  list.append(data) : list에 data를 맨 마지막에 추가함.

  list.pop() : list의 맨 마지막 요소를 반환하고 해당 요소는 list에서 삭제함.

 

위의 두 내장함수로 스택은 데이터의 삽입과 삭제가 한쪽 끝(마지막 혹은 맨 윗 부분)에서만 일어난 다는 것을 알 수 있다.

스택은 배열(list)과 단일 연결리스트(Single Linked List)로 구현이 가능하다.

 

✓ 배열(list)로 구현

 

class Stack:
    # 리스트 초기화
    def __init__(self):
        self.items = []
    
    # 가장 마지막에 data 추가 (맨 위에)
    def push(self, data):
        self.items.append(data)
    
    # 가장 마지막 요소(맨 윗 요소) 반환 후 삭제
    def pop(self):
        return self.items.pop()

    # 가장 마지막 요소(맨 윗 요소, top이라고도 한다) 반환
    def peek(self):
        return self.items[-1]
    
    # 스택에 요소 여부 확인 : 비었을 경우 True 반환
    def isEmpty(self):
        return not self.items

stack = Stack()
print(stack.isEmpty()) # True

for data in range(1,10):
    stack.push(data)

print('Stack : ',stack.items) # Stack :  [1, 2, 3, 4, 5, 6, 7, 8, 9]
print(' Top : ', stack.peek()) # Top :  9

for i in range(len(stack.items)):
    print('Delete ', stack.pop())

# Delete  9
# Delete  8
# Delete  7
# Delete  6
# Delete  5
# Delete  4
# Delete  3
# Delete  2
# Delete  1

print('Stack : ',stack.items) # Stack :  []

 

list로 push(삽입), pop(삭제)할 경우 시간복잡도는 O(1)이다.

 

✓ 연결리스트로 구현

 

우리 머리속에 있는 연결리스트의 형태

 

우리가 알고 있는건 기차놀이하고 있는 노드들이다. 이것을 스택으로 구현하기 위해서는 사고방식의 변화가 필요하다.

기차놀이에서 줄줄이 소세지라고 생각하고 헤드를 손가락으로 들어올리면 다음과 같이 될 것이다. 

 

 

연결리스트의 head는 스택의 가장 윗 부분을 가리키게 된다. 만약 새로운 노드를 삽입하고 싶으면 새로운 노드의 next를 기존 head를 가리키게 한 후 head가 새로운 노드를 가치키게 하면 된다. 

 

# 노드 클래스
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
    
class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)

        if self.isEmpty():
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    def pop(self):
        temp = self.head.data
        self.head = self.head.next
        return temp
    
    def peak(self):
        return self.head.data
    
    def isEmpty(self):
        return not self.head
    
    def print_node(self):
        node = self.head
        print('Stack : ', end='')
        while node:
            print(node.data, end=' ')
            node = node.next

stack = Stack()
print(stack.isEmpty()) # True

for data in range(1,10):
    stack.push(data)

stack.print_node() # Stack : 9 8 7 6 5 4 3 2 1
print('Top : ', stack.peak()) # Top : 9

print('Delete Top : ', stack.pop()) # Delete Top :  9

 

연결리스트로 push(삽입), pop(삭제)할 경우 시간복잡도는 마찬가지로 O(1)이다.

구현은 어렵지 않은듯하다. 연결리스트를 제대로 이해했다면 말이다.

 

✓ 스택의 특징
 top(맨 위)을 통해서만 요소에 접근할 수 있고 데이터를 정해진 방법으로만 쌓을 수 있다.
 후입선출의 구조를 가지고 있다.
 스택이 비어있을 때 요소에 접근할 경우 stack underflow라고 하고 스택이 넘치는 경우는 stack overflow라고 한다. 

✓ 스택의 활용
  역순 문자열을 생성
  웹 브라우저 방문 기록 (뒤로 가기), 실행 취소(undo, cmd+z, ctrl_z) : 최근것부터 보여주기 때문에

 

끝 !

 

👇🏻 Github에서 stack 코드 확인하기

✓ list로 구현

https://github.com/Seeun-Lim/Data-Structure/blob/main/Stack-list.py

GitHub - Seeun-Lim/Data-Structure

 

✓ 이중 연결리스트로 구현

https://github.com/Seeun-Lim/Data-Structure/blob/main/Stack-LinkedList.py

GitHub - Seeun-Lim/Data-Structure