스택, 큐

👀 스택과 큐란?

: 스택과 큐는 들어가고 나오는 곳이 정해져 있는 자료구조입니다!

 

👀 스택이란?

👉 한쪽 끝으로만 자료를 넣고 뺄 수 있는 자료 구조를 말합니다. (선입후출?)

 

실생활적인 예시를 들어 보자면

스택이라는 자료 구조는 "빨래통"을 떠올리시면 됩니다.

 

데이터를 한 곳에서만 넣었다 뺄 수 있습니다.

가장 밑에 있는 빨래를 뺄 수 있나요? 아니요!!

가장 위에 있는 빨래를 빼거나 넣을 수 있습니다.

 

그러면 가장 처음에 넣은 빨래는? 가장 늦게 나오겠죠!!

가장 마지막에 넣은 빨래는? 가장 빨리 나옵니다!!

 

이런 자료 구조를 Last In First Out이라고 해서 LIFO라고 부릅니다.

 

👀 그렇다면 이런 자료구조는 왜 필요할까요?

👉 바로, 넣은 순서를 쌓아두고 있기 때문입니다. 그 순서가 필요한 경우가 있습니다.

 

예를 들어 컴퓨터의 되돌리기(Ctrl + Z) 기능을 아시나요??

직전에 했던 행동을 되돌리고 싶을 때 사용하는 기능으로써 이를 위해서는 내가 했던 행동들을 순서대로 기억해야 하므로 스택을 사용합니다.

 

👀 스택의 구현은??

 

👉 스택이라는 자료 구조에서 제공하는 기능은 다음과 같습니다.

1) push(data) : 맨 앞에 데이터 넣기

def push(self, value):                 # 현재 [4] 밖에 없다면
    new_head = Node(value)             # [3] 을 만들고!
    new_head.next = self.head          # [3] -> [4] 로 만든다음에
    self.head = new_head               # 현재 head의 값을 [3] 으로 바꿔준다.

2) pop() : 맨 앞의 데이터 뽑기

def pop(self):
    if self.is_empty():                  # 만약 비어있다면 에러!
        return "Stack is empty!"
    delete_head = self.head              # 제거할 node 를 변수에 잡습니다.
    self.head = self.head.next           # 그리고 head 를 현재 head 의 다음 걸로 잡으면 됩니다.
    return delete_head                   # 그리고 제거할 node 반환

3) peek() : 맨 앞의 데이터 보기

def peek(self):
   if self.is_empty():
        return "Stack is empty!"

    return self.head.data

4) isEmpty() : 스택이 비었는 지 안 비었는 지 여부 반환 해주기

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

 

👀 스택은 뭘로 구현하면 좋을까요??

👉 데이터를 넣고 뽑는 걸 자주하는 자료구조 입니다.

👉 링크드 리스트와 유사하게 구현 할 수 있습니다.

---

👀 큐란?

👉 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형 구조 (선입선출?)

 

실생활적인 예시를 들어 보겠습니다.

 

큐란 자료구조는 "놀이기구"를 떠올리시면 됩니다.

 

놀이기구는 한 줄로 섰다가, 한 줄로 나옵니다.

 

데이터를 한쪽 끝으로 넣고, 반대쪽으로 빠져 나옵니다.

 

그러면 가장 처음에 줄을 선 사람은? 가장 빨리 나옵니다!

가장 마지막에 선 사람은? 가장 늦게 나옵니다.

 

이런 자료 구조를 First In First Out이라고 해서 FIFO라고 부릅니다.

 

👀 그렇다면 이런 자료구조는 왜 필요할까요??

👉 순서대로 처리 되어야 하는 일이 필요하기 때문입니다.

 

주문이 들어왔을 때 먼저 들어온 순서대로 처리 해야 할 때 혹은 먼저 해야 하는 일들을 저장하고 싶을 때

큐를 사용합니다.

 

👀 큐의 구현은?

👉 큐라는 자료 구조에서 제공하는 기능은 다음과 같습니다.

 

1) enqueue(data) : 맨 뒤에 데이터 추가하기

def enqueue(self, value):              # 현재 [4] -> [2] 인 상태에서
    new_node = Node(value)             # [3] 을 만들고
    self.tail.next = new_node          # 현재 tail 인 [2] 의 다음을 [3] 으로 지정합니다.
    self.tail = new_node	       # 그리고 tail을 [3] 으로 지정합니다.

2) dequeue() : 맨 앞에 데이터 뽑기

def enqueue(self, value):              
    new_node = Node(value)             
	if self.is_empty():                # 만약 비어있다면,
        self.head = new_node           # head 에 new_node를
        self.tail = new_node           # tail 에 new_node를 넣어준다.
        return

    self.tail.next = new_node          
    self.tail = new_node

3) peek() : 맨 앞에 데이터 보기

def peek(self):
    if self.is_empty():
        return "Queue is empty!"
    
    return self.head.data

4) isEmpty() : 큐가 비었는 지 안비었는 지 여부 반환 해주기

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

 

👀 큐는 뭘로 구현하면 좋을까요?

👉 데이터를 넣고 뽑는 걸 자주하는 자료구조입니다!

👉 스택과 마찬가지로 링크드 리스트와 유사하게 구현 할 수 있습니다.