[자료구조/알고리즘] 스택(Stack)과 큐(Queue)

스택과 큐는 모두 배열과 관련된 자료구조이다. 데이터의 출입이 배열의 한 쪽과 양 쪽에서 일어난다는 것이 각각의 특징이다.

 

1. 스택(Stack)

stack 예시, 출처 _ 위키백과

한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)의 자료 구조를 말한다. 이름에서 느껴지듯 데이터를 순서대로 쌓아나갈 수 있다. 하나의 데이터를 stack 안에 집어넣는 것을 push, 빼내는 것을 pop이라 말하며, 파이썬의 list를 기준으로는 append/pop이 그 명령어가 되겠다. 그림 예시에서 2의 데이터를 빼내고 싶다면, 순서대로 6,5,4,3을 pop 해야만 2를 빼낼 수 있다.

> stack과 관련된 문제 예시: https://mingchin.tistory.com/99

[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 큰 수 만들기

> stack의 활용 예시: Javascript Linter(린터) - 문법 교정기

( var x = 2; 등 쌍으로 나와야하는 것들이 제대로 짝지어 사용되고 있는지 stack을 통해 확인할 수 있다. 코드의 앞 부분부터 괄호가 등장하면 stack에 쌓아 두었다가, 해당 괄호의 짝이 등장하면 stack에서 pop하는 방식으로 구현이 가능하다. 올바른 문법으로 작성된 코드의 경우 문장이 끝나면 해당 stack이 비어있어야 한다.

 

2. 큐(Queue)

Queue 예시, 출처 _ 나무위키

선입선출(先入先出, First In First Out; FIFO)의 자료구조를 말한다. 대기열이라고도 하며, 단어의 뜻 자체가 무언가 사기 위해 서는 줄을 말한다. 실제 계산대에 줄서는 방식이 큐의 대표적인 예라고 생각하면 된다. (먼저 줄을 선 사람이 계산 후 빠져나가고, 뒤에 온 사람은 줄을 서 차례를 기다림) 즉 데이터가 들어가는 입구와 나가는 출구가 양쪽에 별도로 존재하며, 데이터를 집어넣는 행위를 Enqueue, 빼내는 행위를 Dequeue라 부른다. 역시나 파이썬에서는 list로 구현할 수 있는데, 이때 관련된 명령어는 append와 pop(0)이 되겠다.

외에도 우선순위 큐, 원형큐 등의 응용된 형태의 자료구조도 있다.

[참고]

2개의 Stack으로 Queue 구현하기: https://www.youtube.com/watch?v=t45d7CgDaDM

 

> Queue와 관련된 문제: https://mingchin.tistory.com/101

[코딩 테스트 연습(파이썬/Python)] 프로그래머스 _ 다리를 지나는 트럭