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

스택 statck

• 스택을 번역하면 쌓다, 쌓아올리다 라는 의미
• 스택 자료구조는 물건처럼 차곡차곡 쌓아 올린 형태의 자료구조

스택의 특징

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

스택의 구조

• push() : 새로운 데이터를 storage 통 안에 쌓아 올린다
• pop() : 최근 push한 데이터를 내보낸다.
• TOP : storage 통에 쌓인 데이터 중 맨 위 데이터를 가르킨다.
• peek():storage 통에 top가 알려준 맨 위 데이터 물건을 가져온다.(top을 대신한 메서드)

스택의 활용

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

Javascript Stack

const stack = [];

console.log(stack.push(1)); 			//1
console.log(stack.push(2)); 			//2
console.log(stack.push(3)); 			//3

console.log(stack[stack.length - 1] );	// 3
console.log(stack); 					//[ 1, 2, 3 ]

console.log(stack.pop()); 				//3
console.log(stack.pop());				//2
console.log(stack.pop()); 				//1

Class

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

---

큐 Queue

• 큐는 대기열에서 들어온 순서대로 기다렸다가 나간다
• 마치 놀이공원이나 은행에서 순서대로 기다렸다 나가는것

큐의 특징

• FIFO ( First In First Out === Last in last out) 구조
• rear : 우선 삽입연산만 수행하는 곳
• front : 삭제 연산만 수행하는 곳
• 삽입연산을 인큐(enQueue)
• 삭제연산을 디큐(deQueue)
  

큐의 구조

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

큐의 활용

• 우선 순위가 같은 작업 예약
• 대기열
• 세차 혹은 에스컬레이터
• 프로세스 관리
• 우선탐색
• 캐시 구현

Javascript Queue

const queue = [];

console.log(queue.push(1)); 			//1
console.log(queue.push(2)); 			//2

console.log(queue); 					//[ 1, 2]

console.log(queue.shift()); 			//1
console.log(queue.shift());				//2

Class

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

---

잘료구조 스택과 큐 참고 블로그