[자료구조 공부기록] 3. Stack + Python 구현

Stack의 생김새

 특징

• 선형구조를 가진 자료구조입니다.
• LIFO(Last In First Out / 제일 나중에 들어온 원소가 제일 먼저 나감) 구조를 가지고 있습니다.

 

장점 및 단점

 

1) 장점

• 구조가 단순하여 구현이 간단합니다.
• 성능이 좋습니다.

 

2) 단점

• 일부 구현 방법은 미리 크기를 정해주어야 합니다.
• 오래된 데이터에 접근이 힘듭니다.

---

왼쪽은 데이터를 집어넣는 Push, 오른쪽은 데이터를 빼는 Pop

데이터가 들어가고 나가는 방법만 이해하신다면 스택은 구조가 정말 단순하여 크게 말씀드릴 것은 없습니다.

 

왼쪽의 사진처럼 Push로 데이터를 넣게 되면 맨 위에 저장되고 

 

오른쪽 사진처럼  Pop으로 데이터를 뺀다면 맨 위의 데이터가 나가는 형식입니다. 

---

# 데이터 저장 노드 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.before = None
        
# Single Linked List 클래스 정의
class Stack:
    # 현재 마지막 노드를 표시할 cur
    def __init__(self):

        temp_node= Node(None)

        self.cur = temp_node
        
    
    # push func
    def push(self, data):
        
        temp_node = Node(data)
        
        # temp_node의 이전 노드를 현재 마지막 노드로 설정
        # cur을 temp_node로 변환
        temp_node.before = self.cur
        self.cur = temp_node
        
    # pop func
    def pop(self):
        
        data = self.cur.data
        
        # 이전 메시지가 정의 안되있다면 이전 노드로 이동
        # 이전 노드가 정의 되지 않았다면 -1 return
        if self.cur.before != None:
            self.cur = self.cur.before
        else:
            return -1
            
        return data


a = Stack()

a.push(1)
a.push(2)
a.push(3)
a.push(4)

print(a.pop()) # 1
print(a.pop()) # 2
print(a.pop()) # 3
print(a.pop()) # 4
print(a.pop()) # -1

Python 기본 자료형중 하나인 list를 사용한다면 정말 쉽게 구현 가능하지만 

 

이전에 사용한 linked list를 사용하여 구현해봤습니다. 

 

원래는 처음 Stack 사이즈도 정해주고 싶었는데 귀찮아서 간단하게 했습니다.

 

temp_list = [1,2,3,4,5]

temp.pop()

참고로 Python list는 위와 같은 pop 기능을 사용할 수 있습니다. 

 

다만 push는 사용할 수 없지만 이미 append가 push와 거의 같은 역할이긴 합니다.