스택(Stack), 큐(Queue)의 제약, 특징,구현

스택(Stack), 큐(Queue) 란?

• 제약을 같는 배열이다.
• 운영 체제 아키텍처, 출력 잡, 데이터 순회와 같이 임시 컨테이너로 사용된다.

 

1. 스택(Stack)

1-1. 스택이 가지는 제약

• 데이터는 스택의 끝에만 삽입할 수 있다.
• 데이터는 스택의 끝에서만 읽을 수 있다.
• 데이터는 스택의 끝에서만 삭제할 수 있다.

 

1-2. 스택의 특징

• 탑(top): 스택의 위.
• 바텀(bottom): 스택의 시작.
• 푸시(push): 스택의 탑에 데이터를 삽입하는 것.
• 팝(pop): 스택의 탑에서 데이터를 제거하는 것.
• LIFO(Last In, First Out): 스택에 마지막으로 푸시된 데이터가 첫번째 팝될 데이터라는 의미.

출처: programiz

 

1-3. 스택 구현 프로그램

• 순차 자료구조 방식을 이용하여 구현한 스택 (깃허브)

• 연결 자료구조 방식을 이용하여 구현한 스택 (깃허브)

 

2. 큐(Queue)

2-1. 큐가 가지는 제약

• 데이터는 큐의 끝에만 삽입할 수 있다. (스택과 동일 동작)
• 데이터는 큐의 앞에서만 읽을 수 있다. (스택과 정반대 동작)
• 데이터는 큐의 앞에서만 삭제할 수 있다. (스택과 정반대 동작)

 

2-2. 큐의 특징

• 프런트(front): 큐의 머리.
• 리어(rear): 큐의 꼬리.
• 인큐(enQueue): 리어에서 이루어지는 삽입 연산.
• 디큐(deQueue): 프런트에서 이루어지는 삭제 연산.
• FIFO(First In, First Out): 큐에 처음으로 인큐된 데이터가 첫번째 디큐될 데이터라는 의미.

출처: tutorialandexample

 

2-3. 큐 구현 프로그램

• 순차 자료구조 방식을 이용하여 구현한 큐 (깃허브)

• 연결 자료구조 방식을 이용하여 구현한 큐 (깃허브)

• 순차 자료구조 방식을 이용하여 구현한 원형 큐 (깃허브)
• 덱(Deque, Double-ended Queue) (깃허브)

 

 

 

학습 교재

자바로 배우는 쉬운 자료구조 - 이지영 지음

누구나 자료구조와 알고리즘 - 제이 웬그로우 지음