큐(Stack)/스택(Queue)
- 자료를 구조화하는 가장 기본적인 방법은 자료를 순서대로 나열하여 리스트를 구성하는 것이다.
"자료를 나열하는 방법을 제한하는 몇 가지 규칙을 추가"하여 리스트를 응용한 자료구조를 만들 수 있다.
구현
스택 (Stack)
- 스택(Stack)이란 쌓아 올린다는 의미다. 따라서 스택 자료구조라는 것은 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조를 말한다.
- 후입 선출(LIFO) : Last In First Out의 구조를 가진다.
- 스택(Stack)에서는 6개의 연산 작업을 가지고 있다.
- createStack() : 공백의 스택(Stack)을 생성하는 연산
- isEmpty(S) : 스택(Stack) S가 공백인지 아닌지를 확인하는 연산
- push(S, item) : 스택(Stack) S의 TOP에 item(원소)를 삽입하는 연산
- pop(S) : 스택(Stack)의 TOP에 있는 item(원소)을 스택(Stack)에서 삭제하고 반환하는 연산
- delete(S) : 스택(Stack)의 TOP에 있는 item(원소)을 삭제하는 연산
- peek(S) : 스택(Stack)의 TOP에 있는 item(원소)을 반환하는 연산
구현 : https://github.com/Raconer/JavaCode/tree/master/src/main/java/com/java/dataStructure/stack
2. 큐 (Queue)
- 큐(Queue)는 리스트의 한쪽 끝에서 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어진다.
- 큐(Queue)의 한쪽 끝은 프런트(front)로 정하여 삭제 연산만 수행하도록 하고, 다른 쪽 끝은 리어(rear)로 정하여 삽입 연산만 수행하도록 제한한다. 큐에서 프런트(front) 원소는 가장 먼저 큐(Queue)에 들어온 첫 번째 원소이고, 리어(rear) 원소는 큐에 가장 늦게 들어온 마지막 원소다. 따라서 가장 먼저 들어온 프런트(front) 원소가 가장 먼저 삭제되므로 선입선출 구조가 된다.
- 선입선출(FIFO) : First In First Out
- 큐(Queue)에서는 6개의 연산 작업을 가지고 있다.
- createQueue() : 공백의 큐(Queue)를 생성하는 연산
- isEmpty(Q) : 큐(Queue)가 공백인지 아닌지를 확인하는 연산
- enQueue(Q, item) : 큐(Queue) 리어(rear)에 item(원소)를 삽입하는 연산
- deQueue(Q) : 큐(Queue)의 프런트(front)에 있는 item(원소)을 큐(Queue)에서 삭제하고 반환하는 연산
- delete(Q) : 큐(Queue)의 프런트(front)에 있는 item(원소)을 삭제하는 연산
- peek(Q) : 큐(Queue)의 프론트(front)에 있는 item(원소)을 반환하는 연산
스택과 큐에서의 삽입/삭제 연산 비교
-
| 삽입 연산 | | 삭제 연산 | |
---|
연산자 | 삽입 위치 | 연산자 | 삭제 위치 | |
스택 | push | top | pop | top |
큐 | enQueue | rear | deQueue | front |
구현 : https://github.com/Raconer/JavaCode/tree/master/src/main/java/com/java/dataStructure/queue