[기본원리] 메모리의 스택과 큐의 이용.

배열과 메모리의 관계에 이은 스택과 큐 에 대한 내용입니다.
2010/07/15 - [Programing/기본원리] - 프로그래머가 본 메모리의 내부.

읽기전에 손가락 한번 클릭~ >_<

고마워요 ~ Chu ~ ♥

스택과 큐

스택과 큐는 보통 데이터 처리시에 데이터를 임시로 저장하거나,
입/출력 장치의 데이터를 일시적으로 저장할 때 사용됩니다.

데이터를 잠시 보관해두는 일을 하기 위하여 메모리 주소와 인덱스를 일일이 지정하는 일은 ( 일반적인 배열 ) 너무 복잡하기 때문에 스택과 큐를 이용하여 어드레스와 인덱스를 지정하지 않고도 배열의 요소를 읽고 쓸수가 있게 됩니다.

우선 스택과 큐는 입력/출력 순서가 다른데요,

스택(Stack) 은 후입선출 ( LIFO : Last - In - First - Out ) 이라 하여 나중에 들어간 것이 먼저 나오는 방식입니다.

다음으로 큐( Queue ) 는 선입선출 ( FIFO : First - In - First - Out ) 이라 하여 먼저 들어간 것이 먼저 나오는 방식입니다.

결국, 이런 방식으로 메모리에 데이터를 쓰거나 읽게 되는데요,
여기에서 읽기/쓰기의 순서를 미리 지정해주면 어드레스와 인덱스를 지정할 필요가 없어지죠.

스택과 큐를 구현하려면 먼저, 데이터 저장 공간을 선언하고,
메소드 두개 ( 읽기 메소드, 쓰기 메소드 ) 를 작성해야 합니다.
Java 에선 미리 이런 메소드들이 만들어져 있는데요.
이 메소드의 내부에서는 배열을 읽고 쓰기 위한 처리를 하지만,
개발자 ( 메소드를 이용하는 쪽 ) 는 내부 처리를 몰라도 되기 때문에 정말 편리합니다 ~ ㅎ

스택

스택에 데이터를 쓰는 메소드를 push, 데이터를 읽는 메소드를 pop 이라고 하겠습니다.
( 실제로 java 에서 이용되는 여러가지 클래스들은 스택에 데이터를 읽고 쓰는 메소드들의 이름이 다를때가 있습니다 )
이 두 메소드는 데이터를 입/출력 하기 위한 한 쌍이 되는 것이지요.

이런식으로 되어 있다고 해보지요.

push 메소드에서는 매개변수로 값을 넣고, 이 값이 필요할 때에 pop 메소드를 이용하여 리턴값을 받게 됩니다. 이 메소드를 쓴다면 데이터를 일시적으로 저장해 두고 쓸 수가 있는 것이지요.

또한 스택은 LIFO 방식이기 때문에 저장된 마지막 데이터가 최초로 나오게 됩니다.
이 코드에선 111,222,333 순으로 입력했다면 출력은 333,222,111 이 되죠.

스택에 데이터를 쓰기 ( push ) 와 읽기 ( pop ) 하는 그림입니다.


스택의 원 의미는 ' 건초더미 ' 라고 합니다. 건초 같은 무언가를 차곡차곡 쌓아 올리게 되면
제일 나중에 쌓아진 것을 제일 먼저 꺼낼수가 있게 되지요. 또한 이 쌓여있는 물건은 결국 누군가에게 주거나 얼마후에 사용하기 위해 일시적으로 보관되어 있는 것이자나요?
이처럼 일시적으로 데이터를 저장하는 것을 메모리에서 구현한 것이 바로 스택입니다.
또한 스택은 인터럽트 처리, 정렬, 산술연산등에서도 사용됩니다.

큐

큐에 데이터를 쓰는 메소드는 put, 데이터를 읽는 메소드는 get 이라고 하겠습니다
( 스택과 마찬가지로 특정 클래스마다 조금씩 다를때가 있습니다 )
이 두 메소드도 또한 한 쌍이 됩니다.

큐는 FIFO 방식이기 때문에 최초로 저장된 데이터가 최초로 나옵니다.

이 프로그램에선 111,222,333 순으로 넣으면 111,222,333 순으로 나오겠지요.

보통 큐를 ' 대기행렬 ' 라고 부르는데요, 이것은 영화표를 사기 위해 줄을 서서 기다리는 것과 같습니다.
제일 먼저 온 사람이 제일 먼저 표를 사고 열을 빠져 나가겠지요.
그러면 그 다음 사람 순으로 차례로 처리되는 형태입니다.

이때 표를 사람사람과 뒤에 기다리는 사람, 그리고 표를 파는 사람의 완충 역할을 해주는 것이 큐.
즉, 프로그래밍 에서는 입출력 처리 타이밍을 조절하기 위한 버퍼가 되요!

일정하지 않은 시간별로 들어오는 데이터를 처리할 때도 사용되고요,
또한 큐를 원형버퍼( ring buffer ) 라고도 하는데, 예를들어 4개의 배열을 큐로 구현했다면,
배열의 선두로부터 시작하여 순서대로 데이터가 저장되고, 순서대로 출력 될 것입니다.

즉, 배열의 끝이 배열이 시작과 연결되어 있기 때문에,
빙글빙글 돌면서 데이터의 저장과 출력이 반복되는 구조라 할 수 있지요 !