Stack & Que, 스택과 큐 이해하기

Stack & Que

Stack(스택)

스택이란?

Stack 이란 무엇일까? 사전에서 검색해보면 다음과 같이 나온다.

1. (보통 깔끔하게 잘 정돈된) 무더기
2. 많음, 다량
3. (깔끔하게 정돈하여) 쌓다, 쌀이다, 포개지다.

사전적 의미에서 잘 알 수 있듯이 스택은 무엇인가를 잘 쌓아 올린것이다.
컴퓨터에서는 무엇을 쌓아 올릴까? 대표적으로 메모리를 쌓아올린다. 그렇다면 어떻게 쌓아 올릴까?

스택의 과정

스택은 LIFO(Last In First Out) 구조를 따른다. 즉 마지막으로 넣은 데이터가 먼저 출력된다는 의미이다.
다음 그림을 살펴보자!

1칸당 1byte씩 총 4byte가 있는 메모리가 있다. 지금은 빈 메모리이지만 이곳에 메모리가 하나 둘씩 추가될 것이다.
이 메모리 구조는 아래에서부터 차곡차곡 적재되어야 하고 위에서부터 빼야한다.
가령 1,2,3,4 를 순서대로 적재한다고 하면 메모리에는 다음과 같이 데이터가 쌓인다.

아래에서 부터 순차적으로 쌓이게 된다.
그렇다면 이 메모리에서 모든 값들을 추출할 때, 출력되는 순서는 어떻게 될까?
입력한것과는 반대로 4 -> 3 -> 2 -> 1 순서로 출력되게 될 것이다.

이처럼 스택은 아래(0번 인덱스)에서부터 쌓이고 뽑아낼 때에는 위(마지막으로 적재한 인덱스)부터 뽑아낼 수 있다.

스택의 연산

스택의 연산은 2가지이다.

• 데이터를 적재하는 삽입연산 : Push
• 데이터를 추출하고 메모리에서 삭제하는 삭제연산 : Pop

스텍을 구현하려면 다음과 같은 것들이 필요하다.

• 배열
• top 을 가리키는 변수

top의 역할은 어느 곳에 데이터를 적재하고 삭제할 지를 알려주는 역할을 한다. 평상시에는 다음 적재할 곳을 가리킨다.
Push를 진행할 때에는 top의 위치에 적재시키고 top을 1 증가시킨다.
Pop을 진행하면 top 값을 하나 감소 시킨루 top이 가리키고 있는 곳을 반환하며 삭제한다.

Stack 구현 예시는 본 저장소에 올려놨습니다. Stack 구현 예시 보기-Python

이렇게 스택을 직접 구현하는 것도 좋지만 사용할 때에는 내장 라이브러리를 이용하면 훨씬 편하게 이용할 수 있다.
Stack은 대부분의 언어가 지원하고 있다.

Python3를 기준으로 다음과 같이 사용 할 수 있습니다.

stack = []
stack.append(1) # Push 하는 작업입니다.
popResult = stack.pop() # Pop 하는 작업입니다.

큐(Queue)

큐(Queue)란?

큐(Queue)를 사전에서 찾아보면 다음과 같이 나온다.

1. (무엇을 기다리는 사람, 자동차 등의) 줄
2. (컴퓨터)큐, 대기행렬

사전적 의미를 보면 기다리는 줄처럼 순서대로 일을 처리하는 자료구조임을 알 수 있다.
즉, 먼저 온 데이터가 먼저 빠져나가는 FIFO(First In First Out) 구조를 이룬다.

스택과 비교

큐와 스택의 가장 큰 차이점은 가장 앞에 있는(가장 먼저 적재된) 데이터를 O(1)의 시간으로 추출 할 수 있다는 것이다. -> FIFO 이기 때문에
큐가 쌀이고 해체되는 작업은 다음 그림과 같다.

적재할때에는 위에서부터 진행하지만 추출할때에는 아래에서부터 추출 할 수 있어 들어온 순서대로 나갈 수 있다.

큐의 연산

큐도 스텍과 마찬가지로 삽입연산과 삭제 연산이 있다.

enQueue : 큐의 삽인연산 (Top 위치에 적재)
deQueue : 큐의 삭제연산 (Rear 위치를 삭재)
(위 그림을 기준으로 이해하기 쉽도록 top과 rear를 설정했습니다.)

삽연하는 과정은 스택과 똑같이 하면 된다. 하나를 적재할때 마다 top의 값을 1씩 증가시키면 된다.
삭제할때도 마찬가지로 rear 값에 있는 것을 삭제하고 1을 증사시캬먼 된다.
지금 설명한 것은 순차큐에 대한 설명이다. 순차큐로만 큐를 구성하다 보면 메모리를 다채우고 다 출력 했을때 다시 사용할 수 없다.
이러한 문제를 해결하기 위해 원형큐와 연결큐라는 것이 고안되었다.

큐의 종류

큐의 종류는 이해하기 쉽도록 다음 그림에 설명하도록 하겠습니다.

순차큐는 일렬로 순차적으로 적재하고 나올 수 있다. 하지만 이전에 사용했던 메모리공간을 다시 사용하기 어렵다는 문제가 발생한다.
원형큐는 순차큐의 문제를 해결한 것이다. 메모리 공간을 효율적으로 사용할 수 있다.
연결큐는 해당 각각의 큐 다음위치에 무엇이 있는지 알수 있도록 진행한 것이다 -> 이러한 것을 Linked List라고 부르는것 같다.
연결쿠의 장점은 큐의 크기를 처음에 지정할 필요 없이 그때 그때 추가시킬 수 있으며 순차큐에서 발생한 메모리 문제도 발생하지 않는다.

연결큐의 파이썬 예시는 다음 링크에 있습니다. 코드보기

스택과 큐를 활용해서 해결한 알고리즘 문제들은 다음 링크를 통해 볼 수 있습니다.

• 프로그래머스 문제(Stack&Que)
• 백준 문제(Stack&Que)