데이터 구조 5 (String , Stack 응용)

• Strings - 문자열

→ 길이 (데이터,메모리) 낭비 문제가 발생한다.

→ C++ String 라이브러리에서는 길이를 신경 쓰지 않기 때문에 

→ Char [@]면 입력 시 가장 마지막은 'NULL' 

     = NULL까지 유효하게 인정.

     = String 에서는 NULL 신경 X

 

1. C언어에서는 (String이 없어서) array의 형태로 선언해야 한다. ex) char[20]

    # 추가공간까지 고려해야 한다.

2. 개별 원소를 단일 문자 취급 가능                 ex) str[3] = 'K'

3. 초기화 가능. 배열 10칸에서 문자 4개만 입력하면  t,e,s,t,\0 이렇게 5개 초기화됨

4. String 연산 library 사용 가능(strcpy or strncpy)

 

• C-string

char str[20];

Input → cin >> str;

Output → cout << str;

 

- #include <string>

- Object 생성 → string st1, st2;

- String 관련 연산자 

        = : assignment, 값 할당 가능

        + : concatenation, 뒤에 붙이는 거 가능 

        ==, != : equality test

 

* String 이랑 Char[] 연산을 할 때 String 이 char보다 앞에 와야 한다.

 

String member function      

→ Size() = strlen 기능을 함  ex) s1.size

 

String의 장점

      1.  Consistency : Char[  ]이 아닌 String 그 자체임  → 메모리 효율적.

      2.  Convienece : Operator 사용 가능

      3.  Dynamic length 덕분에 메모리 걱정 안 해도 됨.

      4.  기존 C-String 기능과 상호연산 가능

 

---

              Stack 응용

 

 

• Post fix '계산'

(3+2) * (4-1) =15

→ 3 2 + 4 1 - *   

그림으로 그려보자.

1)

1 ) 3 2 순서로 push를 하던 도중, operator인 +를 만나면 스택 안에 있는 값을 꺼내는데

    밑에 있는 숫자가 앞으로 가게 설정하여 계산하고, 결괏값은 다시 스택에 넣는다. 

 

2)

2 ) 앞 과정의 결과로 5가 제일 밑에 들어간 뒤에, 그 뒤에 operator인 -가 나올 때까지 계속 Push했다.

1이랑 4를 꺼내야 하는데 앞 과정과 마찬가지로 4가 앞으로 가도록 하여 계산하고, 결괏값은 다시 stack에 넣는다.

 

 

3)

3) 5*3 = 15. 

 

 

• Stack permutation (스택 순열)

// 뭔지만 알면 됨 (4월달에 제대로 배운다고 함)

 

A → Stack → B로 갈 때

Push와 Pop 을 임의로 했을 때 B에 나오는 결괏값들의 경우의 수 느낌

 

 

출처 : 한동대학교 김호준교수님 - 데이터구조 PPT