[자료구조] 스택(Stack)과 큐(Queue)

본 포스팅은 Python을 기준으로 자료구조를 설명하니 참고부탁드립니다.

스택이란?

스택(Stack)

스택은 한쪽 끝에서만 데이터를 넣거나 뺄 수 있는 후입 선출(LIFO - Last In First Out) 구조로 되어있습니다.

 

데이터를 넣는것을 PUSH, 데이터를 꺼내는 것을 POP이라고 합니다. 이때 꺼내지는 데이터는 마지막에 넣은 데이터부터 나오게 됩니다.

이 외에도 top, empty 기능이 있지만 이 글에서는 다루지 않겠습니다.

스택에 대한 자세한 설명은 아래의 링크를 참조해 주세요

https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D

스택 - 위키백과, 우리 모두의 백과사전

실생활에서 예를 들면 그릇을 선반에 넣을 때 그릇은 위로 쌓이고 그릇을 꺼낼 때는 마지막에 넣은(가장 위) 그릇을 꺼내 쓰게 됩니다. 이 과정에서 그릇을 선반에 넣는 행위를 PUSH, 그릇을 꺼내는 행위를 POP이라고 합니다. 이때 그릇을 넣은 선반은 스택, 그릇은 데이터라고 말할 수 있습니다.

사용 방법

파이썬에서는 list를 스택으로 활용이 가능합니다.

append(push), pop 메소드를 사용하면 스택의 기능과 동일하게 사용이 가능합니다.

stack = list()

stack.append(1)
stack.append(2) # [1, 2]

stack.pop() # [2] 2가 반환

stack # [1] 2가 반환되고 먼저 넣은 1만 존재

위에서는 list가 제공하는 메소드로 간단하게 설명을 했지만, 이 글을 읽고 계신 분들은 해당 메서드를 활용해서 push, pop 함수를 직접 구현해보면 좋을 것 같습니다.

큐란?

큐(Queue)

큐는 먼저 넣은 데이터가 먼저 나오는 선입 선출(FIFO - First In First Out) 구조로 되어 있습니다.

 

스택은 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 후입 선출(LIFO - Last In First Out) 구조로 되어있습니다.

데이터를 넣는것을 PUT, 데이터를 꺼내는 것을 GET이라고 합니다. 이때 꺼내지는 데이터는 먼저 들어온 데이터가 나오게 됩니다.

이 외에 자세한 설명은 아래의 링크를 참조해주세요

https://ko.wikipedia.org/wiki/%ED%81%90_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

큐 (자료 구조) - 위키백과, 우리 모두의 백과사전

실생활에서 예를 들면 놀이공원에서 기구를 타기위해 줄을 서고 먼저 줄을 섰던 사람이 기구를 먼저 타는 것을 큐라고 할 수 있습니다. 이외에도 '선착순'이라는 단어로 큐를 설명 할 수 있습니다.

사용 방법

파이썬 내장 모듈인 queue를 통해 사용할 수 있습니다.

스택은 list가 제공하는 메소드 만으로도 구현이 가능하고 이해가 되서 함수 구현을 생략했지만 list를 활용해 큐를 구현해 보겠습니다.

# queue 모듈 사용방법
import queue

data_queue = queue.Queue()

data_queue.put("data1")
data_queue.put("data2")

data_queue.qsize() # 2

data_queue.get() # data1
data_queue.get() # data2

# list를 활용한 큐 구현
queue = list()

def put(data):
	queue.append(data)

def get():
    data = queue[0]
    del queue[0]
    return data
	
put("data1")
put("data2")

len(queue) # 2

get() # data1
get() # data2

 

관련문제

https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

참고하면 좋은 사이트

https://visualgo.net/ko/list

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

위의 링크는 자료구조를 시각적으로 볼 수 있는 사이트입니다.

스택과 큐 이해가 잘 안되신다면 위의 사이트에서 테스트를 해보며 공부하는걸 추천드립니다.