Computer Science

스택, 큐 / ADT, DS 자료구조 / JS의 스택과 큐

hihiha2 2023. 10. 30. 21:58
반응형

스택과 큐는 컴퓨터의 메모리, 자바스크립트의 런타임원리등 공부할 때 자주 등장한 개념이다. 

어느정도 익숙한 개념이지만 정확하게  이해하기 위해서 공부해보았다.

 

스택과 큐는 자료구조를 이해하기 위한 기반이 되며, 이를 통해서 다양한 알고리즘의 구현과 데이터 저장, 관리를 할 수 있다.

따라서 매우 중요한 개념이고 이를 잘 알고 있는 것 또한 중요할 것이다.

 

스택과 큐의 개념을 정확하게 이해하기 위해서는 먼저 ADT와 DS의 정의에 대한 이해가 필요하다.

그래서 ADT와 DS에 대해서 먼저 알아보고, 스택과 큐에 대해서 알아보는 방식으로 공부하였다.

 

 

 

🧷선행학습

💡 ADT와 DS구분하기

 

우선 ADT는 abstract data type의 줄임말로, 말 그대로 자료형을 추상적인 개념으로만 나타내는 것이다.

따라서 구체적인 개념보다는 해당하는 자료형의 특징을 말한다.

"HOW에 대해서는 다루지 않는다!!"

 

DS는 Data Structure의 줄임말로, 일반적으로 말하는 자료구조이다.

ADT의 정의를 실제로 구현하는 것을 의미한다.

 

 

ADT는 추상적인 것을 의미하고, DS는 구체적인 것을 의미한다는 것은 알았지만,

이렇게만 보면 정확하게는 어떤것을 가리키는지 이해하기 어렵다.

 

 

➡️ 그래서 이것을  interface와 class와 동일한 원리로 이해하면 이해하기 쉽다.

객체지향 프로그래밍을 공부하면 항상 빠지지 않고 나오는 것이 interface와 class이다. 

객체지향에서 설명하는 interface는 추상메소드들로 선언만 있는 형태이고, classs는 구현된 개체를 나타낸다.

이와 유사하게 ADT는 해당하는 추상적인 특징만을 기술하고 그것을 실질적으로 구현을 해야만 DS라고 할 수 있다.

interface class
ADT DS

 

 

 

💡 실무에서의 ADT와 DS

ex. 월드컵에서 골을 넣은 선수를 관리하는 자료구조

 

1️⃣ 월드컵에서 골을 넣은 선수를 관리하는 구조를 만든다면, 아래와 같은 ADT를 먼저 도출한다.

① 해당자료는 알파벳순으로 정렬을 할 것이기 때문에 Alphabetical Ordered라는 이름을 짓는다.

② 그런다음  해야할 operation을 지정한다.

   - 사람이름을 넣는 기능을 add()라고 정하고, 삭제는 remove(), 정렬은 get All Players()라고 정한다.

 

이렇게 ADT를 도출했다면, 실제로 자료구조를 만들어야하는 사람이 구체적으로 위의 기능을 수행할 DS를 만든다.

(여기서 중요한 것은 ADT는 함께 도출해서 모든 팀원이 알고 있지만, DS는 가져다 쓰기만 할 수 있다.

구체적 실현체인 DS는 만드는 사람이 ADT를 기반으로 만드는 동안, 다른 팀원들은 자신의 자기역할을 하면 된다.

➡️ 실무의 업무분담 / 모듈화 상향)

"업무를 효율적으로 만든다"

ADT DS
Alphabetical Ordered

 •add(사람이름)
•remove(사람이름)
•get All Players(): 알파벳 순으로 반환

 ➡️ ADT를 실제로 구현하기 위해서 어떤 방법을 사용하는지

ex) 알파벳순으로 정렬하기 위해서 sort()메서드를 사용한다.
중복제거를 위해서 set()를 사용한다...

 

 

 

🖥 ADT관점에서의 스택과 큐

1. 🧱 스택

LIFO(Last in First Out)형태로 데이터를 저장하는 구조

 

"나중에 들어간 것이 먼저 나온다"

 

 

🧱 주요 연산자

push() 스택에 자료를 삽입한다.
pop() 스택에서 자료를 삭제한다.
peek() 스택에서 최상단의 값을 가져온다.

 

🧱 스택 사용사례

스택메모리, 스택 프레임

 

재귀함수와 같은 사용으로 스택이 가득차 넘치게 되는 것을 스택 오버플로우라고 부른다.

 

 

 

2. 🏒 큐

FIFO(First in First Out)형태로 데이터를 저장하는 구조

 

 

