IT, FIRE, License and Daily life

<역순 문자열>

스택의 후입선출(LIFO) 성질을 이용한다.

​
① 문자열을 순서대로 스택에 push 하기

② 스택을 pop하여 문자열로 저장하기

<수식의 괄호의 쌍 검사>

수식에 포함되어있는 괄호는 가장 마지막에 열린 괄호를 가장 먼저 닫아 주어야 하는 후입선출 구조로 구성되어있으므로, 후입선출 구조의 스택을 이용하여 괄호를 검사한다.
수식을 왼쪽에서 오른쪽으로 하나씩 읽으면서 괄호를 검사.

[방법]

① 왼쪽 괄호를 만나면 스택에 push
② 오른쪽 괄호를 만나면 스택을 pop, 마지막에 저장한 괄호와 같은 종류인지를 확인
- 같은 종류의 괄호가 아닌 경우 괄호의 짝이 잘못 사용된 수식임.

※ 수식에 대한 검사가 모두 끝났을 때 스택은 공백 스택이 됨
•수식이 끝났어도 스택이 공백이 되지 않으면 괄호의 개수가 틀린 수식임.

[수식의 괄호의 쌍 검사 코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<스택(Stack)>

접시를 쌓듯이 자료를 차곡차곡 쌓아 올린 형태의 자료구조

스택에 저장된 원소는 top(맨 위)으로 정한 곳에서만 접근 가능

- top 위치에서만 원소를 삽입하므로, 먼저 삽입한 원소는 밑에 쌓이고, 나중에 삽입한 원소는 위에 쌓이는 LIFO(Last In First Out)구조이다.

[스택 실생활 활용 예]

1. 연탄 쌓기

연탄을 하나씩 쌓으면서 아궁이에 넣는다. 마지막에 넣은 연탄이 가장 위에 있게 된다.

꺼낼때는 위에서부터 하나씩 꺼내야 한다. 마짐가에 넣은 연탄을 가장 먼저 꺼낸다.

[Push 알고리즘]

[배열 구조]

① 공백 스택 생성 : createStack(S);

② 원소 A 삽입 : push(S, A);

③ 원소 B 삽입 : push(S, B);

④ 원소 C 삽입 : push(S, C); 

⑤ 원소 삭제 : pop(S);

[연결리스트를 이용한 스택의 코드]

Copyrightⓒ2014 By 한빛아카데미(주)

<이중 연결 리스트 삭제 연산>

1. 삭제할 노드의 오른쪽 노드의 주소(old.rlink)를 삭제할 노드의 왼쪽 노드(old.llink)의 오른쪽 링크에 저장한다.

2. 삭제할 노드의 왼쪽 노드의 주소(old.llink)를 삭제할 노드의 오른쪽 노드(old.rlink)의 왼쪽 링크(llink)에 저장한다.

3. 삭제할 노드를 자유공간리스트에 반환

① old.llink.rlink ← old.rlink;

삭제할 노드의 오른쪽 노드의 주소를 노드 old의 왼쪽노드의 rlink에 저장한다.

② old.rlink.llink ← old.llink;

삭제할 노드의 왼쪽 노드의 주소를 노드 old의 오른쪽 노드의 llink에 저장한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<이중 연결 리스트 삽입 연산>

1. 삽입할 노드를 가져옴

2. 새 노드의 데이터 필드에 값 저장

3. 새 노드의 왼쪽 노드의 오른쪽 링크(rlink)를 새 노드의 오른쪽 링크(rlink)에 저장

4. 왼쪽 노드의 오른쪽 링크(rlink)에 새 노드의 주소를 저장

5. 새 노드의 오른쪽 노드의 왼쪽 링크(llink)를 새 노드의 왼쪽 링크(llink)에 저장

6. 오른쪽 노드의 왼쪽 링크(llink)에 새 노드의 주소를 저장

① new.rlink ← pre.rlink;

노드 pre(이전노드)의 rlink를 노드 new의 rlink에 저장한다.

② pre.rlink ← new;

새 노드 new의 주소를 노드 pre(이전노드)의 rlink에 저장한다.

③ new.llink ← pre;

포인터 pre의 값을 삽입할 노드 new의 llink에 저장한다.

④ new.rlink.llink ← new;

포인터 new의 값을 노드 new의 오른쪽노드의 llink에 저장한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<이중 연결 리스트>

양쪽 방향으로 순회할 수 있도록 노드를 연결할 리스트이다.

[이중 연결 리스트의 노드 구조]

llink(left link) 필드 : 왼쪽 노드와 연결하는 포인터

rlink(right link) 필드 : 오른쪽 노드와 연결하는 포인터

[노드 구조에 대한 구조체]

typedef struct Dnode {

   struct Dnode *llink;

   char data[5];

   struct Dnode *rlink;

}

[이중 연결 리스트의 표현]

[이중 연결 리스트의 원형 리스트]

Copyrightⓒ2014 By 한빛아카데미(주)

<원형 연결 리스트 삭제 연산>

원형 연결 리스트 CL에서 포인터 pre가 가리키는 노드의 다음 노드를 삭제하고 삭제한 노드는 자유 공간 리스트에 반환하는 연산이다.

1. if (CL = null) then error;

공백 리스트일 경우 삭제할 노드가 없기 때문에 에러

2. else {                         

      old ← pre.link;            // ①

      pre.link ← old.link;      // ②

      if(old = CL) then          // ③ - 1

         CL ← old.link;         // ③ - 2

      returnNode(old);         // ④

   }

① old ← pre.link;

이전 노드(pre)의 다음 노드를 삭제할 노드로 지정

② pre.link ← old.link;

이전 노드(pre)의 다음 노드를 old.link인 삭제할 노드의 다음 노드로 지정

한마디로 old를 건너뛴다는 의미

③ - 1 if(old = CL) then

삭제할 노드가 원형 리스트의 첫 번째 노드일 경우

③ - 2 CL ← old.link;

CL(리스트 포인터)가 old.link인 첫번째 노드를 가리키게 한다.

두번째 노드가 리스트의 첫 번째 노드를 가리키게 한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<원형 연결 리스트>

단순 연결 리스트에서 마지막 노드가 리스트의 첫 번째 노드를 가리키게 하여 리스트의 구조를 원형으로 만든 연결 리스트를 원형 연결 리스트라고 한다.

링크를 따라 계속 순회하면 이전 노드에 접근이 가능하다.

<원형 연결 리스트 삽입>

[첫 번째 노드로 삽입하기]

1. if (CL = null) then {

      CL ← new;          // ①

      new.link ← new;  // ②

   }

원형리스트가 공백 리스트인 경우에는 삽입하는 노드 new는 리스트의 첫 번째 노드이자 마지막 노드가 된다.

① CL ← new;

원형 리스트의 시작을 가리키는 CL포인터가 new를 가리키게 한다.

② new.link ← new;

노드 new가 자기자신을 가리키게 한다. 첫번째 노드이자 마지막 노드이기 때문

2. else {

      temp ← CL;                       // ①

      while (temp.link ≠ CL) do   // ②

         temp ← temp.link;

      new.link ← temp.link;         // ③

      temp.link ← new;               // ④

      CL ← new;                      // ⑤

   }

원형 리스트가 공백이 아닌 경우에는 첫 번째 노드의 주소를 임시 순회 포인터(temp)에 저장하여 노드 순회의 시작점을 정한다.

① temp ← CL;

② while (temp.link ≠ CL) do

         temp ← temp.link;

temp를 링크를 따라 마지막 노드까지 이동한다.

③ new.link ← temp.link;

리스트의 마지막 노드의 링크 값을 노드 new의 링크에 저장하여, 노드 new가 노드 temp의 다음 노드(이 노드가 처음 노드임)를 가리키게 한다. (왜? 마지막 노드의 다음 노드는 리스트의 첫 번째 노드가 되기 때문에)

④ temp.link ← new;

포인터 new의 값을 포인터 temp의 마지막 노드 링크에 저장하여, 리스트의 마지막 노드가 노드 new를 가리키게 한다. 즉, 첫번째로 노드를 삽입해 주었으면 마지막 노드가 그 첫번째 노드를 가리키게 해주는 작업을 하는 것이다.

⑤ CL ← new;

노드 new의 값을 CL에 저장하여 노드 new가 리스트이 첫 번째 노드가 되도록 지정한다.

​[중간 노드로 삽입하기]

1. if (CL = null) then {

      CL ← new;

      new.link ← new;

   }

"[첫 번째 노드로 삽입하기]"의 공백 리스트일 경우와 같다.

​

2. ​else {

      new.link ← pre.link;   // ①

      pre.link ← new;     // ②

   }

​공백 리스트가 아닐 경우

① new.link ← pre.link;

​new노드의 링크에 노드(pre)의 다음노드를 연결한다.

② pre.link ← new;

​노드 new를 노드 pre의 링크(pre.link)에 저장하여 pre가 노드 new를 가리키게 한다

Copyrightⓒ2014 By 한빛아카데미(주)

<단순 연결리스트의 탐색>

1. temp ← L;

리스트의 시작주소를 temp라는 임시 포인터변수에 저장한다.

2. while (temp ≠ null) do { 

    // 시작주소가 null일 때 까지(마지막 노드일 때 까지) 반복

        if (temp.data = x) then return temp;

        // 처음 노드부터 비교하면서 temp.data가 x인지를 검사. 참이라면 temp 노드를 반환

        temp ← temp.link;

        // temp에 temp.link를 저장한다 (노드 이동)

  }

Copyrightⓒ2014 By 한빛아카데미(주)

<단순 연결 리스트의 삭제>

1. 공백 리스트인 경우

삭제할 노드가 없어 error로 표시하였다.

2. 공백 리스트가 아닌경우

① old ←pre.link;

노드 pre의 다음노드의 주소(pre.link)를 포인터 old에 저장하여, 포인터 old가 다음 노드를 가리키게 한다.

② if (old = null) then return;

만약 노드 pre가 리스트의 마지막 노드였다면 pre.link값은 null이므로 old의 값은 null이 된다.

즉, pre 뒤에 삭제할 노드가 없다는 의미이다. return으로 종료

③ pre.link ← old.link;

삭제할 노드 old의 다음 노드(old.link)를 노드 pre의 다음 노드(pre.link)로 연결한다.

④ returnNode(old);

삭제할 노드를 반환한다.

Copyrightⓒ2014 By 한빛아카데미(주)

<단순 연결 리스트의 삽입>

 삽입의 알고리즘은 첫 번째 노드로 삽입하는 경우, 중간 노드로 삽입하는 경우, 마지막 노드로 삽입하는 경우로 나뉜다.

1. 첫 번째 노드로 삽입하는 경우

① new ← getNode();
삽입할 노드를 자유 공간리스트에서 할당받는다.

② new.data ← x;
새 노드의 데이터 필드에 x를 저장

③ new.link ← L;
삽입할 노드를 연결하기 위해서 리스트의 첫 번째 노드 주소(L)를 삽입할 새 노드 new의 링크 필드(new.link)에 저장하여, 새 노드 new가 리스트의 첫 번째 노드를 가리키게 한다.

④ L ← new;
리스트의 첫 번째 노드 주소를 저장하고 있는 포인터 L에, 새 노드의 주소 new를 저장하여, 포인터 L이 새 노드를 첫 번째 노드로 가리키도록 지정

2. 중간 노드로 삽입하는 경우

중간에 노드를 삽입하기 위해서는 삽입할 위치의 앞에 있는 선행자 노드를 알려주는 포인터 pre가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

3. 마지막 노드로 삽입하는 경우

마지막에 노드를 삽입하기 위해서는 먼저 마지막 노드를 찾아야 한다. 링크 필드가 null인 노드가 마지막 노드이다. 마지막 노드를 찾기 위해서는 리스트의 노드들을 순회하는 임시 포인터 temp가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

[공백 리스트일 경우]

① L ← new;
리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 한다.

② new.link ← null;
리스트의 마지막 노드인 new의 링크 필드에 null을 저장하여 마지막 노드임을 표시한다.

[공백 리스트가 아닐 경우]

① new.link ← pre.link;
노드 pre의 링크 필드 값을 노드 new의 링크 필드에 저장하여, 새 노드 new가 노드 pre의 다음 노드를 가리키도록 한다.

② pre.link ← new;
포인터 new의 값을 노드 pre의 링크 필드에 저장하여, 노드 pre가 새 노드 new를 다음 노드로 가리키도록 한다.

3. 마지막 노드로 삽입하는 경우

마지막에 노드를 삽입하기 위해서는 먼저 마지막 노드를 찾아야 한다. 링크 필드가 null인 노드가 마지막 노드이다. 마지막 노드를 찾기 위해서는 리스트의 노드들을 순회하는 임시 포인터 temp가 필요하다. 공백 리스트일 경우와 공백 리스트가 아닐 경우로 나뉜다.

[공백 리스트일 경우]

① L ← new;

​리스트 포인터 L에 새 노드 new의 주소를 저장하여, 새 노드 new가 리스트의 첫 번째 노드가 되도록 한다.

② temp ← L;
현재 리스트 L의 마지막 노드를 찾기 위해서 노드를 순회할 임시포인터 temp에 리스트의 첫 번째 노드의 주소(L)를 지정​