01. Stack & Queue

Stack

 

1. Stack 

• 가장 마지막에 삽입된 데이터를 가장 먼저 삭제하는 방식
• 후입선출 (LIFO, Last in First out)
• 정해진 방향으로만 데이터를 쌓을 수 있음

 

2. 사용 방법

    : 리스트를 통해 코드를 작성할 경우,

      가장 마지막에 추가한 데이터를 가장 먼저 삭제하도록 (LIFO) 해야 하므로

      .append()를 이용하여 새로운 값을 추가한 후,

      .pop()을 이용하여 가장 마지막에 있는 값 (방금 새로 추가한 값)을 삭제하면 된다.

stack = [1,2,3,4]
stack

stack 리스트에 [1,2,3,4]가 들어있다.

 

stack.append(5)
stack

stack 리스트에 5라는 값이 맨뒤에 추가된다.

stack.pop()

pop을 통해 가장 마지막에 있는 값이 나온다.

 

stack을 이용해 코드를 구현하고 싶을 경우 이와 같이 append()와 pop()을 이용하면 좋다.

 

 

 

Queue

 

1. Queue란?

• 맨 처음에 넣은 데이터부터 차례로 삭제하는 방식
• 선입선출 (FIFO, First in First out)
• 한쪽 끝에서는 삽입, 반대편 끝쪽에서는 삭제가 이루어짐

 

2. 사용 방법

    : 리스트를 통해 코드를 작성할 경우,

      가장 처음에 넣은 데이터부터 차례로 삭제해야하므로

      .append()를 통해 데이터를 삽입하면 이 데이터는 기존 리스트의 가장 마지막에 저장되므로

      .pop(0)를 이용하여 가장 앞에 있는 데이터부터 삭제하면 된다.

queue = [1,2,3,4]
queue

queue 리스트에 [1,2,3,4] 가 들어있다.

 

queue.append(6)
queue

append()를 통해 6을 넣었고 가장 마지막에 위치하는 것을 볼 수 있다.

 

queue.pop(0)

가장 앞에 있는 값을 출력하기 위해 .pop(0)를 사용하였다.

 

queue의 방식으로 코드를 구현하고 싶은 경우, 이와 같이 append()와 pop(0)를 이용하면 좋다.

 

 

Deque

 

1. Python을 이용하여 Queue를 구현하는 경우 단점

    탐색 알고리즘에서 Python을 이용하여  Queue를 구현하는 경우 속도가 매우 느릴 수 있다.

     따라서, 이 경우엔 리스트 대신  deque를 사용하는 것이 더 좋다.

 

 

2. 사용 방법

   

from collections import deque

a_dq = deque([1,2,3])
a_dq

 

deque를 이용하여 출력하면 이와 같이 저장된 것을 볼 수 있다.

 

a_dq.append(4)
a_dq

값을 추가할 경우, 리스트와 같이 append를 이용하여 추가할 수 있다.

 

a_dq.popleft()
a_dq

하지만, 맨 왼쪽(앞)의 값을 뺄 경우, pop(0) 대신 popleft()를 이용하여야 한다는 차이점이 있다.