자료구조 | 스택(Stack), 큐(Queue) 추상 자료형, 이중 연결리스트(Doubly Linked List)

자료구조, 나한테 설명하며 공부해보자!

 

정성스러운 손 필기 ✍🏻 (클릭)

 

스택(Stack), 큐(Queue)?

아주 단순한 규칙을 갖고 있는 리스트라고 생각하면 쉽다.

각각이 어떤 규칙을 갖고 있는지 알아볼까? (위에 참조된 사진 내 그림을 참고하면 이해가 쉽다. 😊)

 

자료구조 - 스택(Stack)

- FILO (First In Last Out) : 먼저 들어간 데이터가 나중에 쓰이는 데이터 구조

일상생활 속 스택이 활용되는 구조를 먼저 생각해보자.

나: 엘리베이터 탑승 : 먼저 탑승한 사람이 가장 안쪽에 타게 되니까 나중에 나가게 돼.

 

- Stack 구현 (연결 리스트를 이용)

데이터 삽입/ 제거를 첫 번째 인덱스에 하면 된다. (한쪽 방향으로만 데이터를 삽입, 제거하면 된다.)

나: 가장 앞 (head) 노드에 데이터를 하나씩 넣고, 가장 앞(head) 노드에서 데이터를 제거

 

- 이 구조가 왜 필요해? (사용 예시)

차례가 중요할 때는 스택은 필요 없어 보인다. 다음 사용 예를 보면 스택의 필요성이 느껴진다.

 

사용 예시 1) 그림판에서 그림 그리다가 되돌리고 싶을 때 "ctrl+z"로 되돌리기

컴퓨터는 우리의 모든 작업을 stack에 기록하고 있다.

나 : 고양이를 그려볼까? 동그라미를 그리고(stack 저장) - 눈을 그리고(stack 저장)....

      아이코 잘못 그렸네. 뒤로 가기!

컴퓨터 : 가장 최근 작업이 기록된 stack을 버릴게.

 

오호.

윈도우에서 제공하는 메모장은 뒤로 가기가 한 번밖에 안 되어서 불편하다고 생각했는데,

이전 내용을 딱 한 개만 저장하는가 보다. (앱을 최대한 가볍게 이용할 수 있도록?)

원리가 궁금한데 좋은 검색 키워드가 생각나면 공유해주시면 감사드린다.

 

 

사용 예시 2) 코드 괄호 검사 

여는 괄호를 만날 때마다 스택에 넣고 // 과정 ①②

닫는 괄호를 만나면 // ③④ 스택에서 데이터를 꺼내

짝이 맞는 괄호인지 체크한다.

{  // ①여는 괄호 : stack에 넣기
  let num = (②2+10)③;
  // 현재 스택에는 ①②가 들어있다.
  // 닫는 괄호 ③을 만났으니 스택에서 데이터를 꺼내 비교한다.
  // (스택은 가장 나중에 넣은 데이터를 먼저 꺼내므로, ②를 꺼내 닫는 괄호 ③과 비교한다.)
  // 짝이 맞기 때문에 통과
} // ④ 닫는 괄호를 만났으므로 스택에서 데이터를 꺼내 비교한다. 짝이 맞기 때문에 통과

더 이상 체크할 코드가 없고, 스택이 비어있으니 → 문법 에러가 없다고 판단.

 

 

스택의 추상 자료형(JS)

추상 자료형(Abstract Data Type)?

구현하고자 하는 구조의 구체적 기능의 진행 과정을 언급하는 것이 아닌, 데이터의 연산 기능을 표기하는 것
(규칙의 나열이라고 보면 이해하기 쉽다)

예) 세탁기 : 탈수..

 

추상자료형	설명
push()	1. 스택에 데이터 삽입
pop()	2. 스택에서 데이터 꺼내기(데이터 제거)
peek()	3. 스택에서 데이터 꺼내진 않고 top에 있는 데이터 참조
isEmpty	4. 스택이 비어있는지 체크

 

 

자료구조 - 큐(Queue)

- FILO (First In First Out) : 먼저 들어간 데이터가 먼저 쓰이는 데이터 구조

일상생활 속 큐가 활용되는 구조를 먼저 생각해보자.

나: 맛집 대기 줄 : 번호표를 뽑은 순서대로 들어가게 돼. "질서를 위해 서는 줄"

 

- 운영체제에서의 큐 : FIFO 스케줄링

운영체제는 프로세스 작업 요청을 들어온 순서대로 큐에 넣고,

CPU가 순서대로 꺼내서 처리한다.

 

- Queue 구현 (양방향/이중 연결 리스트를 이용)

데이터 삽입은 가장 앞 head에서부터

데이터 제거는 가장 뒤에서부터!

 

하지만, 단방향 연결 리스트를 이용해 가장 뒤에서 데이터를 제거하려면

가장 앞 head 노드부터 순서대로 타고 가야 가장 뒤의 노드에 접근할 수 있기 때문에

O(n)의 성능을 가진다. (너무 느리다)

 

양방향/이중 연결리스트를 이용해 Queue를 구현하도록 하자.

 

 

양방향/이중 연결리스트 (Doubly Linked List)

이전 글의 단일 연결 리스트에 이어서 구현한다.

 

가장 뒤에 tail 변수를 추가하고, 이전 노드도 참조할 수 있도록 한다.

노드 수정 ( data, next , prev ) : 데이터를 담는 변수, 다음 누구를 연결하면 되는지 변수, 이전 노드를 가리키는 변수를 포함한 노드를 생성

(이해하기 쉽게 소괄호로 묶었다)

노드 연결 : next, prev를 이용해 이전 노드로도 연결하는 정보를 담는다.

 

큐의 추상 자료형(JS)

추상 자료형(Abstract Data Type)?

구현하고자 하는 구조의 구체적 기능의 진행 과정을 언급하는 것이 아닌, 데이터의 연산 기능을 표기하는 것
(규칙의 나열이라고 보면 이해하기 쉽다)

예) 세탁기 : 탈수..

 

추상자료형	설명
enqueue()	1. 큐에 데이터 삽입 (stack의 push())
dequeue()	2. 큐의 데이터 제거 (stack의 pop())
front()	3. 가장 먼저 들어간 데이터 참조 (=tail이 가르키는 데이터 참조) (stack의 peek())
isEmpty	4. 큐가 비어있는지 체크

 

 

다음 시간은 자료구조 - 덱(Deque)과 해시 테이블(Hashtable), 셋(Set)에 대해 알아보자

:D