알고리즘

[자료구조] 스택, 큐는 무엇인가? :: 마이구미

mygumi 2019. 9. 7. 22:35
반응형
이 글은 자료구조의 "스택, 큐" 를 다룬다.
자료구조에서 가장 먼저 나오는 기본적인 자료구조이다.
각 자료구조에 대한 깊은 설명보다는 현실적인 이해에 도움을 위해 다루려고 노력했다.


알고리즘 문제를 풀기 위해 알아야하는 지식을 위한 설명이 아닌, 현실적으로 활용할 수 있는 이해를 위한 도움에 중점을 둔다.

실제로 요즘은 자료구조를 생각하지않고도 코드를 작성할 수 있다.

예를 들어, 스택과 큐와 같은 개념은 배열로 처리하면 그만이다.

하지만 이 과정에서도 자료구조의 개념을 인지하고 활용하면 분명 코드와 개발에 도움이 된다.

본인은 왜 코딩테스트가 존재하는지도 연관이 있다고 생각한다.

자료구조를 구현하기 위한 코드를 작성해야하는가? 에 대한 글은 다른 글을 참고하길 바란다.

 

자료구조에서 가장 기본적인 스택, 큐는 이해하기 쉽다.

모든 자료구조는 구체적인 이해보다는 조금 더 다른 관점으로 개념을 이해하는 것이 좋다.

스택과 큐는 가장 기본적인 개념으로써, 이 개념을 포함하는 또 다른 자료구조가 존재한다.

예를 들어, DFS 는 스택을 활용하고, BFS 는 큐를 활용한다. (DFS, BFS)

또한 메모리, 스케쥴링 등 우리가 인지하는 못하고 보지 못하는 곳에서 이루어지고 있는 개념이다.

 

 

결과적으로 스택(Stack)은 나중에 넣은 데이터가 먼저 나오는 형태, 큐(Queue)는 먼저 넣은 데이터가 먼저 나오는 형태이다.

참고로 덱(Deque)은 스택과 큐를 합친 형태이다.

 

스택이란 무엇인가?

 

객체들의 집합소로써, 데이터를 기록하는 구조라고 보면 된다.

하지만 접근 방법에 제한을 두고 있다.

접근 방법은 LIFO(Last Input First Out) 라고 부르며, 마지막에 넣은 요소가 먼저 나온다는 의미이다.

그림을 보면 이해하기 쉽다.

 

 

아래가 막혀있고 위가 뚫린 형태로써, 차곡차곡 쌓는 구조이다.

이러한 구조이기에, 마지막에 삽입한 요소는 가장 처음으로 삭제할 수 있다.

스택에서 삽입은 PUSH, 삭제는 POP 이라는 용어로 사용하고 있다.

 

우리는 스택오버플로우라는 에러를 많이 접했을 것이다.

해석 그대로, 위처럼 정해진 크기에 무언가를 계속 넣고 있다가 받아들일 수 있는 크기를 초과해서 흘러넘쳐버린 것을 의미한다.

흔히, 재귀함수를 호출할 때 많이 경험한다.

 

 

이러한 개념은 우리가 실제로 많이 접하고 있다.

브라우저에서 뒤로 가기, 문서 작업에서 컨트롤 + Z 와 같은 이전 상태로 되돌리기 등처럼 캐시와 같은 모습으로 많이 존재한다.

이러한 개념은 이외에도 많은 곳에서 활용되고 있다.

 

개인적으로는 컴퓨터가 어떻게 사칙연산을 계산하는지를 이해하면 좋겠다고 생각한다.

사람은 눈으로 연산자와 괄호 등을 보고 우선순위를 판단하여 계산한다.

하지만 컴퓨터는 어떻게 계산할까? 이를 위해 스택이 사용되고 있다.

"후위 표기법" 이라는 것을 검색해서 확인해보길 바란다.

