스택과 큐 [자료구조]

해당 글은 프로그래머스 [고득점 알고리즘 kit. 스택/큐 - 기능개발] 문제를 풀면서 스택과 큐 개념에 대해 정립할 필요를 느끼고 정리한 글입니다!! 해당 문제가 궁금하시면 아래 사이트를 방문해주세요~!!

프로그래머스

 

🔖 스택(Stack)?? 

스택은 "쌓다"라는 의미를 가진 단어로, 알고리즘에서는 아래 그림과 같이 '데이터를 차곡차곡 쌓은 구조'를 의미한다. 

그림1. LIFO (Last In First Out)

 

스택은 자료구조에서 메인 장으로 다뤄야 할 정도로 중요하고 자주 쓰이는 개념이다. 데이터가 순차적으로 쌓일 때 처리하는 방식이라던지, 접근 방식이라던지, 삭제하는 방식이라던지, 다른 자료구조(ex. 큐)와는 다소 다른 특징을 지니고 있다.

 

---

 

1️⃣ 스택의 특징

 스택은 '후입선출(LIFO : Last In First Out)'의 원리를 갖고 삽입과 삭제를 수행하는 자료구조의 주요 개념이다. 여기서 삽입은 Push, 삭제는 Pop 이라 한다.

 보통 인터넷 브라우저의 예시를 통해 많이 설명하는데, '뒤로가기' 기능이 대표적인 예시다. 새로운 사이트를 방문할 때마다 해당 사이트의 주소를 스택에 Push하고, 유저가 뒤로가기를 누르면 스택의 Pop 기능을 통해 이전 사이트로 돌아가는 식이다. 

 

Ex) 티스토리 메인 페이지 🔜 (Push) 🔜  'JOON__HK's 기획/개발 STORY' 🔜  (POP) 🔜  '티스토리 메인 페이지'

Ex) 마트에서 우유를 고를 때. 유통기한이 긴 우유('맨 뒤에 있는 녀석')를 꺼내가는 것처럼... ("나만 그런가?")

 

2️⃣ 파이썬 스택 구현 함수 (리스트)

• append() : 리스트의 가장 뒤쪽에 데이터를 삽입하는 함수
• pop() : 리스트의 마지막 데이터를 꺼내는 (+ 원래 리스트에서 삭제) 함수
• is_empty() : 리스트가 빈 스택인지 확인하는 함수
• peek() : 리스트의 마지막 데이터가 무엇인지 확인하는 (+ pop과 달리 삭제는 x) 함수

Ex) 단어를 역순으로 출력할 때 (*스택 클래스 활용)

def word_reverse(word): # word = "aircraft"
    ex_s = Stack()
    ret_str = ""

    for w in word:
	ex_s.push(w)

    while not ex_s.is_empty():
	ret_answer += ex_s.pop()
    return ret_answer # ret_answer = "tfarcria"

 

#️⃣ 보통 자료구조(Data Structure)를 공부할 때 파이썬보다는 C++을 많이들 언급하기에, 스택을 구현하기 위한 C++의 함수도 언급하고 넘어가겠다. 

• push(변수) : 변수를 스택의 맨 위에 삽입
• pop() : 스택의 맨 위에 있는 항목을 삭제
• empty() : 스택이 비어있는지 확인 후 boolean 타입의 값을 반환
• size() : 스택에 들어있는 원소의 개수를 반환
• top() : 스택의 맨 위에 있는 항목을 반환

 스택은 구현하기 간단한 컨테이너 구조이기 때문에, 순서가 별로 중요하지 않은 경우에 활용하기 좋다. 특히 중첩된 구조를 처리할 때라던지, 재귀함수를 구현할 때라던지, DFS 등.

 

 

🔖 큐(Queue)?? 

흔히 편의점에서 알바를 해봤거나, 음료수, 상품 진열의 경험이 있는 사람이라면 '선입선출(FIFO : First In First Out)'이라는 개념을 기본 탑재하고 있을 것이다. (본인은 군 시절 px병을 잠깐... ㅋㅋㅋ) 큐에 데이터를 넣을 때에는 스택과 마찬가지로 마지막에 데이터를 추가한다. 하지만 데이터를 꺼낼 때는 가장 앞에 있는 요소부터 꺼낸다. 음료수를 예로 들면, 유통기한이 길게 남은 음료수들은 뒤에 점점 쌓이면서 내려오고, 앞의 진열대에서는 유통기한이 얼마 남지 않은 음료가 꺼내지는 방식이다. 

