[자료구조] 스택(Stack), 큐(Queue)

Stack의 정의​

Stack이란, Stack이란 단어의 의미처럼 쌓아 올린다는 뜻이다.

한쪽에서만 원소를 삽입하고 삭제가 가능한 자료구조이다.

 

한쪽에서만 원소를 쌓아 올리고 꺼내고 하기 때문에

LIFO(Last In First Out) 구조로 되어있다.

 

Stack의 기술 내용​

출처 : 위키백과

Stack에는 두가지 중요한 기술인 Push와 Pop이 있다.

 

위 그림과 같이 입구와 출구가 동일한 바구니가 있다.

 

Push를 하게 되면 바구니에 원소를 집어넣게 되며,

또 한번 Push를 하게 되면 첫 원소 위에 두번째 원소가 위치하게 된다.

 

여기서 첫번째 원소를 꺼내고 싶다면 Pop을 두번해야 한다.

 

결국 삽입을 할 때에도 맨 위(Top)에 삽입을 하게 되고 꺼낼때에도 맨 위에 있는 원소를 꺼내게 된다.

 

주로

• 문자열의 역순을 만들 때,
• 괄호 검사를 할 때,
• DFS
• 재귀함수
• 웹 브라우저에서의 뒤로가기 방식 등
  에 사용된다.

그래서, Stack의 시간복잡도는 Stack 안의 원소의 총 개수가 n일 때, O(n)이다.

 

Queue의 정의​

Queue란, 일렬로 서서 들어온 순서대로 나가는 방식이다.

한쪽에서 원소를 삽입하고, 반대쪽에서 삭제가 가능한 자료구조이다.

 

즉, 입구와 출구가 각각 존재하기 때문에 들어온 순서대로 나갈 수 있다.

그래서 FIFO(First In First Out)구조로 되어있다.

 

Queue의 기술 내용​

Queue에는 두가지 중요한 기능인 Enqueue와 Dequeue가 있다.

Enqueue를 하여 데이터를 삽입할 수 있고

Dequeue를 사용하여 데이터를 제거할 수 있다.

 

데이터를 삽입할 때에 삽입되는 원소의 위치는 Queue의 맨 뒷부분(Back)이고,

데이터를 제거할 때에 제거되는 원소의 위치는 Queue의 맨 앞부분(Front)이다.

 

Queue의 시간복잡도는 Queue 안의 원소의 총 개수가 n일 때, O(n)이다.

큐는 주로,

• 프로세스 관리
• 대기순서 관리
• 너비우선탐색(BFS) 등

에 쓰인다.