[자료구조] Stack & Queue

 스택(stack)과 큐(queue) 

스택과 큐.
처음 들었을 땐 어려울 수 있지만, 쉽게 설명해보고자 한다.

 

728x90

---

 1. 스택 (Stack) 

 스택(stack) 은 데이터를 아래에서 위로 쌓아올리는 구조를 말한다.
이때 데이터를 추가하거나 제거할 때 위에서부터 추가/삭제해야 하며, 이러한 자료구조를 LIFO(후입선출, Last-in, First-out)이라고 한다.

예로는 다음과 같은 것이 있을 수 있다.

 

• 브라우저창에서 뒤로가기
  새로운 주소에 접속하면 그 방문기록이 히스토리 스택 아래에서부터 쌓일거고, 뒤로 돌아간다는건 맨 위에 쌓인 방문기록에서 아래로 돌아가는 것
• Ctrl+Z로 실행 취소하여 직전 상태로 되돌아가기
• 역순 문자열 만들기
  가장 마지막에 입력된 문자부터 출력하기 때문
• 수식의 괄호 검사
  연산자 우선순위 표현을 위한 괄호 검사

따라서 스택은 여러 작업을 연달아 수행할 때 이전 작업 내용을 저장해 둘 필요가 있을 때 주로 사용된다.

 

---

1-1) 스택 작업 방식

 

스택과 같은 자료 구조에선 크게 3가지 작업 방식이 있다.

(1) 삽입(push) : 스택 최상단에 데이터를 저장
(2) 제거(pop) : 스택 최상단의 데이터를 제거
(3) 읽기(peek) : 맨 나중에 집어넣은 데이터를 확인하는 작업

 

이때 데이터의 삽입과 제거는 모두 탑(top)에서만 이루어진다.

삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다.

 

 

이러한 작업 방식을 가지고 JavaScript의 배열에서 아래처럼 사용할 수 있다.

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 스택의 최상단 데이터인 3이 제거된다

 

반응형

 

---

 2. 큐 (queue) 

 큐(queue) 는  데이터를 줄세우는 구조를 의미한다.
이때는 먼저 앞에 줄 선 데이터가 삭제되기에, 이러한 자료구조는 FIFO(선입선출, First-in, First-out)이라 한다.

 

예를 들어,

 

• 프린터 출력 과정
  인쇄해야할 데이터를 임시로 큐(queue)에 저장해두고, 저장한 데이터를 앞에서부터 차례로 출력하는 것
• 프로세스 관리

따라서, 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 자주 사용된다.

 

---

2-1) 큐 작업 방식

 

큐와 같은 자료 구조에선 2가지 작업 방식이 있다.

(1) 큐 삽입(Enqueue) : 큐의 맨 끝의 데이터 추가
(2) 큐 삭제(Dequeue) : 큐의 맨 앞의 데이터 삭제

 

이때 데이터가 삭제되는 곳을 프론트(front), 데이터가 삽입되는 곳을 리어(rear)라고 한다.

삽입과 삭제에 O(1), 탐색에 O(n)이 걸린다.

 

 

이러한 작업 방식을 가지고 JavaScript의 배열에서 아래처럼 사용할 수 있다.

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 큐의 맨 앞 데이터인 1이 제거된다

 

 

---

 

</> 끊임없이 성장하기 위해 공부한 내용을 글로 작성하고 있습니다. 틀린 부분이나 추가해야 할 부분이 있다면 언제든 댓글로 남겨주세요❗️

 

---

References

 

• https://www.programiz.com/dsa/stack
• https://helloworldjavascript.net/pages/282-data-structures.html
• 면접을 위한 CS전공지식노트