백준 알고리즘을 풀고 있다면, 관련 문제를 풀어보길 바란다. (https://mygumi.tistory.com/181)

 

큐는 무엇인가?

 

큐는 단순히 스택의 반대 개념을 갖는다.

접근 방법은 FIFO (First Input First Out) 라고 불리며, 먼저 들어간 데이터가 먼저 나오는 구조이다.

 

 

우리가 흔히 접할 수 있는 순서대로 처리하는 형태이다.

물건을 구매하기 위해, 줄을 선 순서대로 살 수 있는 그러한 구조이다.

이러한 구조이기에, 마지막에 삽입한 요소를 삭제하기 위해서는 앞에 요소들이 전부 삭제되어야한다.


주로 순서를 보장하기 위한 처리가 필요할 때 사용된다.

큐에 저장된 요소들은 순서대로 존재하고, 가장 앞에 있을수록, 오래 기다리고 있다는 것을 의미한다.

예를 들어, CPU는 하나의 태스트가 처리가 완료되어야 다음 태스크를 처리함으로써, 실행 순서대로 처리하게 된다.

우리는 이러한 개념을 많은 아이디어를 통해 활용할 수 있다.

 

예를 들어, 네트워크 연결 상태를 확인해보자.

우리는 코드가 연결되지않다고 판단하는 즉시 알림을 주는 코드를 작성했다.

 

setInterval(() => {
  if (!checkNetwork()) {
    // 네트워크 끊어짐
  };
}, 1000);

function checkNetwork() {
  if (네트워크 연결 되었음) {
  	return true;
  } else {
  	return false;
  }
}

 

위 코드는 1초마다 네트워크 상태를 확인한다.

하지만 굉장히 불안정하여 1초마다 "연결"과 "연결되지않음"을 반복하는 상황이 있다가 다시 안정화가 되었다고 가정해본다.

결국 불안정한 시기가 있지만, 결과적으로는 안정화가 되었다.

하지만 이 코드는 "연결되지않음" 상태가 한번이라도 존재하면, 연결이 끊어졌다고 판단한다.

결과적으로 네트워크 상태는 끊어졌다고 판단했다.

 

5초이상 네트워크가 끊어졌을 경우에만 네트워크가 연결되지 않았다고 판단하는 코드를 작성해본다.

이를 위해 우리는 큐를 활용할 수 있다.

 

  1. 큐의 길이는 5을 가진다.
  2. 큐에 1초마다 네트워크 상태를 삽입한다.
  3. 큐가 가득차면 맨 앞에 있는 값을 삭제한 후, 새로운 값을 삽입한다.

 

const interval = setInterval(async () => {
const result = await checkNetwork();

queue.push(result); // 삽입
if (queue.length > 5) {
  queue.shift(); // 삭제
}
}, 1000);

 

위 코드는 1초마다 네트워크 상태를 확인하는 함수가 호출되고, 큐는 그때마다 오래된 값를 삭제하고, 새로운 값을 삽입한다.

위 코드의 흐름의 상태를 그림으로 보면 다음과 같다.

 

 

연결이 안정할 때는 모든 값이 true 일 것이고, 불안정할때는 큐의 값이 true 와 false 가 섞여서 존재할 것이다.

그러다가 큐의 모든 값이 fasle 로 동일할 때만 네트워크가 끊어졌다는 걸 판단할 수 있다.

즉, 5초동안 연속적으로 네트워크가 끊어졌을 때만, 끊어졌다고 판단할 수 있다.

코드로 작성하면 다음과 같다.

 

const interval = setInterval(async () => {
  const result = await checkNetwork();

  queue.push(result); // 삽입
  if (queue.length > 5) {
    if (queue.every(item => !item)) {
      toast.error('네트워크 연결이 되지 않았습니다!');
    }
  }
}, 1000);

 

이렇게 큐의 개념을 활용하여 많은 곳에 접목시킬 수 있다.

 

무엇인지 이해하기보다는 추상적인 개념을 받아들여 기능과 목적에 따라, 우리가 구현하면 된다.

단순히 구현된 코드보다는 개념을 따르는 코드가 본인과 상대방에게 보다 명확하게 목적이 파악될 수 있다.

예를 들어 LIFO 를 따르는 구조라면, 굳이 양쪽 모두 접근할 수 있는 리스트와 같은 구조보다는 스택이 낫다.

 

암기가 아니라 이해를 말하고 싶었지만, 잘 표현한 지 모르겠다.

아무튼 자료구조를 직접적으로 사용하는 것은 현재로썬, 사실 어렵고 많지 않다.

자료구조를 사용하는 거에 초점을 두기보다는 그 개념을 이해하여 접목할 수 있는 곳을 판단하여 사용하는 것이 효율적이다.

반응형