[Data Structure] Stack, Queue

슬지로운 개발생활·2020년 12월 3일

data structure

Data Structure

목록 보기

3/3

Stack

데이터를 집어넣을 수 있는 선형(linear) 자료형
LIFO (Last In First Out)
Stack은 쌓여있는 접시 더미와 같이 작동
스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 사용

property

storage : 스택의 저장소(객체형태)
top : 스택의 가장 위에 쌓여 있는 데이터(index 역할)

Method

push(element) : 요소를 스택 최상단에 추가
pop() : 최상단에 위치한 요소를 제거 후 반환
size() : 스택의 요소 개수 반환

Additional Method

peek() : 최상단에 있는 요소를 제거하지 않고 반환
isEmpty() : 스택이 비어있는지 확인 후 boolean값으로 반환
isFull() : 스택이 다 찼는지 확인 후 boolean값으로 반환

Pseudocode

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }

  size() {
    // 방법1. this.storage의 길이 반환
    // 방법2. this.top에 1 더한 값 반환
  }

  push(element) {
    // this.top++
    // this.storage에 this.top : element 넣기
  }

  pop() {
    // storage에 prop이 없을때 this.top이 계속 마이너스 되지않게 조건문 설정
    	// this.top이 0이상일때 조건문 내용 실행
    // 삭제할 최상단에 있는 요소(this.storage[this.top])를 변수에 할당
    // 최상단에 있는 변수 삭제
    // this.top--
    // 삭제한 요소(this.storage[this.top])를 할당한 변수 반환.
  }
}

스택 활용 예시

expression evaluation
Parenthesis Matching
Memory management
Backtracking Problems
call and return process
참고 :
- Stack applications in data structure
- Stack Applications

Queue

데이터를 집어넣을 수 있는 선형(linear) 자료형
FIFO (First In First Out)
Queue는 놀이공원에서 서는 줄과 같이 작동

property

storage : 큐 저장소(객체형태)
first : 가장 앞에 있는 요소의 index 값
rear : 마지막에 있는 요소의 index 값

Method

enqueue(element) : 요소를 큐 뒤에 추가
dequeue() : 제일 앞에 있는 요소 제거 후 반환
size() : 큐의 요소 개수 반환

Additional Method

peek() : 앞에 있는 요소를 제거하지 않고 반환
isEmpty() : 큐가 비어있는지 확인후 boolean값으로 반환
isFull() : 큐가 다 찼는지 확인후 boolean값으로 반환

Pseudocode

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

  size() {
    // 방법1. this.storage의 길이 반환
    // 방법2. this.rear - this.front 값 리턴
  }

  enqueue(element) {
  	// this.storage에 this.rear = element(새로생긴 요소) 넣기
    // this.rear++
  }

  dequeue() {
  	//this.storage(큐)에 값이 없을 때 front값이 더해지지 않게 조건문 설정
    	// this.size()값이 0보다 클때 조건문 실행
    // 삭제할 앞에 있는 요소(this.storage[this.front])를 변수에 할당
    // 앞에 있는 요소 삭제
    // this.front++
    // 삭제할 앞에 있는 요소를 담은 변수 반환
    }
  }
}