밸~하!

오늘은 자료구조 중 기초 스택과 큐에 대해서 알아보겠습니다!

먼저 스택에 대해서 알아보겠습니다!

스택 저희가 게임을 하거나 여러가지 활동을 하거나 할때
스택이라는 말을 종종 쓰기도 하죠??

그럼 자료구조에서의 스택은 어떤것을 의미하는지 한번 알아보겠습니다!

1. 스택이란?

스택이란
Last In First Out 이라는 개념을 가진 선형 자료구조 입니다!

즉 나중에 들어간 요소가 먼저 들어간 요소보다 먼저 나온다는 뜻입니다!

쉽게 생각해서
상자를 생각해보겠습니다!
상자에 물건을 넣으면 먼저 넣은것들부터 아래에 쌓이게 되고 마지막에 넣은것이 위로 오게되죠?
그런것과 비슷하다고 생각하시면 이해가 쉬우실 것입니다!

여기서 스택에 요소를 추가하는것을 push 요소를 제거하는것을 pop이라고 합니다!

그리고 제일 위 곧 가장 마지막에 들어있는 요소를 top이라고 표현합니다!

이해를 돕기 위해 조금더 쉬운 예시를 들어보겠습니다

과자 프링글스를 한번 생각해 보겠습니다!

프링글스는 아래있는 과자를 꺼내고 싶어도 바로 못꺼내고 위에서 부터 하나씩 꺼내야하죠??
스택은 마치 프링글스의 과자와 같다고 생각하면 조금 더 이해가 쉬울 것입니다

스택은 간단합니다
바로 요소를 넣을 수 있는 push와 요소를 제거할 수 있는 pop만이 존재합니다
가장 위의 요소만 제어하기에 구현하는데도 어렵지가 않습니다

그럼 스택은 어디에서 쓰일까요??

스택을 사용하는곳은 가장 먼저 스택 메모리 입니다

스택메모리란?

함수가 호출되며 생성되는 지역변수, 매개변수가 저장되는 메모리 영역입니다!

스택 메모리의 예제를 한번 봐보겠습니다

function sum(a, b) {
  return a + b;
}

function print(value) {
  console.log(value);
}

print(sum(5, 10));

먼저 가장 안쪽에 위치한 sum함수가 실행 됩니다!
sum함수가 실행되면서 스택메모리에는
매개변수,반환주소값,지역변수가
push되며 기록이 됩니다

sum함수 실행이 종료되어 값이 반환되면
스택메모리에서 pop이 실행되며 제거가 됩니다!

이어서 print함수가 실행이 됩니다
아까 반환된 값 (sum함수가 실행되고 종료될때 반환된 값)
으로 실행되어 스택 메모리에 기록이됩니다

print함수 안에는 console.log 함수가 있습니다
그렇기에
스택메모리에는 Print함수 위에 console.log 함수가 기록이 됩니다
이후 console.log 함수가 실행후 종료가 되면 스택메모리에서 console.log함수가 삭제가 됩니다

이후 print함수도 실행이 종료가 되어 스택메모리에서 삭제가 됩니다

이렇게 함수는 스택메모리에 기록이 되고 실행 후 삭제가 됩니다!

자! 이렇게 이론에 대해서 알아보았는데요
이것을 어떻게 코드로 표현할 수 있을까요??

먼저 배열로 표현할 수가 있는데요!

배열에 push를 하면 데이터가 순차적으로 들어가는것을 확인할 수 있습니당
그리고 pop을 사용하면 배열의 가장 마지막 요소가 나오게 됩니다!

이러한 방식은 중간요소 추가 삭제로직이 추가되지 않기때문에 매우 유리한 방식이라고도 할 수 있습니다!

게다가 javascript 에서는 배열의 크기가 정해진것이 아니라 동적으로 변하기 때문에 더 편하게 구현을 할 수 있습니다!

두 번째 방식으로는 지난시간에 포스팅했던
연결 리스트로 표현할 수 있습니다!

C언어나 java와 같은 언어에서 스택의 크기가 고정되지않는 경우 연결리스트를 이용해서 스택을 구현하는 경우가 있습니당

