Queue

CS/자료구조

[자료구조 및 프로그래밍] 5. Stack & Queue With Linked List

2023.10.17

지난 글에서 Linked List 의 개념과 그 구현에 대해 정리하였다. 이번에는 Array 로 구현했던 Stack 과 Queue를 Linked List 로 구현하는 과정을 살펴보고자 한다. Stack With Linked List 스택을 연결리스트로 구현해보자. 연결리스트에서 데이터를 중간에 삽입할 때는 이전 노드의 주소를 알아야 하기 때문에 아주 복잡했다. 데이터를 맨 처음에 삽입하는 것이 아주 간단하기 때문에, 스택의 데이터 삽입과 삭제가 빈번히 일어나는 top 을 연결리스트의 첫 head로 설정하자. 그림으로 나타내면 이렇게 나타난다. 스택에 데이터를 추가하면 추가된 데이터를 top 이 가리키고, 추가된 데이터가 기존 데이터를 가리키는 방식으로 구현하면 된다. 스택에서 데이터를 뺄 때는 top 의..

CS/자료구조

[자료구조 및 프로그래밍] 3. Queue (Circular Queue) - 2

2023.10.04

지난 포스팅에서는 배열을 이용한 큐를 구현해보았다. front, back 변수를 모두 0으로 초기화 하였을 때, push: back 변수가 가리키는 인덱스에 데이터 추가, back >= size 이면 오버플로우 pop: front 변수가 가리키는 인덱스의 데이터를 제거, front >= back 이면 언더플로우 와 같이 구현할 수 있었다. 그러나 이렇게 구현하면 push 를 최대 N번, pop은 push 횟수 이하로만 할 수 있다는 문제가 있었다. 이번에는 Size N 이라는 메모리 공간에 중간중간 여유가 생긴다면 그 여유공간까지 활용하여 push 를 더 많이 할 수 있도록 기존의 큐를 개선하여 보겠다. 그림과 같이 사이즈 5인 큐에 모든 값이 다 들어있는 상황을 생각해보자. 현재 front 는 2이고,..

[자료구조 및 프로그래밍] 5. Stack & Queue With Linked List

[자료구조 및 프로그래밍] 3. Queue (Circular Queue) - 2

티스토리툴바