TIL - Stack, Queue
자료구조란 실세계에 존재하는 다양한 자료들을 어떤 규칙에 의해 저장할 것이고, 어떻게 사용할 것인지 정의한 것이다.
자료구조는 크게 선형 구조, 비선형 구조, 파일 구조로 나누어져있다. 선형 구조에는 Stack, Queue, Deque 등이 있고 비선형 구조에는 Tree, Graph가 있다.
오늘은 이 중에서도 선형구조에 해당하는 Stack과 Queue에 대해 학습한다.
1. Stack
[정의]
자료를 일시적으로 쌓아 두었다가 팔요할 때에 꺼내어 사용할 수 있도록 만든 자료구조이다.
예를 들어, 설거지를 하고 건조대에 접시를 쌓아두었다고 생각해보자. 그러면 가장 나중에 닦은 접시는 가장 위에 올라와 있을 것이다. 그리고 점심에 접시를 사용할 때에는 맨 위에 있는 가장 마지막에 닦인 접시 먼저 사용하게 될 것이다.
이 상황에서 건조대를 Stack 자료구조, 접시를 자료(data)로 비유할 수 있다.
[특징]
가장 나중에 닦은 접시는 가장 먼저 사용되고, 가장 먼저 닦은 접시는 가장 나중에 사용된다. 이런 정책을 자료구조에선 LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 한다.
[어디에]
컴퓨터에서의 활용에는 브라우저를 예로 들 수 있다. 우리가 velog 메인 화면에 들어와서 게시물을 클릭했을 때 컴퓨터는 velog 메인 화면을 Prev Stack에 저장하고 게시물 페이지로 넘어간다.
이 때, 유저가 뒤로가기 버튼을 누른다면 현재 위치한 게시물 페이지는 Next Stack에 저장하고 Prev Stack에 저장되었던 velog 사이트를 보여준다.
이렇게 stack 자료구조를 이용해 브라우저의 기능을 구현할 수 있다.
2. Queue
[정의]
2개의 포인터를 가지고 한쪽 끝에서 삽입이 발생되고 다른 한쪽 끝에서 삭제가 일어나는 순차적 자료구조이다.
예를 들어 우리가 빵을 사기위해 빵집에 들렀는데 사람이 너무 많아서 줄을 섰다고 해보자. 그러면 가장 먼저 줄을 선 사람이 가장 먼저 사가고 가장 나중에 도착한 나는 앞사람이 모두 빵을 사고가야 내 차례가 된다. 이 상황에서 줄을 Queue 자료구조, 사람은 자료(data)로 비유할 수 있다.
[특징]
가장 먼저 도착한 사람은 가장 먼저 가고 가장 나중에 도착한 사람은 가장 나중에 간다. 이런 정책을 자료구조에선 FIFO(First In First Out) 혹은 LIFO(Last In First Out) 이라고 한다.
[어디에]
컴퓨터에서의 활용은 프린터를 예로 들 수 있다.
우리가 ppt5장을 프린터로 출력해야 한다고 가정해보자. 그러면 컴퓨터 안에서는 무슨 일이 일어날까?
컴퓨터에서 출력 버튼을 누르는 순간 ppt5장은 Queue에 차례대로 저장이 된다.
이후 1부터 5까지 차례대로 Printer에 전달되어 인쇄가 된다.
이렇게 Queue 자료구조를 이용해 프린트 기능을 구현할 수 있다.
오늘은 Stack과 Queue에 대하여 공부하였다. 내일은 Tree와 Graph에 대하여 공부한다. 오늘은 여기까지~
