큐(Stack)/스택(Queue)[1]

자료를 구조화하는 가장 기본적인 방법은 자료를 순서대로 나열하여 리스트를 구성하는 것이다.
"자료를 나열하는 방법을 제한하는 몇 가지 규칙을 추가"하여 리스트를 응용한 자료구조를 만들 수 있다.

0. 구현

• 순차 자료구조 방식을
  • 1차원 배열 Stack [n]을 사용
• 연결 자료구조 방식
  • LinkedList 사용

1. 스택 (Stack)

스택(Stack)이란 쌓아 올린다는 의미다. 따라서 스택 자료구조라는 것은 접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 구조를 말한다.
후입 선출(LIFO) : Last In First Out의 구조를 가진다.

스택(Stack)에서는 6개의 연산 작업을 가지고 있다.

1. createStack() : 공백의 스택(Stack)을 생성하는 연산
2. isEmpty(S) : 스택(Stack) S가 공백인지 아닌지를 확인하는 연산
3. push(S, item) : 스택(Stack) S의 TOP에 item(원소)를 삽입하는 연산
4. pop(S) : 스택(Stack)의 TOP에 있는 item(원소)을 스택(Stack)에서 삭제하고 반환하는 연산
5. delete(S) : 스택(Stack)의 TOP에 있는 item(원소)을 삭제하는 연산
6. 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개의 연산 작업을 가지고 있다.

1. createQueue() : 공백의 큐(Queue)를 생성하는 연산
2. isEmpty(Q) : 큐(Queue)가 공백인지 아닌지를 확인하는 연산
3. enQueue(Q, item) : 큐(Queue) 리어(rear)에 item(원소)를 삽입하는 연산
4. deQueue(Q) : 큐(Queue)의 프런트(front)에 있는 item(원소)을 큐(Queue)에서 삭제하고 반환하는 연산
5. delete(Q) : 큐(Queue)의 프런트(front)에 있는 item(원소)을 삭제하는 연산
6. 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