자료구조 스택(Stack)과 큐(Queue)

스택(Stack)

스택(Stack)을 번역하면 쌓다, 쌓아올리다 라는 의미를 가지고있다. 스택 자료구조는 물건을 쌓아 두는것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다.

스택의 특징

• LIFO (Last In First Out) 구조로, 맨 위에서 자료를 넣고 뺄 수 있는 구조이다.
• 스택에 데이터를 push하면 항상 최상단에 들어가고, pop 으로 최근에 push를 한 데이터가 나온다.
• 자료가 없을 경우 pop을 하게되면 stack underflow, 스택의 크기 이상의 자료를 push할 경우 stack overflow

스택의 구조

• push('item') : 새로운 데이터를 Storage안에 있는 통 안에 쌓아 올리는 작업을 한다.
• pop() : 받아놓은 데이터의 맨 위에 있는 물건을 내보낸다.
• TOP : TOP는 Storage 라는 통에 쌓인 물건들 중 맨 위에 있는 물건을 가르킨다.
• peek() : stroage에 담긴 통에 top가 알려주는 맨 위에있는 물건을 가져온다. (top대신해서 메소드로 쓰인다)

스택의 활용

• 웹 브라우저 방문기록 (뒤로가기) : 가장 마지막 페이지를 다시 보여준다.
• 역순 문자열 만들기 : 가장 나중에 입력된 문자부터 출력한다.
• 실행취소(undo) : 가장 나중에 실행된 것 부터 실행을 취소한다.

JavaScript Stack

const stack = [];

stack.push(1);
stack.push(2);
stack.push(3);

stack[stack.length - 1] // 

stack.pop() //3
stack.pop() //2
stack.pop() //1

 

Class로 표현하면 다음과 같다.

class Stack {
 constructor() {
   this.stack = [];
   }
  
  push(item){
   this.stack.push(item);
  }
  
  pop(){
   this.stack.pop()
  }
}

 

스택은 O(1)의 시간 복잡도를 가지고 있다.

큐(Queue)

큐는 대기열에서 들어온 순서대로 기다리고 나가는 것을 뜻한다.. 게임 대기열이나 놀이공원, 은행 등 대기열에서 기다리는것과 같이 선입선출(FIFO, First in first out) 방식의 자료구조이다.

큐(Queue)의 특징

• FIFO (First In First Out === Last in last out)구조로, 한쪽에서 삽입, 다른 쪽 끝에서 삭제 작업이 이루어진다.
• 우선 삽입연산만 수행하는 곳을 rear, 삭제 연산만 수행하는 곳을 front 라고 정해져있다.
• 삽입연산을 인큐(enQueue), 삭제 연산을 디큐(deQueue)라고 한다.

큐의 구조

• front : 순서를 기다리는 맨 앞줄, 나가기 위한 줄의 순서를 나타낸다.
• rear : 순서를 기다리기 위해 들어가는 맨 뒷줄, 들어가기 위한 줄의 순서를 나타낸다.
• storage : 줄을 서기 위한 대기열을 의미한다.
• enqueue('item') : 기다리려는 존재가 줄의 맨 뒤쪽부터 붙는 행위를 의미한다.
• dequeue() : 기다리던 존재가 자기 차례가 되자 나가는 행위를 의미한다.
• size() : 줄의 길이를 의미한다.

큐의 활용

• 우선 순위가 같은 작업 예약
• 대기열
• 세차 혹은 에스컬레이터
• 프로세스 관리
• 너비 우선탐색(BFS, Breadth-First Search) 구현
• 캐시(Cache)구현

JavaScript Queue

enqueue: 선입
dequeue: 선출

const queue = []

queue.push(1) 
queue.push(2)


queue.shift()
qeueue.shift()

 

 

class로 표현하면 다음과 같다.

 

class Queue {
 constructor() {
   this.queue = []
 }
 enQueue(element){
   this.queue.unshift(element);
 }
 
 deQueue(){
  this.queue.shift();
 }
}