Linked list, Stack, Queue <3-3>

<< 3주차 Lecture Note 3번째>>

• Stack

---

Stack

 

Stack이란, 데이터를 삽입/제거 하는 통로가 1개로 구성된 구조라고 생각하면 된다.

 

이것을 링크드리스트에서 생각해보자. 링크드리스트는 값을 가진 여러개의 노드가 연결되어있는건데,

이미 존재하는 노드 사이에 어느 위치라도 새로운 노드를 연결해서 데이터를 추가할 수 있었다.

 

하지만 스택에서는 데이터를 추가할 수 있는 위치를 맨 앞 노드로만 한정짓는 것이고, 이것을 '탑 노드'라고 한다.

데이터의 추가와 삭제가 탑 노드에서만 이루어지게 되면, 데이터가 추가되는 순서와 삭제되는 순서는 반대가 된다.

즉, 데이터가 1, 2, 3의 순서로 추가된 경우, 반대로 삭제되는 것은 3, 2, 1 순서로 삭제가 되는 것이다.

---

1. Operation of Stack

Stack에는 Operation이 2가지(Push/Pop)가 존재한다.

데이터가 들어오고 나가는 통로가 1개로 한정되어있기 때문에, 일반적인 리스트처럼 search / insert가 필요하지 않다.

 

- Push

데이터를 탑 노드에 추가하는 작업이다. Push를 반복할 경우, 먼저 추가된 데이터는 다음 노드로 밀리고 새로운 데이터가 들어온다.

즉, Push는 항상 링크드리스트의 첫 번쨰 노드에서 데이터를 추가 하는 거다.

 

- Pop

데이터를 탑 노드에서 제거하는 작업이다. Pop을 반복할 경우, 탑 노드의 데이터는 삭제되고 그 다음 노드의 데이터가 탑 노드로 오게 된다.

즉, Pop은 항상 링크드리스트의 첫 번째 노드에서 데이터를 삭제 하는 거다.

---

2. Implementation of Stack

 

아래 코드는 Stack을 구현해서 데이터를 추가, 삭제하고 프린트해본 거다.

우선 SinglyLinkeList 클래스는 이전 글에서 구현한 적이 있다.

2023.10.19 - [KOOC/Linear Structure & Dynamic Programming] - Linked list, Stack, Queue <3-1>

Linked list, Stack, Queue <3-1>

 

 

class Stack:
    lstInstance = SinglyLinkedList()
    
    def pop(self):
        return self.lstInstance.deleteAt(0)
        
    def push(self, value):
        self.lstInstance.insertAt(value, 0)

 

위 코드에서 Stack 클래스에 push와 pop을 정의했다.

 

stack = Stack()

stack.push("a")
stack.lstInstance.printStatus()

stack.push("b")
stack.lstInstance.printStatus()

stack.push("c")
stack.lstInstance.printStatus()

 

그리고 위 코드를 실행하면, 링크드 리스트의 상태를 출력해본 결과는 아래와 같다.

 

$$ a 

$$ b a 

$$ c b a 

 

push를 이용해 a → b → c 순서대로 삽입했고, 가장 먼저 입력한 a가 가장 맨 뒤에 있는 것을 볼 수 있다.

 

이제 pop으로 하나씩 삭제해보면 출력 결과는 아래와 같다.

stack.lstInstance.printStatus()

stack.pop()
stack.lstInstance.printStatus()

stack.pop()
stack.lstInstance.printStatus()

stack.pop()
stack.lstInstance.printStatus()

 

$$ c b a 

$$ b a 

 

$$ a 

 

c → b → a 순서로 삭제됨으로써 결과는 빈 리스트가 된다.