알고리즘 - 10 리스트, 스택, 큐

리스트

- 동일한 값이 두 번 이상 나타날수 있는, 셀수 있는 정렬된 값을 나타내는 자료구조

 

리스트 종류

1. 선형 리스트

2. 단일 연결 리스트

3. 이중 연결 리스트

4. 원형 연결리스트

 

선형 리스트

- 리스트 중에서 순서를 가지는 리스트

- 순차 방식으로 구현하는 선형 순차 리스트

- 순차 자료구조는 원소를 논리적은 순서대로 메모리에 연속하여 저장

- 원소의 삽입, 삭제가 비효율적임

 

단일 연결 리스트

- 저장할 떄 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장하는 자료구조

- 각 노드는 다음 노드를 가리키는 포인터를 가짐

- 각 노드로 다음 노드를 가리키는 포인터로 연결하여 만든 리스트

- 하지만 포인터 데이터를 잃어버리면 이후 데이터들을 손실하게 됨

typedef struct tagNode
{
   int Data; //데이터 필드
   struct tagNode* NextNode; //다음 노드를 가리키는 포인터
} Node;

 

이중 연결 리스트

- 다음 노드의 참조 뿐만 아니라 이전 노드의 참조도 같이 가리키게한 연결 리스트

 

원형 연결 리스트

- 이중 연결 리스트에서 마지막 원소가 널 대신 처음 원소를 가리키게 한 연결 리스트

 

 

 

 

 

스택

- 먼저 들어간 요소가 가장 나중에 나오는(LIFO, Last in First Out) 자료구조

-  스택에서의 삽입(push), 스택에서의 삭제(pop)

- 스택의 응용 : 역순 문자열 만들기, 시스템 스택

 

 

역순 문자열 만들기

1. 문자열 ABCD를 스택에 삽입

2. pop을 하면 DCBA가 출력

 

시스템 스택

- 함수 호출과 복귀에 따른 전체 프로그램 수행 순서

- 함수를 수행 후 돌아올수 있는 지점을 저장하는 곳이 시스템 스택

 

 

시스템 스택 예시

1. main()함수 실행 시작

2. F_1() 함수 호출

3. 호출된 함수 F_1() 실행

4. F_2() 함수 호출

5. 호출된 함수 F_2() 함수 실행

6. F_2() 함수 실행 종료, F_1() 함수로 복귀

7. F_1() 함수로 복귀하여 F_1() 함수의 나머지 부분 실행

8. main()함수 실행 완료(전체 프로그램 실행 완료) -> 스택 프레임도 삭제

 

 

 

 

큐

- 먼저집어넣은 데이터가 먼저 나오는 FIFO(First In, First Out)구조로 저장하는 자료구조

- 삽입 enQueue, 삭제 deQueue