Data Structure Stack, Queue

아래 자료구조에 대해 스스로 검색해보며 공부해보시기 바랍니다.

내가 찾아서 이해한 구조의 추상적 그림을 찾아서 보면서 이해하는 방식으로 공부를 했다.

스택 (Stack)

스택(stack) 다음과 같은 성질을 갖는 자료형입니다.

• 데이터를 집어넣을 수 있는 선형(linear) 자료형입니다.
• 나중에 집어넣은 데이터가 먼저 나옵니다. 이 특징을 줄여서 LIFO(Last In First Out)라고 부릅니다.
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peek 등의 작업을 할 수 있습니다.

• •  

push(elemet) - 요소를 스택의 최상단에 추가합니다.

pop() - 스택의 최상단에서 요소를 제거하고 반환합니다.

size() - 스택의 현재 요소 개수를 반환합니다.

 

stack은 포인터는 한개이며 하노이의 탑을 알고있다면 이해하기 쉬울것이다.

서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을 때 널리 사용된다.

 

peek에 대해서는 test에서는 나오지 않았지만 따로 찾아보았다.

 

일단 peek에 대해서는 peek = stack.length -1의 사용으로 했었다.

 

배열을 이용해서 간단하게 스택을 구현할 수 있다. 사실상 arr을 사용하지 않고도 사용할 수있는 작업을 했지만 그것과는 다르게 여기서는 arr를 이용한 작업을 했다.

class Stack {
  constructor() {
    this._arr = [];
  }
  push(item) {
    this._arr.push(item);
  }
  pop() {
    return this._arr.pop();
  }
  peek() {
    return this._arr[this._arr.length - 1];
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); // 3

포토샵에서 사용하는 ctrl+z(history), 웹브라우저의 뒤로 가기 버튼 

 

 

큐 (Queue)

큐(queue)는 다음과 같은 성질을 갖는 자료형입니다.

• 데이터를 집어넣을 수 있는 선형(linear) 자료형입니다.
• 먼저 집어넣은 데이터가 먼저 나옵니다. 이 특징을 줄여서 FIFO(First In First Out)라고 부릅니다.
• 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있습니다.

• •  

enqueue(element) - 요소를 큐의 뒤에 추가합니다.

dequeue() - 요소를 큐의 앞에서 제거하고 반환합니다.

size() - 큐의 현재 요소 개수를 반환합니다.

 

큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.

배열을 이용해서 간단하게 큐를 구현할 수 있습니다.

class Queue {
  constructor() {
    this._arr = [];
  }
  enqueue(item) {
    this._arr.push(item);
  }
  dequeue() {
    return this._arr.shift();
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue(); // 1

•