20.07.23_Stack과 Queue

0. 들어가며

   요즘 가장 많이 활용하는 단어 중 하나는 데이터(Data)일 것이다. 데이터의 의미는 다양하게 쓰인다. 

   어떤 현상을 추측하는 상황에서 '데이터가 없어서 함부로 단언하기 어렵네'라고 말할수도 있고, 뉴스에서도 '통신사 데이터를 활용하여 시민들의 해당 지역을 통과한 인원에 대해 연락을 취하고 있다' 라고 말하는 등 이미 우리 생활에서 밀접한 단어가 되고 있다. 그런만큼 데이터의 양과 종류는 더욱 늘어나고 다양해지고 있으며, 그 중에 가장 나에게 필요한 정보를 취득하는 것이 기술이 되고 있다.  필요한 정보를 찾기 위해 여러 자료들을 정리한 형태, 그것이 바로 '자료 구조(Data Structure)'이다. 그 중 오늘은 Stack(스택)과 Queue(큐)를 알아보았다. 

 

1. Stack

  stack은 많은 접시가 쌓인 상황을 상상하면 쉽다. 아래와 같은 접시가 있다고 해보자.

 

1) 정의

접시를 쌓기 위해서는 가장 위(top)에 올려놓아야 하고, 

마찬가지로 접시를 빼기 위해서도 가장 위(top)에서 빼야한다.

 

이렇게 top에서만 작업이 가능한 자료구조 형태가 stack이라고 한다.

우리가 흔히 쓰는 기능으로는 ctrl+z 기능이다. 포토샵을 사용해본 사람이라면 알텐데 사용했던 기능들이 stack으로 차곡차곡 쌓여, 제일 최근의 작업부터 취소하는 형태이다. 

 

2) 특징

- LIFO(last in, first out) : 가장 마지막 것이 들어온 것이고, 제일 먼저 나감

- 제한된 용량을 갖도록 구현할 수 있음

- 요소를 더이상 수용할 수 없는 오버 플로우 상태가 되면 더 이상 요소를 받지 않음.

 

 

3) 기능

wikipedia에서는 stack에서 사용할 수 있는 연산자(operations)를 아래와 같이 정리하고 있다.

 

이 중 stack에서 가장 중요한 키워드는 세가지인 것 같다.

1. top(peek) : top은 stack 내에서 가장 최상단의 요소를 의미

2. pop()

3. push()

 

operation	explain
push(new-item)	Adds an item onto the stack.     : stack에 새로운 item 추가(제일 위에 쌓임)
top()	item-typeReturns the last item pushed onto the stack.(현재 위치) = peek    : stack에서 현재 위치, 즉 제일 최상단
pop()	Removes the most-recently-pushed item from the stack.   : 제일 최근의 item을 삭제함(동시에 해당 요소를 반환(return))
is-empty()	BooleanTrue if no more items can be popped and there is no top item.   : stack이 비어 있는지 확인. 비어있다면 true 반환
is-full()	BooleanTrue if no more items can be pushed.   : stack에 더 이상 담을 수 없다면 true 반환
get-size()	IntegerReturns the number of elements on the stack. : stack에 쌓인 요소들의 갯수을 반환

 

 

3) 적용

1. 하노이의 탑

  개인적으로는 혹성탈출에서 시저 어머니가 풀었던 문제라서 기억에 남는데, 하노이의 탑이 stack의 대표적인 문제라고 할 수 있다. 하노이의 탑은 세개의 기둥이 있는데, 한 기둥에는 크기가 다른 원형 블럭이 있다. 블럭은 자신보다 더 큰 블록 위에만 쌓을 수 있다. 이 방식으로 원래 있던 기둥에서 다른 기둥으로 옯기는 게임이 하노이의 탑이다.

 

 

