해나의 컴공생존기

스택이란 선입후출의 자료구조이다. 원소의 추가,제거,제일상단의 원소확인이 O(1)에 가능하지만 다른 위치의 원소확인과 변경이 원칙적으로 불가능하다. 하지만 배열과 연결리스트로 스택을 구현한다면 가능하다. 1. 배열로 스택 구현하기 cosnt in MX=1000005; int dat[MX]; int pos=0 //위치 void push(int x){ dat[pos++]=x; } void pop(){ pos--; } void top(){ dat[pos-1]; } 2. STL #include using namespace std; int main(void) { stack S; S.push(10); // 10 S.push(20); // 10 20 S.push(30); // 10 20 30 cout

앞으로 자주 쓰일 자료구조들을 한번 복습해볼 것이다. 1. Array 동일한 type의 데이터를 연속된 주소에 저장하는 자료구조이다. 갯수를 미리 정해야하고 중간에 용량을 늘리기는 불가하다. 인덱스만 알면 데이터에 접근하기 슂다는 장점을 가지고있다. ex) A[7] = 400 + 7*4 = 428 Search, Delete, Insert 입장에서 효율이 좋지 않다. sorting이 되어있다면 Binary Search O(log N)가능하다. 2. Stack insertO(1) / DeleteO(1)만 제공한다. Search x Last in, First out 수식 계산에 사용 ex (3+7)*2 + (6-3)/5 3. Queue insert O(1) / Delete O(1)만 제공한다. Search x..

연결리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조 특징 k 번째 원소를 확인하기 위해 O(k)가 필요하다 임의의 위치에 원소를 추가,제거는 O(1) 종류 단일 연결리스트 이중 연결리스트 원형 연결리스트 배열 vs 연결리스트 // 연결리스트에 원소를 넣었다가 뺏다하는 함수 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; void insert(int addr, int num) { dat[unused] = num; pre[unused] = addr; nxt[unused] = nxt[addr]; if(nxt[addr]!=-1) // 맨 끝에 삽입하는게 아..