자료구조
-
[자료구조] 큐와 덱STUDY/Algorithm 2021. 4. 7. 12:28
큐(Queue) 앞에서 배운 스택의 경우, 나중에 들어온 데이터가 먼저 나가는 LIFO였다면, 큐는 먼저 들어온 데이터가 먼저 나가는 FIFO(First In First Out, 선입선출)의 특성을 가진다. 예를 들어 큐는, 매표소에 표를 사기 위해 줄을 선 사람들이라고 생각하면 된다. 줄의 맨 앞에 서있는 사람(=먼저온 사람)이 먼저 표를 사게 된다. 이것이 FIFO(First In First Out, 선입선출)이다. 큐는 뒤에서 새로운 데이터가 추가되고, 앞에서 데이터가 하나씩 삭제되는 구조를 가진다. 스택과의 차이점은, 스택은 데이터의 추가와 삭제가 같은 쪽에서 일어나지만, 큐는 데이터의 추가와 삭제가 다른 쪽에서 일어난다. 추가는 후단(Rear)에서, 삭제는 전단(front)에서 일어난다. 큐는 ..
-
[자료구조] 스택STUDY/Algorithm 2021. 4. 5. 10:41
스택이란? 스택(Stack)은 컴퓨터에서 굉장히 많이 사용되는 자료구조이다. 식당에 쌓여있는 접시 더미, 책상에 쌓여있는 책 등이 스택의 전형적인 예이다. 책상에 쌓여있는 책들을 이용하여 스택을 설명해보자. 책상에 새로운 책을 쌓을 때는, 책 더미의 맨 윗부분에 놓는다. 책이 필요하게 되면, 맨 위에 있는 책을 꺼낸다. 중간이나 맨 밑의 책부터 뽑아 사용한다면, 책 더미는 무너져버릴 것이다. 그렇기 때문에, 가장 최근에 들어온 책이 제일 위에 있고, 먼저 나간다. 이러한 입출력 형태를 LIFO(Last In First Out, 후입 선출)라고 한다. 스택에서의 입출력은 맨 위에서만 일어나고, 스택의 중간에서는 데이터를 삭제할 수 없다. 스택의 입출력이 일어나는 부분을 스택 상단(Stack Top)이라고 ..