이 경우에는 연결리스트의 head가 top이라고 할 수 있습니다

이번엔 큐에 대해서 알아보겠습니다!

2. 큐 란?

큐는 First In First Out이라는 개념을 가진 선형 자료구조 입니다!
즉 먼저들어간 것이 먼저 나오고 나중에 들어간 것이 나중에 나온다는 것입니다!

큐의 구조에 대해서 잠깐 알아보겠습니다!

큐의 제일 앞에 있는 요소를 Front라고 부르고 제일 마지막에 있는것을 Rear라고 부릅니다!
그리고 큐에 요소를 추가하는 것을
EnQueue라고 부르고
큐에 요소를 제거하는 것을
DeQueue라고 부릅니다!

큐의 종류에는 두가지가 있는데요!

먼저는 Linear Queue(선형 큐) 와 Circular Queue(환형 큐)가 있습니다!
종류에 대해서는 뒤에서 추가로 설명하겠습니다!

큐를 일상생활에서 볼 수 있는것은 대기열을 일종의 큐라고도 할 수 있습니다
가장 일찍 온 사람이 가장 먼저들어가고 먼저 온 순서대로 입장을 하게되기 때문입니다!

그럼 큐에 대해서 본격적으로 알아보겠습니다

먼저

Linear Queue(선형 큐)

에 대해서 알아보겠습니다!

선형 큐는 두가지 방식으로 구현할 수 있습니다

첫 번째 방법(Array)

먼저 선형 큐는 배열로 표현할 수 있습니다
하지만 스택과는 다르게 배열에서 사용하는데 조금 어렵습니다!

한번 예시를 들어보겠습니다

먼저 스택처럼 큐도 배열에 요소를 순서대로 담을 수 있습니다
여기서 DeQueue를 한다면 앞에 있는 요소부터 나오게 됩니다
하지만 배열이기 때문에 빈 공간이 메꿔지지는 않습니다
그렇기에 배열에서는 DeQueue를 하고 EnQueue즉 배열의 앞요소를 제거하고 뒤에서 요소를 넣게 된다면
배열이 어느순간 가득 차게되어 요소를 추가할 수 없게됩니다!

물론 javascript에서는 배열의 크기가 자유롭게 증가되기 때문에 이런 문제가 없겠지만
문제는 Front와 Rear의 인덱스가 무한정 커질 수 있다는 문제가 있습니다

따라서 배열의 공간을 더 효율적으로 쓰기위해 뒤에있는 요소들을 앞에 있는 공간들로 당기는 작업이 필요하게 됩니다!

이 작업을 수행하려면 한개씩 전부 앞으로 당겨야 하기에 O(n)즉 선형시간이 필요하게 됩니다!

그럼 이런 문제를 어떻게 해결할 수 있을까요??

여기서 두번째 방법이 나오는데요

바로 Linked List를 이용하면 해결을 할 수 있습니다

두 번째 방법(Linked List)

Linked List로 구현을 하게 되면
연결리스트의 Head부분이 Front가 되게 되고 Rear부분이 tail이 되게 됩니다

배열대신 연결리스트를 사용하게 된다면 index에 관한 문제를 해결 할 수가 있습니다

자 이렇게 선형 큐를 구현하는 두가지 방법에 대해서 알아보았는데요
여기서 한가지 주의해야 할 점이 있습니다

주의해야 할 점

바로 shift함수 사용인데요
그 이유는 shift함수를 사용하게 된다면 시간복잡도가 O(n)즉 선형 시간이 걸리기 때문입니다
그렇기에 queue에서 기대하는 로직이 수행되지 않습니다

그 다음은

Circular Queue (환형 큐)

환형 큐는 환형 연결리스트처럼 Front와 Rear가 이어져 있는 Queue입니다!

이 자료구조는 한정된 공간을 효율적으로 이용할 때 사용하는 자료구조 입니다!

그렇기에 연결리스트로 구현해도 상관은 없지만 큰 이점은 없게됩니다!

자 이렇게 오늘은 큐와 스택에 대해서 알아보았는데요!

각각 자주 쓰이는 자료구조인 만큼 많은 학습이 필요한것 같습니당~

그럼 이만 밸~바!