9/3[TIL] Stack & Queue

DataStructure(자료 구조)

  자료 구조는 여러 데이터들의 묶음을 어떻게 저장하고 사용할지 정의한 것으로 종류에는 오늘 배운 stack, queue 내일부터 배울 Linked List, Hash Table 등등 여러 가지가 존재한다.

[Stack]

(LIFO: last in, first out) 말 처럼 바닥에 책을 쌓는다고 가정하면, 다시 한권 씩 들어 올릴 때 가장 위의 책부터 들어 올리게 된다는 것이다. 그렇기 때문에 실행 속도가 빠르나 맨 위의 데이터들을 하나 씩 빼내지 않으면 맨 아래 데이터에 접근할 수 없다.

 

프로퍼티

- 저장공간 역할을 하는 곳(배열(?))

- top : stack에 가장 위에 쌓여있는 데이터를 나타낸다. 정확히는 그 데이터의 위치(index) 값이다.

- maxSize : maxSize는 해당 저장소의 최대 크기를 나타낸다.

- stackArray : stackArray는 해당 저장소 자체이다.

 

메소드

- push() : push()는 배열(Array) 메소드로 배열의 가장 뒤에 값을 추가시키는 메소드(요소를 스택의 최상단에 추가)

- pop() : pop() 또한 배열(Array) 메소드로 배열의 가장 뒤의 값을 삭제하는 메소드(스택의 최상단에서 요소를 제거하고 반환)

- empty() : empty()는 저장소가 비어있는지 확인 스택에 원소가 없으면 ‘true’ 있으면 ‘false’ 값 반환

- size() : 스택의 현재 요소 개수를 반환

- top() : 스택의 맨 위에 있는 데이터 값을 반환

- full() : 스택에 원소가 없으면 ‘false’ 있으면 ‘true’ 값 반환

- peek() : 맨 나중에 집어넣은 데이터를 확인

- clear() : 스택 안에 있는 모든 요소 삭제

- lefts() : 스택에 있는 모든 요소 문자열로 반환

 

 

[Queue]

(FIFO : First In, First Out) 말처럼 가장 먼저 들어왔던 데이터가 가장 먼저 빠져나간다고 생각하면 된다.

큐의 종류는 두 가지가 있는데 하나는 선형(linear) 큐이고(linear) 다른 하나는 환형(circular) 큐이다.

 

선형 큐는 기본적이며 구현하는 게 매우 간단하지만 단지 배열로 일직선으로 구현하기에 큰 약점이 존재하는데

 

우선 큐에 데이터가 꽉 찼다면 데이터를 더 추가할 수 없다.

(물론 큐 사이즈를 늘리고 원소를 다시 복사하면 되긴 하지만 여기서 소요되는 시간이 아까울 수밖에 없다.)

 

그리고 공간의 효율성을 고려해야 합니다. 배열로 단순히 구현하면 front가 뒤로 계속 밀려 앞의 공간이 남게 됩니다. 하나의 원소가 빠져나가면 그다음부터 모든 데이터들을 앞으로 당겨와야 하기에 속도 측면에서 상당히 느릴 수밖에 없다. 물론 작은 데이터들이라면 상관없지만, 빅데이터를 사용하는 요즘 같은 시대에서는 큰 단점 일 수밖에 없다.

 

그렇기에 선형 큐를 보완하게 되는 환형(원형 큐)(원형큐) 큐 즉, 직선 형태로 놓는 것보다 원형으로 생각해서 큐를 구현하는 방법이 존재한다. 이렇게 되면 메모리 공간은 잘 활용하게 되지만 배열로 구현되어 있기 때문에 큐의 크기가 제한되는 단점이 존재하게 된다.

앞서 말한 두 가지 방법의 단점을 상쇄할 만한 것이 링크드 리스트 구현한 큐이다. 아직 오늘 배우지는 않았지만 링크드 리스트로 구현한 큐는 큐의 크기가 제한이 없고 삽입, 삭제가 편리하다고 한다.

 

프로퍼티

front : 가장 앞에 위치한 데이터

rear : 가장 뒤에 위치한 데이터

 

메소드

  앞서 말한 stack의 메소드들과 비슷한 것들이 많지만 queue 만 사용하는 메소드들에는

 

- insert() 혹은 enqueue() : 배열의 맨 뒷부분에 데이터를 삽입하는 것

- remove() 혹은 dequeue() : 배열 맨 앞에 위치한 데이터를(front가 가리키는) 지우는 것

- peek() : 배열 맨 앞의 데이터를(front가 가리키는) 읽는 것

 

  stack과 queue의 메소드들은 javascript는 이미 배열에 대하여 이 기능들을 모두 내부 함수로써 가지고 있기에 이 방법들을 직접

구현하며 만들어야 한다.