[자료구조] Stack과 Queue

스택(Stack)이란?

스택은 데이터가 들어온 순서대로 차곡 차곡 책이 쌓이듯 쌓이는 형태의 기억공간이다.

출력시 가장 나중에 쌓인 데이터가 제일 먼저 출력을 하게 된다.

그러므로 스택을 선입후출 혹은 LIFO(Last In First Out)이라고도 부른다.

1. 처음에 DATA[0]이 스택에 들어간다.

2. 이어서 DATA[1]이 스택에 들어온다.

3. 2번과 같은 방식으로 계속해서 데이터가 들어온다.

이런식으로 데이터가 계속 쌓이고 필요할때 꺼내어서 사용하면된다.

만약 4개의 데이터가 들어오고 나는 0번째 데이터를 사용하고 싶다면 어떻게 해야할까?

당연히 3번과 2번 그리고 1번데이터를 빼낸후 0번째 데이터를 사용해야한다.

스택에서는 TOP, POP, PUSH라는 용어를 사용한다.

TOP이란 스택의 맨위의 데이터인 즉, 최근에 들어온 데이터를 가리키는 화살표라고 생각하면된다.

데이터가 입/출력이 되면 이 TOP이란 화살표는 움직이면서 스택안에서 데이터가 최대 몇개가 저장되어있는지 알수가 있다.

POP이란 스택에 있는 데이터를 이용해 연산을 할때에 데이터를 삭제하가 위한 것이다.

PUSH란 데이터를 삽입하기 위한 것이다. TOP이 다음 데이터가 들어올 자리로 이동하면 그 자리에 데이터를 삽입한다.

큐(Queue)란?

스택의 그림을 보면 입구와 출구가 같은 한 곳 이지만 큐는 입구와 출구가 다른 자료구조이다.

큐는 데이터가 계속해서 쌓이다가 가장 먼저 들어온 데이터가 나가게 된다.

따라서 선입선출 혹은 FIFO(First In First Out)이라고 한다.

참고로 큐를 배열로 만들었다고 가정합니다. 따라서 큐의 크기가 정해져있겠죠?

그림과 같이 큐에서 삭제가 일어나는 위치를 Front라고 하고 데이터가 있는 가장 끝 부분 즉, 삽입이 일어나는 곳을 Rear라고 한다.

그리고 큐에 데이터를 삽입하는 작업을 Enqueue, 빼는 작업을 Dequeue라고 한다.

우리가 삽입과 삭제작업을 할떄마다 Front와 Rear는 움직인다.

그런데 큐가 비어있을 경우에 삭제를 하는 작업을 한다면 Queue Underflow가 발생하게 된다.

당연히 데이터가 없는데 데이터를 삭제하겠다고하면 오류가 나는 경우이다.

마찬가지로 큐가 꽉 차있을경우 삽입을 하려한다면 오류가 난다. 이를 Queue Overflow라고 한다.