그림2. FIFO (First In First Out)

1️⃣ 큐의 특징

 스택은 선입선출(FIFO : First In First Out)의 원리를 갖고 큐와 함께 삽입과 삭제를 수행하는 자료구조다. 큐는 스택과 동일하게 삽입은 Push, 삭제는 Pop 을 사용한다. 대신 pop()을 사용하면, 맨 뒤의 항목을 삭제했던 스택과는 달리 큐의 맨 앞에 있는 항목을 삭제한다.

 

 이처럼 큐는 양쪽 끝에 대해 작업을 처리해야 하므로 스택보다는 구현이 조금 까다롭다. 파이썬에서 큐를 구현하려면 리스트의 한 쪽 끝에 원소를 추가하고 pop을 할 때마다 리스트의 원소를 한 칸씩 당기는 방법이 있다. 하지만 pop을 할 때마다 모든 원소를 앞으로 옮겨야 하므로 데이터의 크기가 클 경우, 이는 비효율적인 방법이 될 수 있다. 

 이럴 때는 큐의 첫 번째와 마지막 원소에 대한 인덱스를 따로 관리하면서 원형으로 큐를 사용하면 공간을 재활용할 수 있으면서 보다 효율적으로 관리가 가능하다. 

 

2️⃣ 파이썬 큐 구현 함수

• enqueue() : 큐의 맨 끝에 항목을 추가하는 함수
• dequeue() : 큐의 맨 앞에 있는 항목을 제거하는 함수
• peek() : 큐의 맨 앞에 있는 항목을 반환하는 함수
• isfull() : 큐가 가득 찼는지 확인하는 함수
• isempty() : 큐가 비어있는지 boolean 타입으로 반환하는 함수

 

#️⃣ 큐의 종류

선형 큐 (Linear Queue)

기본 큐의 형태로써 앞선 그림2와 같은 형태로 되어있다. 배열로 구현 시 크기가 제한되어 있고, 빈 공간을 사용하기 위해선 모든 자료를 꺼내거나 내부 원소들을 한 칸씩 옮겨야 하는 단점이 있다. 

 

Ex) Queue 뒤집기

def queue_reverse(Q): # Queue 뒤집기
    ex_s = []
    while not Q.is_empty():
        ex_s.append(q.dequeue()) # ex_s에 dequeue() 한 값을 리스트 뒤에 추가.
    while ex_s:
        Q.enqueue(s.pop()) # ex_s의 길이가 0이 아니면, ex_s의 뒤 원소들을 pop해서 Q에 다시 입력.

def display(q: Queue) -> None:
    node = q.front
    while node:
        print(node.data, end = " ")
        node = node.next
    print()


Q = Queue() # 0, 1, 2, 3, 4
for i in range(5):
    Q.enqueue(i)
display(Q) # 0, 1, 2, 3, 4

queue_reverse(Q)
display(Q) # 4, 3, 2, 1, 0

환형 큐 (Circular Queue)

그림3. 환형 큐(Circular Queue)

 

선형 큐의 문제점을 보완한 형태의 큐. 1차원 배열(리스트) 형태의 큐를 원형으로 구성해 배열의 처음과 끝을 연결해서 만든다. 어떠한 작업/데이터를 순서대로 사용하기 위해 대기시킬 때 사용하거나, 
 Ex) CPU 스케줄링, 디스크 스케줄링

 

서로 다른 작업환경 또는 프로세스 사이에서 자료를 주고 받을 때 자료를 일시적으로 저장하는 용도로 많이 사용한다. (== 비동기 전송)
Ex) IO 버퍼, 파이프, 파일 IO 

 

 

 

 

📋 Reference

https://wikidocs.net/192523

02. 스택과 큐

https://wikidocs.net/192523

05. 파이썬으로 큐 구현하기

https://wikidocs.net/192069

04. 파이썬으로 스택 구현하기

 

이미지 출처) "https://www.flaticon.com/kr/free-icons/"  제작자: Alfredo Creates - Flaticon