[SEB BE] Section 2. 스택 & 큐

박두팔이·2023년 1월 16일

알고리즘

목록 보기

1/12

자료구조를 우리가 배워야 하는 이유는 무엇인가?
알고리즘 테스트는 궁극적으로 우리의 문제해결 능력을 테스트하는 것이다. 우리에게 주어진 문제에는 제한시간이 존재한다. 때문에 여러가지 형태의 자료구조를 이해한다면 테스트를 통과할 수 있을 것이다.

우리는 지금까지 자료구조의 형태와 유사하게 구현하여 문제를 사용해왔는데, 그것이 바로 배열이다.

배열은 자료구조의 형태를 구현할 수 있다고 했다.
그렇다면 배열은 어떤 자료구조의 형태를 구현한 것일까?

바로 Stack과 Queue이다.

⭐️ 후입선출, push(데이터넣기) & pop(데이터빼기) ⭐️

스택은 자료구조의 한 형태이다.

스택의 자료구조는 LIFO(Last In First Out)의 규칙을 따른다. 즉, 후입선출(나중에 들어온 것이 먼저 나간다)의 방식으로 데이터를 관리한다.
스택은 데이터를 하나씩 넣고 하나씩 뺄 수 있다.
Stack은 데이터를 push(데이터넣기)하고 pop(데이터 빼기)하기 위한 길이 하나뿐이어서 제한적 접근이라는 특징을 가지고있다. 즉 입출력 방향이 하나뿐이라는 것이다. (문이 하나)

앞이 가로막힌 1차선 도로에 차들이 줄지어 있다고 가정할 때, 맨 앞에있는 차가 밖으로 빠져나가기 위해서는 어떻게 해야할까? 당연히 맨 뒤에 있는 차량이 빠져나간 다음 차례차례 후입선출이 된 후에야 맨 앞 차량은 비로소 그 곳을 빠져나갈 수 있을 것이다.

현재 페이지에서 새로운 페이지로 접속하면 현재페이지는 이전 페이지가 되기 때문에 Prev Stack에 보관된다.
이제 1번의 새로운 페이지가 현재페이지가 되었다.
뒤로가기 버튼을 누르면 Prev Stack에서 가장 마지막에 저장된 이전페이지가 후입선출의 규칙에 따라 현재 페이지가 된다.
2번의 현재페이지었던 새로운 페이지는 Next Stack에 보관된다.
앞으로가기 버튼을 누르면 현재 페이지는 Prev Stack에 보관되고 Next스택에서 후입선출의 규칙에 따라 가장 나중에 저장된 페이지가 현재페이지로 열린다.

⭐️ 선입선출, enqueue(데이터넣기) & dequeue(데이터빼기) ⭐️

위의 사진은 큐 자료구조의 대표적인 예이다.
가장 먼저 진입한 자동차가 톨게이트를 가장 먼저 통과 한다.

이처럼 큐의 자료구조에는 FIFO(First In First Out) 의 특징을 가지고 있다. 즉, 선입선출(먼저 들어온 것이 먼저 나간다)의 특징을 가지고 있다.
입력(enqueue, 데이터 넣기)과 출력(dequeue, 데이터 빼기) 방향이 다른 두 개의 입출력 방향을 가지고 있다.
데이터가 입력된 순서대로 처리할 때 사용한다.
데이터는 하나씩 넣고 하나씩 뺄 수 있다.(여러개 안됨)

문서 순서대로 인쇄하기가 대표적이다.
데이터를 주고받을 때 기기들의 속도나 시간차이를 극복하기 위해서는 임시기억장치를 사용하게 되는데 이때 쓰이는 자료구조가 Queue인 것이다.

이 과정을 버퍼(buffer)라고 한다.
불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼를 사용하게 된다. 우리의 데이터를 처리하는 CPU는 규칙적인 속도로 데이터를 처리하지만

대부분의 컴퓨터장치(프린트기 등)들은 불규칙한 속도를 보인다.

기억을 위한 기록 :>