한쪽 방향으로 데이터가 삽입되고, 반대방향으로 데이터가 삭제된다.

"먼저 들어간 것이 먼저 나온다."

 

 

 

 

🏒   주요연산자

enqueue() 큐에 자료를 삽입한다.
dequeue() 큐에서 자료를 삭제한다.
peek() 큐에서 해당자료의 값을 가져온다.

 

 

 

🏒  큐 사용사례

producer / consumer architecture

 

큐가 쌓이기만 하고 consume이 되지 않아 넘치는 것을 OutOfMemoryError(아웃오브메모리에러)라고 부른다.

(Java의 힙 메모리를 다 썼을 때 발생)

 

 

⛔️ 주의!!

기술문서에서 큐  ➡️ 항상 FIFO를 의미하는 않는다!!

대기공간으로서의 큐를 의미하기도 한다.

 

 

 

2-2. 🔫 우선순위 큐

큐와 유사하지만 우선순위가 높은 아이템이 먼저 처리됨

 

우선순위 큐 주요동작

insert() 큐에 자료를 삽입한다. (우선순위 정보도 함께 넣는다)
delete() 큐에서 가장 우선순위가 높은 것을 삭제한다.
peek() 큐에서 가장 우선순위가 높은 자료의 값을 가져온다.

 

우선순위 큐 사용사례

프로세스 스케줄링

 

CPU에 ,P1, P2, P3, P4가 있다고 할때 P1이 실행중이면 P2,P3,P4는 ready Queue에서 대기를 한다.

대기하다가 P1의 작업이 끝나면 readt queue에서 가장 우선순위가 높은 것을 다음으로 불러온다.

➡️ 우선순위에 따라서 프로세서를 스케줄링할 수 있다!!

 

 

 

 

 

 

🖥 JS와 스택, 큐

자바스크립트의 런타임환경에 대해서 공부한 사람이라면, 스택과 큐에 대해서 들어봤을 것이다.

자바스크립트엔진에는 함수의 실행순서가 담기는 공간이 콜스택이라는 이름으로 존재한다.

콜스택역시 스택이므로 선입선출의 방식이다.

 

비동기함수들은 callback Queue라는 곳에 대기열로 쌓아둔다.

콜스택이 모두 비워지면 콜백규에 있던 함수들이 콜스택으로 들어간다.

이때 콜백큐는 위에서 설명한 우선순위 큐로서, 우선순위를 갖는 큐들이 먼저 대기열을 빠져나가 콜스택에 쌓인다.

 

➡️ 기본적으로 동기적으로 작동하는 자바스크립트가, 비동기적으로 동작할 수 있는 원리에도 스택과 큐가 숨어있다.

이에 대해서는 따로 포스팅을 한 적이 있어서 더 자세한 내용은 아래 포스팅을 참고하기를 바란다.

 

자바스크립트 동기, 비동기 정의 / 자바스크립트 런타임

동기적이란? 자바스크립트는 단일 스레드 언어로서 한번에 하나의 일만 처리할 수 있다. (=구조상 콜스택이 하나밖에 없다) 이렇게 한번에 하나만의 동작을 하는 것을 동기(syncronous)라고 한다.

hihiha2.tistory.com

 

 

 

 

🖥 DS관점에서의 스택과 큐

자료구조 (Data Structure)

1. 선형구조
(순차적인 순서)		 2.비선형구조
(순서X)
배열 트리
부모와 자식관계
최상위 노드(root)가 존재
한쪽방향으로만
리스트 (단일, 이중, 원형) 그래프
여러경로 존재가능
root가 존재X
다양한 방향존재
스택
LIFO
한쪽방향으로 push, pop이 이루어짐
Chrome에서 뒤로가기 버튼
배열이 유리		  
큐
FIFO
들어온 순서대로 나간다
프린터의 출력순서
연결리스트가 유리		  
데크
스택 + 큐		  

 

🧱 스택의 구현

배열 / 연결리스트를 사용

스택의 구현에는 배열을 이용할수도 있고, 연결리스트를 이용할 수도 있다.

들어온 순서와 반대로 나가기 때문에, 배열을 이용하는 것이 더 좋다.

 

배열로 구현한 스택

연결리스트로 구현한 스택

 

class Stack {
  // 스택을 저장할 배열 생성
  constructor() {
    this.elements = [];
  }

  // 삽입 메서드
  push(element) {
    this.elements.push(element);
  }
  
  // 삭제 메서드
  pop() {
    return this.elements.pop();
  }
  
