210913. Stack/Queue

sylph0105·2021년 9월 21일
0

With Codestates

목록 보기
103/114
post-thumbnail

공부시간 : 19:30 ~ 22:00

오늘의 공부
[자료구조/알고리즘] 자료구조 기초 : Stack/Queue

💡 Stack

💜 Stack 개념

  • Stack 은 쌓다, 쌓이다, 포개지다 와 같은 의미를 가짐
  • 접시를 쌓고 치우는 형태와 비슷한 자료구조
  • LIFO(Last-In-First-Out): 가장 마지막에 들어온 데이터가 가장 먼저 삭제됨
  • FILO(First-In-Last-Out): 가장 처음에 들어온 데이터가 가장 마지막에 삭제됨
  • 데이터간 순서 관계를 유지할 수 있음
    1. 맨 뒤 데이터 추가
    2. 맨 뒤 데이터 삭제
    3. 맨 뒤 데이터 접근

💜 Stack 구현

  • Stack 구현 코플릿을 풀면서 this.top / this.top-1 인 부분들이 명확하게 이해가 되지 않음
  • Reference 설명이 모호해서 헷갈렸는데, 수도코드화하면서 이해함
  • this.top 은 실제 객체 내에서 사용하는 인덱스가 아니라 1부터 붙인 순서이자, 최종적으로 storage 내의 요소 개수임
  • 그러므로 인덱스를 이용하는 경우에는 this.top-1 을 이용해야 함!
class Stack {
  
  //stack constructor 를 생성
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화
  }
  
  // 목표1. stack 의 사이즈를 구할 수 있어야 함
  // this.top 은 스택이 쌓일 때마다 하나씩 증가 => top 으로 size 를 구할 수 있음
  // this.top 은 스택에 새롭게 추가될 요소의 순서(객체 내에서의 인덱스와는 다름)를 나타내며, 
  // 0부터 1씩 증감하며 표현하기 때문에 전체 요소의 개수를 나타내기도 함
  size() {
    return this.top;
  }
  
  // 목표2. stack 에 데이터를 추가할 수 있어야 함
  // this.top 을 키로, element 를 값으로 하여 storage 에 할당 
  // this.top 은 다음 순서를 가리키게 하여 새로운 요소에 대비
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
  
  // 목표3. stack 의 가장 마지막 데이터를 가장 처음으로 삭제할 수 있어야 함
  // 만약 size 가 0 이라면 아무 일도 일어나면 안 됨
  // 만약 size 가 위의 경우에 해당하지 않는다면 => element를 제거 한 뒤 해당 element를 반환
  // this.top-1(객체 내에서의 인덱스)로 최상단을 설정한 후 변수에 저장하고, this.top-1인 요소를 스택에서 삭제
  // 하나를 제거했으니 top (순서이자 개수)도 감소
  pop() {
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top - 1];
    delete this.storage[this.top - 1];
    this.top -= 1;
    return result;
  }
}

💡 Queue

💜 Queue 개념

  • Queue 는 줄을 서서 기다리다, 대기 행렬 이라는 의미를 가짐
  • 자료구조 Stack 과는 반대되는 개념
  • 마트 계산대 줄 혹은 톨게이트 통과 형태와 비슷한 자료구조
  • FIFO(First-In-First-Out): 가장 처음에 들어온 데이터가 가장 처음에 삭제됨
  • LILO(Last-In-Last-Out): 가장 마지막에 들어온 데이터가 가장 마지막에 삭제됨
  • 데이터간 순서 관계를 유지할 수 있음
    1. 맨 뒤 데이터 추가
    2. 맨 앞 데이터 삭제
    3. 맨 앞 데이터 접근

💜 Queue 구현

  • Queue 구현 코플릿을 풀면서
    1. this.front 와 this.rear 의 초기값이 모두 0인 상태에서 진행할 때, 요소를 삭제하는 경우 값이 어떻게 바뀌는지 혹은 어떤 요소가 삭제가 되는 건지 헷갈림
    2. 특정 부분에서 this.front-1 / this.front / this.front+1 을 써야할지 명확하게 이해가 되지 않음
  • Reference 설명이 모호해서 헷갈렸는데, 수도코드화하면서 이해함
  • queue 구현의 경우 객체 내의 실제 인덱스와 삭제되어야 하는 요소의 this.front 값이 일치하므로, 요소 삭제 시 인덱스 부분에는 그냥 this.front 를 쓰면 됨!
class Queue {

  // 가장 앞에 있는 요소를 front,
  // 가장 뒤에 있는 요소를 rear 라고 했을 때
  // queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  // 목표1. queue 의 사이즈를 구할 수 있어야 함
  // queue 는 추가될 때, rear 의 값이 커지고 
  // queue 가 삭제될 때, front 가 변경되므로,
  // 각 값을 알아야 size를 구할 수 있음
  size() {
    return this.rear - this.front;
  }
  
  // 목표2. queue 에 데이터를 추가할 수 있어야 함
  // queue 에 element 를 추가
  // this.rear 를 키로, 요소를 값으로 하여 storage에 할당
  // this.rear 은 다음 인덱스를 가리키게 하여 새로운 요소에 대비
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  
  // 목표3. queue 의 가장 처음 데이터를 가장 처음으로 삭제할 수 있어야 함
  // 만약 size 가 0 이라면 아무 일도 일어나면 안 됨
  // 만약 size 가 위의 경우에 해당하지 않는다면 => element 를 제거 한 뒤 해당 element를 반환
  // this.front+1(객체 내에서의 인덱스)을 가장 앞에 있는 요소로 다시 설정한 후 변수에 저장하고, this.front 인 요소는 큐에서 삭제
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}
profile
Connecting the dots

0개의 댓글