[자료구조] 스택(Stack)

1. 의미 파악

스택: 박스가 쌓인 형태

박스를 쌓은 뒤 꺼낼 때, 가장 마지막에 올렸던 박스부터 꺼내야함

 

자료구조에서의 의미

가장 마지막에 들어온 데이터가 가장 먼저 추출되는 자료구조

 

스택에서 사용하는 연산

 

Push: 스택에 원소를 삽입

Pop: 스택에서 원소를 추출

Top: 스택의 최상위 원소(마지막에 들어온 원소)를 확인하는 연산

Empty: 스택이 비어 있는지 확인하는 연산

 

리스트에서 스택의 기능 제공이 가능함

그래서 일반적으로 리스트 자료형을 이용해서 구현한다고함

 

Push => append

Pop => Pop

 

사용예시

 

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

    def push(self, data):
        # 마지막 위치에 원소 삽입
        self.stack.append(data)

    def pop(self):
        if self.is_empty():
            return None
        # 마지막 원소 추출
        return self.stack.pop()

    def top(self):
        if self.is_empty():
            return None
        # 마지막 원소 반환
        return self.stack[-1]

    def is_empty(self):
        return len(self.stack) == 0


stack = Stack()
arr = [1, 2, 3, 4, 5, 6, 2, 1]
for x in arr:
    stack.push(x)

while not stack.is_empty():
    print(stack.pop())
    
#결과
1
2
6
5
4
3
2
1

 

결과를 보면 알지만 거꾸로 나오는 것을 확인할 수 있음

 

 

연결 리스트를 이용한 스택 구현 

 

연결 리스트로 구현할 때는 헤드를 가리키는 한개의 포인터만 가짐

헤드(head): 남아 있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터

 

삽입, 삭제 둘다 데이터를 헤드에서 작업함

 

삽입: 삽입시 기존 헤드에 포인터 연결 - 헤드를 새로 추가한 노드로 변경해주면됨

삭제: 헤드에서 데이터를 꺼냄 - 헤드가 없을때 다음을 가리키도록 만들면됨

 

사용 예시

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    # 삽입
    def push(self, data):
        node = Node(data)
        node.next = self.head
        self.head = node

    # 추출
    def pop(self):
        if self.is_empty():
            return None

        # 헤드에서 노드 꺼낼때
        data = self.head.data
        self.head = self.head.next
        return data

    # 최상위 원소
    def top(self):
        if self.is_empty():
            return None
        return self.head.data

    # 먼저 추출할 원수부터 출력
    def show(self):
        cur = self.head
        while cur:
            print(cur.data, end=' ')
            cur = cur.next

    # is_empty
    def is_empty(self):
        return self.head is None

stack = Stack()
arr = [1,2,3,4,5,6,3,2]
for i in arr:
    stack.push(i)
stack.show()

#결과
2 3 6 5 4 3 2 1