[자료구조] Stack, Queue

 

목차

 

 

 

 

📌  자료구조

 

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것

데이터란? 문자, 숫자, 그림, 영상 등 실생활을 구설하고 있는 모든 값

데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

 

 

📍Stack

 

쌓다, 쌓이다, 포개지다

데이터를 순서대로 쌓는 자료구조(프링글스 구조)

예를 들어 스마트폰 "뒤로가기" 버튼 처럼 현재 수행되는 앱이 종료되고 바로 직전에

수행되는 앱이 다시 나타나는 구조 또한 스택 구조이다.

 

 

 

 

🔗 Stack의 특징

 

1. LIFO(Last In First Out)

 

후입선출의 구조(가장 최근에 들어온 데이터가 가장 먼저 나간다.)

최상단의 데이터를 저장하고 꺼내는 특징

최상단에서 행위가 이루어지며 데이터를 저장하고 검색하는 프로세스가 매우 빠르다.

 

 

예1) 1, 2, 3, 4를 스택에 차례대로 넣습니다.

stack.push(데이터)
|  4  | <- top
|  3  |
|  2  |
|  1  |
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 스택이 빌 때까지 데이터를 전부 빼냅니다.

stack.pop()
|    |
|    |
|    |
|    |
4, 3, 2, 1
제일 마지막에 있는 데이터부터 차례대로 나오게 됩니다.

 

 

2. 하나의 입출력 방향을 가지고 있습니다.

 

자료를 넣고 뺄 수 있는 경로는 최상단뿐, 스택이 여러개 쌓여서도 데이터를 뺄때는 최상단에서만 뺄 수 있다.

 

3. 데이터는 하나씩 넣고 뺄 수 있습니다.

 

자료를 넣고 뺄 수 있는 경로는 최상단뿐, 한번에 한 개의 데이터만 뺄 수 있다.

 

 

 

🔗 Stack의 수도 코드

 

나의 생각

 

stack 구현

stack을 담을 storage가 필요

마지막에 들어올 데이터 : top

데이터가 들어올때마다 커지는 크기 메서드 : size

데이터 추가 메서드 : push

데이터 삭제 메서드 : pop

 

 

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
  }

  size() {
    return this.top + 1;
  }

	// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if ( this.size() <= 0 ) {
      return;
    }

    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    
    return result;
  }
}

 

 

📍Queue

 

줄을 서서 기다리다, 대기행렬

Queue는 Stack의 반대되는 개념으로 먼저 들어간 데이터가 먼저 나오는 FIFO구조를 가지고 잇다.

 

 

🔗 Queue의 특징

 

1. FIFO (First In First Out)

 

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조

프린터기 처럼 먼저 들어온 문서를 먼저 출력하는 구조에 쓰인다.

 

 

예1) 1, 2, 3, 4를 큐에 차례대로 넣습니다.

						queue.enqueue(데이터)
출력 방향(head) 	<---------------------------< 입력 방향(tail)
					1 <- 2 <- 3 <- 4
				<---------------------------<
들어간 순서대로, 1번이 제일 먼저 들어가고 4번이 마지막으로 들어가게 됩니다.

예2) 큐가 빌 때까지 데이터를 전부 빼냅니다.

						queue.dequeue(데이터)
출력 방향(head)	 <---------------------------< 입력 방향(tail)

				 <---------------------------<
1, 2, 3, 4
제일 첫 번째 있는 데이터부터 차례대로 나오게 됩니다.

 

2. 두 개의 입출력 방향을 가지고 있습니다.

 

데이터의 입력,출력 방향이 달라, 입력할 때는 큐의 맨 끝으로만 입력 가능하며

출력할 때는 맨 앞에서만 가능합니다. 즉 입출력 방향이 2개입니다

 

3. 데이터는 하나씩 넣고 뺄 수 있습니다.

 

데이터의 입력,출력 방향이 달라, 각 처리 시마다 한개의 데이터를 넣거나 뺄 수 있습니다.

 

 

 

🔗 Queue의 수도코드

 

나의 생각

 

queue 구현

queue을 담을 storage가 필요

입력 : 뒤 rear

출력 :  앞 front

데이터가 들어올때마다 커지는 크기 메서드 :  size

데이터 추가 메서드 : enqueue

데이터 삭제 메서드 : dequeue

 

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front;
  }
	
	// 큐에 데이터를 추가 할 수 있어야 합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() <= 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

 

 

🔗 Stack과 Queue의 공통점

 

선형 자료 구조, 순서가 있다.