[Swift CS Study] 스택(Stack) & 큐(Queue)

Oxong·2021년 6월 15일

iOS CS Study

목록 보기

3/18

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;
}