[자료구조/알고리즘] 자료구조 기초 : Stack/Queue

hosik kim·2021년 10월 6일
0

With CodeStates

목록 보기
6/45
post-thumbnail

💡Stack


📌Stack 개념

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

📌Stack 구현

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 구현

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
안되면 될 때까지👌

0개의 댓글