[C언어]41일차 - 스택 (이것이 C언어 자료구조 알고리즘이다.)

[C언어]41일차 - 스택 (이것이 C언어 자료구조 알고리즘이다.)

 

1.스택의 개념

2.노드 삽입과 제거 연산

3.배열 기반 스택 구현

4.링크드 리스트 기반 스택 구현

5.스택 기반 계산기 구현

 

 

스택의 개념

 

스택에서 데이터 입/출력은 오로지 스택의 꼭대기에서만 이루어진다.

스택 가운데에 있는 데이터를 삭제하거나 새로운 데이터를 입력하는 일은 허용되지 않는다.

 

-> 가장 마지막에 들어간 데이터가 제일 먼저 나오고, 가장 먼저 들어간 데이터는 가장 나중에 나온다.

 

-> 요소의 삽입과 삭제가 한쪽 끝에서만 이루어지는 것.

 

사용하는곳)

자동 메모리 , 컴파일러의 구문분석기, 네트워크 프로토콜, 이미지 편집 프로그램의 되돌리기

 

 

스택의 핵심 기능: 삽입과 제거 연산

 

스택 ADT의 주요기능은 삽입과 제거 연산 두가지다.

 

 

스택을 배열로 구현하기

 

배열을 이용한 스택은 용량을 동적으로 변경하는 비용이 크다.

하지만 구현이 간단하다.

 

배열 기반의 스택은 각 노드를 동적으로 생성하고 제거하는 대신, 스택 생성 초기에 사용자가 부여한 용량만큼의 노드를 한꺼번에 생성한다. 

그리고 최상위 노드의 위치를 나타내는 변수를 두고 삽입과 제거 연산을 수행한다.

 

스택 노드의 표현

 

 

배열 기반의 스택은 다음 세가지 필드를 가지고 있어야 한다.

 

1.용량 : 스택이 얼마만큼의 노드를 가질 수 있는지 알기 위해 사용

2.최상위 노드의 위치 : 삽입/제거 연산을 할 때 최상위 노드에 접근할 수 있게 도와준다.

3.노드 배열 : 스택에 쌓이는 노드를 보관하는 데 사용된다.

 

Nodes 포인터는 다음 그림과 같이 자유 저장소에 할당된 배열을 가리키는 용도로 사용할 예정이다.

 

 

스택 및 노드 생성

 

 

스택 및 노드 소멸 연산

 

 

노드 삽입 연산

 

삽입 연산은 최상위 노드의 인덱스(Top)에서 1을 더한 곳에 새 노드를 입력하도록 구현한다.

 

 

노드 제거 연산

 

제거 연산에서는 최상위 노드의 인덱스 값을 1만큼 낮추도록 구현한다.

그리고 제거 연산에서는 최상위 노드에 있던 데이터를 호출자에게 반환해야 한다.

 

 

아래 함수를 구현해 보기

 

 

호출 부분

 

 

 

---

 

링크드 리스트로 구현하는 스택

링크드 리스트가 배열보다 좋은 점은 스택 용량에 제한을 두지 않아도 된다는 것.

 

링크드 리스트는 배열과 달리 인덱스를 활용하여 노드에 접근할 수 없습니다.

 

따라서 링크드 리스트로 스택을 구현하려면 노드는 자신의 위에 위치하는 노드에 대한 포인터를 갖고 있어야 한다.

 

 

Data 필드의 자료형이 int나 double 같은 기본 자료형이라면 '값 복사'를 통해 데이터를 담지만

char* 형은 포인터이기 때문에 문자열이 저장된 주소만 담을 수 있다.

 

그리고 이 문자열은 자동 메모리가 아닌 자유 저장소(힙)에 저장되어야 한다.

그 이유는 자동 메모리에 담긴 데이터의 경우 컴파일러가 정해준 수명이 다하면 사라지기 때문이다.

 

 

 

 

 

 

 

 

 

링크드 리스트 스택은 배열 기반 스택과 달리 '스택의 용량' 이나 '최상위 노드의 인덱스'가 없다.

 

대신 링크드 리스트의 헤드(List 포인터)와 테일에 대한 포인터(Top 포인터)가 필요하다.

 

 

 

List 포인터는 데이터를 담는 링크드 리스트를 가리키고, 

Top 포인터는 이 링크드 리스트의 테일을 가리킨다.

 

즉, Top 포인터는 스택의 입출력이 이루어지는 최상위 노드에 대한 포인터이다.

 

Top 포인터 없이도 List 포인터를 이용해서 스택의 최상위에 접근 가능하다.

하지만 순차 탐색을 해야 한다. Top 포인터를 이용하면 8바이트(64비트기준)를 소비하는 대신, 최상위 노드를 찾느라 허비하는 시간을 아낄 수 있다.

 

 

 

 

링크드 리스트 기반 스택의 기본 연산

 

스택 생성 / 소멸 연산

malloc() 함수를 이용해서 LinkedListStack 구조체를 자유 저장소(힙)에 할당하도록 구현.

 

먼저 각 노드를 제거하고 자유 저장소에서 LinkedListStack 구조체를 할당 해제한다.

노드 제거는 함수 앞부분에 있는 while 블록이 담당.

 

LLS_IsEmpty() 함수는 스택이 비어 있는지 점검하고, LLS_Pop 함수는 스택의 최상위 노드를 제거한다.

그리고 LLS_DestroyNode() 함수는 자유저장소에 할당된 노드를 메모리에서 해제 한다.

 

 

노드생성 / 소멸연산

노드를 자유 저장소에 생성할 때 문자열을 저장할 공간도 함께 생성해야 한다.

 

malloc() 함수는 Node 구조체를 할당하기 위해서 한번, 

Node 구조체의 Data 필드를 할당하기 위해 또 한번, 총 2번 호출이 된다.

 

소멸도 free를 두번해준다.

 

 

노드 삽입 연산

 

 

노드 제거 연산

링크드 리스트 기반 스택에서 제거 연산은 다음 네 단계로 이루어진다.

 

1.현재 최상위 노드(top)의 주소를 다른 포인터에 복사한다.

2.새로운 최상위 노드(현재 최상위 노드)의 바로 아래(이전) 노드를 찾는다.

3.LinkedListStack 구조체의 top 필드에 새로운 최상위 노드의 주소를 등록한다.

4.1단계에서 포인터에 저장했던 예전 최상위 노드의 주소를 반환한다.

 

 

기본 함수

 

 

호출부분