[자료구조] Stack과 Queue

오늘은 선형 자료구조인 Stack과 Queue에 대해 알아보자

 

Stack 이란?

입력과 출력이 한 곳으로만 이루어지는 자료구조의 형태이다.

LIFO정책을 따르고 있다.(Last In First Out)

따라서 나중에 들어온 것이 먼저 나간다.

뷔페의 접시가 쌓여있는 것을 생각하면 쉽다!!

 

그렇다면 Stack은 언제 사용될까?

1. 함수의 콜스택에 사용된다.

2. 문자열을 역순 출력할때에도 하나하나씩 넣고 빼면 역순으로 출력된다.

3. 후위 표기법을 연산할때 ex) 234*+ = 14

5. 브라우저 방문기록

6. 실행 취소(undo)

 

Stack은 배열과 달리 index로 접근할 수 없다.

또한 삽입과 삭제는 O(1)의 시간 복잡도 이다.(값을 넣고 빼기만 하면 되므로)

하지만 탐색시에는 O(n)이 걸린다.

 

Queue란?

FIFO정책을 따른다.(First In First Out)

먼저 들어간 것이 먼저 나온다!

에버랜드 줄서기를 생각하면 쉽다!

버퍼와 BFS에 이용된다.

 

큐에는 front와 rear라는 포인터가 존재한다.

front는 맨앞을 가리키고 rear는 맨 뒤를 가리킨다.

 

크기가 고정되어 있을때 rear가 배열의 마지막을 가리키게 되면 큐가 가득찼다고 판단하는데

앞에서 데이터가 빠져나가 빈공간이 생길 경우는?

 

이래서 원형큐가 나왔다.

 

원형큐란?

논리적으로 배열의 처음과 끝이 연결되어있는 것 처럼 동작하는 큐

빈공간이 있는지 풀인지 판단하기 위해 항상 공간 하나를 비워놓는다.

 

삽입하려고 할때 front와 rear+1이 같은 위치를 가리키게 되면 Full이라고 판단한다.

삭제할때는 front와 rear가 같은 위치를 가리키고 있으면 아무것도 없는 빈 큐라고 판단해 실행하지 않는다.

 

하지만 원형큐에 크기제한이 있기 때문에 다른것이 나오게 된다.

 

연결리스트 큐이다.

 

연결리스트 큐란?

LinkedList를 이용하여 큐를 구현한 형태로 크기제한이 없고 삽입과 삭제의 시간복잡도가 O(1)이다.

노드를 무한으로 생성할 수 있어 원형 큐처럼 포화상태를 판단하지 않는다.

공백상태는 확인해야 하는데 front의 포인터 변수가 null이라면 큐가 비어있다고 판단한다.

 

 

끝!