[Swift CS Study] 스택(Stack) & 큐(Queue)
21.06.14
공부한 것을 정리하는 용도의 글이므로 100% 정확하지 않을 수 있습니다.
참고용으로만 봐주시고, 내용이 부족하다고 느끼신다면 다른 글도 보시는 것이 좋습니다.
+ 틀린 부분, 수정해야 할 부분은 언제든지 피드백 주세요. 😊
by. ryalya
들어가기 전
Stack과 Queue는 List 자료구조에 속한다.
자료구조란?
Stack과 Queue는 하나를 검색하면 서로 묶여서 비교하는 형태로 많이 볼 수 있다.
🔶 Stack(스택)
- LIFO(Last in First out) = 후입선출
- 마지막에 들어온 요소가 처음으로 나옴.
- 가장 대표적인 예시> 웹페이지 '뒤로가기'.
우리가 새로운 페이지로 넘어갈 때마다 넘어가기 전 페이지를 스텍에 쌓고, 만약 뒤로가기를 누른다면 가장 위에 있는 페이지부터 꺼내오는 방식인 것.
- Object[] 배열을 사용하여 데이터들을 관리.
🔹 데이터 추가
Stack은 index를 가장 마지막(위)를 Top, 가장 처음(아래)를 Bottom이라고 함.
데이터를 추가하는 작업을 push. (리스트에서의 add)
또한 데이터를 삭제하는 작업을 pop 이라고 한다. (리스트에서의 remove)
push()구현 메소드는 아래와 같다.
@Override
public E push(E item) {
if (size == array.length) {
resize();
}
array[size] = item; // 마지막 위치에 요소 추가
size++; // 사이즈 1 증가
return item;
}
여기서 resize()는 용적을 재할당해주는 것을 말한다.
용적이 가득찼다면 array의 용적을 늘려주어야 한다.
🔹 데이터 삭제
pop()구현 메소드는 아래와 같다.
@Override
public E pop() {
// 만약 삭제할 요소가 없다면 Stack이 비어있다는 의미이므로 예외 발생시키기
if(size == 0) {
throw new EmptyStackException();
}
@SuppressWarnings("unchecked")
E obj = (E) array[size - 1]; // 삭제될 요소를 반환하기 위한 임시 변수
array[size - 1] = null; // 요소 삭제
size--; // 사이즈 1 감소
resize(); // 용적 재할당
return obj;
}
🔶 큐(Queue)
- FIFO(First-in First-out) = 선입선출
- 넣은 순서 그대로 나옴.
- Linked List의 구현체.
- 대표적인 예시로는 은행 창구 대기줄
- 입구와 출구가 따로 있다고 생각하면 쉽다.
Queue의 데이터를 추가하는 작업은 offer, 데이터를 삭제하는 작업을 poll 이라고 한다. (C의 경우)
🔹 데이터 추가
offer() 구현 메소드는 아래와 같다.
@Override
public boolean offer(E value) {
Node<E> newNode = new Node<E>(value);
// 비어있을 경우
if(size == 0) {
head = newNode;
}
// 그 외의 경우 마지막 노드(tail)의 다음 노드(next)가 새 노드를 가리키도록 한다.
else {
tail.next = newNode;
}
/**
* tail이 가리키는 노드를 새 노드로 바꿔준다.
*/
tail = newNode;
size++;
return true;
}
🔹 데이터 삭제
poll() 구현 메소드는 아래와 같다.
@Override
public E poll() {
// 삭제할 요소가 없을 경우 null 반환
if(size == 0) {
return null;
}
// 삭제될 요소의 데이터를 반환하기 위한 임시 변수
E element = head.data;
// head 노드의 다음노드
Node<E> nextNode = head.next;
// head의 모든 데이터들을 삭제
head.data = null;
head.next = null;
// head 가 가리키는 노드를 삭제된 head노드의 다음노드를 가리키도록 변경
head = nextNode;
size--;
return element;
}
Reference
정의 및 이미지 출처 + 더 공부해야 함
: https://st-lab.tistory.com/142
Author And Source
이 문제에 관하여([Swift CS Study] 스택(Stack) & 큐(Queue)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ryalya/Swift-CS-Study-스택Stack-큐Queue저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)