[자료구조] 자료구조 기초 Stack, Queue

자료구조?

자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것입니다.

자료구조는 자료의 집합을 구조화하고, 이를 표현하는 데에 초점이 맞춰져 있습니다.

이미 자료구조를 알게 모르게 많이 접했습니다. 사람이 사용하기에 편리하려고, 사용하기 좋으려고 만들어진 것이 자료구조입니다.

 

자주 등장하는 네 가지의 자료구조

• Stack, Queue, Tree, Graph

대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있습니다. 따라서 많은 자료구조를 알아두면, 어떠한 상황이 닥쳤을 때 적합한 자료구조를 빠르고 정확하게 적용하여 문제를 해결할 수 있습니다. 이것은 문제 해결력을 필요로하는 알고리즘 테스트(코딩 테스트)와 굉장히 밀접한 연관성이 있습니다. 특정 문제를 해결하는 데에 적합한 자료 구조를 찾아 데이터를 정리하고 활용할 줄 알면, 상황에 가장 적합하고 정확한 코드를 작성할 수 있습니다.

 

 

1. Stack

Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있습니다.

 

 stack의 구조에 사용되는 Property와 method

 

Method

• push() : push()는 배열(Array) 메소드로 배열의 가장 뒤에 값을 추가시키는 메소드입니다.
• pop() : pop() 또한 배열(Array) 메소드로 push()와는 반대로 배열의 가장 뒤의 값을 삭제하는 메소드입니다. pop()으로 꺼낸 값은 출력하거나 다른 곳에 할당할 수 있습니다.
• empty() : empty()는 저장소가 비어있는지 확인합니다. 저장소의 비움 여부에 따라 boolean(true/false)으로 값을 반환합니다.
• size() : size()는 현재 저장소에 저장되어있는 데이터가 몇 개 인지 체크합니다

Property

• top : top은 말 그대로 stack에 가장 위에 쌓여있는 데이터를 나타냅니다. 정확히는 그 데이터의 위치(index) 값입니다.
• maxSize : maxSize는 해당 저장소의 최대 크기를 나타냅니다.
• stackArray : stackArray는 해당 저장소 자체입니다.

 

2. Queue

큐(Queue)는 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있습니다. 어떤 구조를 가지고 있을지 짐작할 수 있나요?

자료구조 Queue는 Stack과 반대되는 개념으로, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있습니다. 티켓을 사려고 줄을 서서 기다리는 모습과 흡사한 이 자료구조의 특징을 일상 생활에서의 예를 통해 살펴보겠습니다.

 

가장 먼저 진입한 자동차가 가장 먼저 톨게이트를 통과합니다. 다시 말해, 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다는 말입니다.

 

인쇄 작업 Queue는 Queue에 들어온 문서를 순서대로 출력합니다.

 

 

 

 

 

컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)라고 합니다. 아래 이미지는 버퍼링(buffering)의 개념을 보여주고 있습니다.

대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생합니다. 이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖습니다. 불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용합니다.

(왼쪽) CPU에서는 이벤트를 규칙적으로 처리합니다. (오른쪽) 대부분의 컴퓨터 장치에서는 이벤트가 불규칙하게 발생합니다. 컴퓨터와 프린터 사이의 데이터(data) 통신을 정리하면 다음과 같습니다.

 

• 일반적으로 프린터는 속도가 느립니다.
• CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠릅니다.
• 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행합니다.
• 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄합니다.

유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드 된 데이터(data)가 영상을 재생하기에 충분하지 않은 경우가 있습니다. 이때 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생합니다.

 

 

 queue의 구조에 사용되는 Property와 method

method

• push() : queue도 stack과 동일하게 가장 마지막의 위치에 데이터가 쌓이기 때문에 push()를 사용합니다.
• shift() : shift() 메소드는 배열의 가장 앞에 있는 값을 삭제하는 메소드입니다. 데이터를 꺼내는 위치만 다를 뿐 pop()메소드와 동일하게 다른 곳에 꺼낸 값을 출력하거나 할당할 수 있습니다.
• empty : empty()는 저장소가 비어있는지 확인합니다.
• size : size()는 현재 저장소에 저장되어있는 데이터가 몇 개 인지 체크합니다

 

property

• front : 가장 먼저 들어온 데이터의 위치(index)를 나타냅니다.
• rear : 새로운 데이터가 들어갈 위치(index)를 나타냅니다.
  • front : 가장 먼저 들어온 데이터의 위치(index)를 나타냅니다.
  • rear : 새로운 데이터가 들어갈 위치(index)를 나타냅니다.
  • queueArray : queue저장소를 나타냅니다.property

 

 

property, method 설명

https://m.blog.naver.com/magnking/220966405605

 

참고 자료

https://velog.io/@hytenic/Data-Structure-Javascript를-이용한-stack-queue-이해하기