  // 해당 데이터 불러오기
  peek() {
    return this.elements[this.elements.length - 1];
  }

  //스택이 비어있는지 확인 메서드
  isEmpty() {
    return this.elements.length === 0;
  }

  // 스택에 저장된 요소의 수 확인 메서드
  size() {
    return this.elements.length;
  }
}

// 스택 사용 예제
const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop());  // 3
console.log(stack.peek()); // 2

 

 

 

 

 

 

🏒 큐의 구현

큐의 구현 역시 배열과 연결리스트 모두 이용가능하다.

큐는 먼저 들어온 것이 먼저 빠져나가기 때문에, 배열을 이용한다면 데이터가 한칸씩 모두 이동해야해서 비효율적이다.

따라서 큐는 연결리스트를 이용해서 만드는 것이 효율적이다.

 

배열로 구현한 큐

class Queue {
  
  // 큐 요소 저장할 배열 생성
  constructor() {
    this.elements = [];
  }

  // 삽입 메서드
  enqueue(element) {
    this.elements.push(element);
  }

  // 삭제 메서드
  dequeue() {
    return this.elements.shift();
  }

  // 해당하는 데이터 가져옴
  peek() {
    return this.elements[0];
  }

  // 큐가 비어있는지 확인 메서드
  isEmpty() {
    return this.elements.length === 0;
  }

  // 큐에 저장된 요소의 수 확인 메서드
  size() {
    return this.elements.length;
  }
}

// 큐 사용 예제
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // 1
console.log(queue.peek());    // 2
console.log(queue.dequeue()); // 1
console.log(queue.peek());    // 2

연결리스트로 구현한 큐

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.front = null; // 큐의 맨 앞 요소
    this.rear = null;  // 큐의 맨 뒤 요소
  }

  enqueue(element) {
    const newNode = new Node(element);
    if (this.isEmpty()) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

  dequeue() {
    if (this.isEmpty()) return;
    const removed = this.front;
    this.front = this.front.next;
    if (this.isEmpty()) {
      this.rear = null;
    }
    return removed.data;
  }

  peek() {
    if (this.isEmpty()) return;
    return this.front.data;
  }

  isEmpty() {
    return this.front === null;
  }

  size() {
    let count = 0;
    let current = this.front;
    while (current) {
      count++;
      current = current.next;
    }
    return count;
  }
}

// 큐 사용 예제
const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue()); // 1
console.log(queue.peek());    // 2

 

 

🙋‍♀️ 내 생각

대강 개념은 알고 있었지만, 정확하게 알고 있다고 말하기는 어려웠던 것 같다.

 

후입선출, 선입선출의 방식은 이해하고 있었지만, 더 깊게 공부하고 나니 CPU의 스케줄링이나 자바스크립의 런타임환경과 같이 이전에 공부했던 것들도 더 머릿속에서 정리되는 느낌이다!

 

위에 이론적으로 공부했던 것들을 알고리즘문제를 풀면서 코드로 쳐보려고 한다.

스택과 큐가 중요한만큼 이에 해당하는 문제들이 따로 있는데 프로그래머스에서 찾아보니, 아래와 같이 스택/큐와 관련된 문제모음집이 있었다.

 

🔗 프로그래머스 스택/큐 문제 모음집

 

 

문제들을 풀어나가면서 이론공부한 것을 바탕으로 코드로 구현해볼 생각이다.

 

 

 

 

참고자료

 

쉬운코드: 스택과 큐 설명! 참 쉽죠~~? 기술 문서 읽다가 큐 만났을 때 팁과 스택/큐와 관련된 에러들 그리고 해결책도 설명드려요!!

쉬운코드: 우선순위 큐와 힙의 개념과 차이, 사용 사례를 설명합니다! 힙이 어떻게 동작하는지도 예를 통해 자세히 설명합니다!

쉬운코드: ADT 뜻 ; 데이터구조와 차이 ; 실무에도 중요할까?

혀니c코딩: 자료구조란? | 배열(array) | 리스트(list) | 스택( stack) | 큐(queue) | 데큐(deque) | 트리(tree) | 그래프(graph)

반응형

'Computer Science' 카테고리의 다른 글

Web Event란? (웹이벤트란? ) / e.target이란?  (0) 2023.08.31
브라우저 렌더링 과정  (0) 2023.04.10
localStorage 로컬스토리지  (0) 2023.03.18
Ajax란  (0) 2023.02.23
JSON이란?  (0) 2023.02.23

'Computer Science'의 다른글

  • 현재글스택, 큐 / ADT, DS 자료구조 / JS의 스택과 큐

관련글

댓글

티스토리툴바