Stack 과 Queue

Stack

쌓다, 쌓이다, 포개지다

자료구조의 한 종류로 스택은 데이터를 계속 해서 쌓아 놓은 것을 말한다. 자료의 입출력이 한 방향에서만 이루어진다.

LIFO(Last In First Out)
접시를 바닥에서부터 하나씩 쌓을 경우 맨 아래의 접시를 꺼내기 위해서는 위에 쌓인 접시들을 모두 꺼내어야한다. 이처럼 데이터(접시)가 스택에 쌓여있기 때문에 가장 먼저 삽입된 데이터를 사용하기 위해서는 뒤에 들어온 데이터들을 모두 꺼내야한다. 이를 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO, Last In First Out)라고 한다.

Stack에서 사용하는 용어

• top : stack에서 제일 위에 있는 위치, 즉 stack의 길이이자 데이터가 입출력되는 위치( top의 데이터가 0인 상태를 bottom이라고 한다. )
• .push : top의 위치에 데이터를 입력하고, top을 증가시킨다.
• .pop : top의 위치에 있는 데이터를 삭제하고 top을 감소시킨다.

Stack의 실사용 예제

컴퓨터에서 자료구조 Stack은 어떤 곳에 사용되고 있을까? 대표적으로 우리가 자주 사용하는 브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용된다.

1. 새로운 페이지로 접속할 때, 현재 페이지를 Prev Stack에 보관합한다.
2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때에는, 현재 페이지를 Next Stack에 보관하고 Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져온다.
3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동을 원할 때에는, Next Stack의 가장 마지막으로 보관된 페이지를 가져온다.
4. 마지막으로 현재 페이지를 Prev Stack에 보관한다.

Queue

차례를 기다리는 사람이나 승용차의 열

한 방향에서 입력이 이뤄지고, 그 반대편 방향에서 출력이 이루어지는 자료구조

FIFO(First In First Out)
스택과는 상반되는 자료구조이다. 은행에 가서 번호표를 뽑고 순서를 기다린다. 가장 먼저 도착해서 번호표를 뽑고 기다리고 있는 사람부터 시작해서 가장 먼저 나간다. 이처럼 먼저 들어온 데이터가 먼저 사용되는 것을 선입선출(FIFO, First In First Out)이라고 한다.

Queue 에서 사용하는 용어

• front : dequeue 하였을 시 출력이 되는 부분
• rear : 제일 뒤에 있는 데이터
• enqueue : data를 queue의 맨 뒤에 입력
• dequeue : head에 있는 data를 출력 및 삭제
• .push : rear의 위치에 데이터를 입력하고, rear을 증가시킨다.
• .shift : front 위치의 데이터를 삭제하고 그 데이터를 반환한다

Queue의 실사용 예제

컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하려면 어떻게 해야 할까?

1. 우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어간다.
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄합니다.
   컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 순서대로 인쇄

만약 Queue에 들어온 순서대로 출력하지 않는다면, 인쇄 결과물이 뒤죽박죽일 것이다.