2. 역추적(Backtracking)

  미로에서 길을 찾는다고 생각해보자. 출발지에서 목적지까지는 일련의 포인트가 있고, 최종 목적지에 도달하기 위해서는 다양한 경로가 있다. 임의의 경로를 선택하여 갈 때 잘 못되었음을 안다면 stack에 따라 최근에 갔던 위치로 돌아갈 수 있다. 역추적 알고리즘을 통해 분기 및 바운드를 관리할 수 있다고 한다. 

 

3. 컴파일 시간 메모리 관리

 눈에 보이는 사례는 찾기는 어렵지만 stack은 컴퓨터 내부 운영에 많이 사용된다고 한다. 위에서 언급한 것처러럼 실행 취소 기능에서도 활용되고 callstack 등 구현에 사용되어 재귀함수를 표현하는데 큰 역할을 한다.

 

 

4) Stack 구현

  stack에서 자주 사용하는 메소드인 size, push, pop 메소드만 먼저 구현해보았다.

 

수도코드는 다음과 같다.

  size 메소드

: 말 그대로 stack에 쌓인 데이터 크기를 반환하는 메소드

1. 객체의 키 개수를 체크(Object.keys())해서 반환

 

  push 메소드

: stack에 새로운 데이터를 추가하는 메소드

1. top을 키로 지정해서 파라미터(element) storage에 추가하기
2. top은 1 증가

 

  pop 메소드

: stack에서 가장 최근에 추가된 데이터를 삭제하는 동시에 그 자체를 반환하는 메소드

전제 )

• 삭제한 후에는 해당 데이터를 반환이 불가능함.
• 그러나 삭제와 반환을 동시에 할 수는 없음. 이에 대한 대안 필요
• 데이터가 있는 상태에서 top은 가장 최근 데이터 다음을 가리키고 있음

1. top 1 줄이기
2. 해당 객체(storage) 복사하기
3. storage에서 제일 마지막 키( this.top)로 제일 최근 데이터 삭제(delete)
4. 복사한 객체에서 제일 마지막 요소 반환

 

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

  size() {
    return Object.keys(this.storage).length
  }

  push(element) {
      this.storage[this.top] = element;
      this.top++;
  }

  pop() { //help
    this.top--

  let newObj = {};
  Object.assign(newObj,this.storage)
  // let keys = Object.keys(this.storage);
  // keys.sort();

  delete this.storage[this.top];
  return newObj[this.top];
  }
}

---

 

2. Queue

  stack이 쌓여진 접시의 형태였다면, queue는 은행에서 번호표를 받고 줄을 서서 기다리는 사람들을 생각하면 쉽다.

사람들이 1번부터 5번까지 각각 번호표를 받았다고 하자.

1) 창구에서 가장 먼저 1번을 부를 것이다.

2) 그러면 1번이 줄에서 나와 창구로 이동하고

3) 남은 줄에서 가장 높은 우선순위는 이제 번호표 2번을 받은 사람이 될 것이다. 

 

즉 queue는 하나의 줄처럼 운영된다. 그렇기에 stack과는 달리 선입선출(FIFO : frist in, first out/ 첫번째로 들어온 요소가 첫번째로 나감)의 방식으로 운영된다. 

 

 

2) 기능

operate	explain
enqueue(new-item)	queue 대기열 끝에 항목 추가
front()	규의 앞에 있는 항목을 반환
dequeue()	대기열 앞면에서 항목을 제거하면서, 해당 요소 반환(pop과 비슷)
is-empty()	queue가 빈 항목인지 확인. boolean 값으로 반환
is-full()	queue에 더 이상 넣을 수 없는지 확인. boolean 값으로 반환
get-size()	queue의 요소의 개수 반환

 

queue의 경우 inqueue와 dequeue의 과정이 흥미로웠다. 배열에서 pop()과 psuh()와는 달리, queue는 하나의 대기열이기 때문에 front는 원래 제일 앞 요소에 고정되어 있지만 dequeue를 하면 제일 앞 요소를 제거함과 동시에 front도 바로 다음 요소로 이동하게 된다. 이를 쉽게 설명한 예시가 바로 위에서 queue를 설명할 때 제시한 은행의 대기줄이다. 참고로 제일 마지막 요소의 인덱스는 rear라고 한다.

 

 

