목록스택 (2)
Seung's Learning Record
≣ 목차 연결 리스트 연속된 공간에 데이터를 저장하는 방식인 리스트와는 다르게 연결 리스트(linked list)는 연속적이지 않는 공간에 데이터를 줄줄이 엮어서 저장한다. 연결 리스트는 일반적인 리스트보다 특정 원소의 삽입/ 삭제가 수월하다는 장점이 있지만, 특정 원소를 탐색하는 시간이 길고 요구되는 메모리 공간이 더 크다는 단점이 있다. 따라서 각각의 상황이 요구하는 자료구조를 제대로 파악해서 적절하게 사용하는 능력을 키우는것이 중요하다. 연결 리스트의 종류는 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. 단일 연결 리스트 - 각 원소가 자신의 다음 원소 주소를 들고 있는 구조 이중 연결 리스트 - 각 원소가 자신의 이전, 다음 원소 주소를 들고 있는 구조 c++에서 제공하는 ST..
STACK 이란? 한쪽 끝에서만 원소를 삽입/삭제할 수 있는 자료구조이다. FILO(First In Last Out)구조로 가장 먼저 삽입된 원소가 가장 나중에 빠져나온다. 원소가 삭제되는 위치를 최상단, top이라고 부른다. STACK 성질 원소의 추가 O(1) 원소의 제거 O(1) 최상단의 원소 확인 O(1) 최상단의 원소를 제외한 나머지 원소들은 확인 및 변경은 원칙적으로 불가능 STACK 구현 스택의 구현 방법에는 배열을 사용하여 구현하는 방법과 STL을 사용하는 방법이 있다. 배열을 사용한 구현 const int MX = 1000000; int dat[MX]; int pos = 0;//다음 원소가 삽입될 인덱스 정보 //원소 삽입 void push(int x){ dat[pos++] = x; } ..