3) 특징

• 포인터가 2개이다. 앞에 있는 포인터(보통 front 혹은 head)와 뒤에 있는 포인터(rear 혹은 tail)

• front 는 첫 요소에 고정이다. 그렇기 때문에 dequeue에 의해 첫 요소가 삭제되면 원래는 두번째 요소였던 것이 front 포인터를 받으며 첫 요소가 된다.

• rear 는 stack과 유사하게 요소의 추가, 삭제에 따라 유동적으로 움직인다.

 

4) 단점

  장점이라면, 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에서 용이하다는 점과 간단하게 구현할 수 있음다는 점이다. 예시를 보면 알겠지만 실생활에서도 비슷한 사례과 매우 많은 편이라 구조를 이해하는 것도 쉬운 편이었다. 단점은 크기가 제한적이다는 것이다. JS에는 해당되지 않을 수 있지만 일반적인 경우 메모리를 미리 할당하고 앞 뒤에 포인터를 배치하기 때문이다. 또한 일반적인 큐의 경우 빈 메모리가 남아있어도 꽉차있는 것으로 판단될 수 있다. enqueue나 dequeue를 통해 요소들이 삭제되고 빈공간이 생겼는데 포인터 지정 알고리즘을 잘못 배치하면 생길 수 있는 문제이다. 이를 개선하고자 나타난 개념이 원형 queue이다. 이에 대해서는 추가적으로 정리해보려고 한다. 

 

 

5) 활용

• 음악 스트리밍 프로그램에서 선택한 순서대로 스트리밍을 해줌
• 실행 선택 순서에 따라 프로그램이 실행됨.
• 배달 앱 대기 순서, 티켓팅, 수강신청 등등

 

6) 구현

 queue의 메소드로 size, enqueue, dequeue만 일단 만들어보았다. 수도 코드는 다음과 같다.

 

size 메소드

: queue의 데이터 크기를 반환하는 메소드

1. 객체의 키 개수를 체크(Object.keys())하여 사이즈 반환

 

enqueue 메소드

: queue의 뒤에 새로운 데이터를 추가하는 메소드

1. this.rear를 키로 하여 storage에 데이터 저정
2. rear 1 증가하기

 

dequeue 메소드

: queue의 앞에 있는 데이터를 삭제 및 반환하는 메소드

전제)

• 삭제와 더불어 해당 데이터를 반환해야함.
• 삭제한 후에 front 포인터는 두번째 데이터를 향하게 됨.

1. 해당 객체에서 가장 첫번째 요소 복사하기
2. 제일 앞에 있는 데이터를 this.front를 이용하여 삭제하기(delete)
3. front 1 증가하기
4. 복사한 요소 반환

아래는 queue를 js의 class를 통해 구현한 것이다. 

여기서는 배열을 활용했지만 object를 활용해서도 구현해보는 것도 재밌었다. 

 

 

class Queue {
  constructor() {
    this.storage = {}; //저장소 객체
    this.front = 0;    //
    this.rear = 0;     //
  }

  size() {
    return Object.keys(this.storage).length;
  }

  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear++;
  }

  dequeue() {
    //제일 앞에 있는 요소를 인식해서
    //그 요소를 delete 하고
    //제일 앞[인덱스 0]을 가리켰던 포인터가 인덱스 1로 이동
    //(앞에 있는 것을 지정하는 기능)
    let newfront = this.storage[this.front];

    delete this.storage[this.front];
    this.front++;
    return newfront;
  }
}

 

 

* 참고하면 좋은 영상

: https://www.youtube.com/watch?v=BdsyG5yP1cQ

 

 

 

 

 

 

위 내용의 정의, 코드, 기능등은 widipedia를 참고하여 나름대로 재구성한 내용입니다.