4. 스택(stack)

1. 스택 자료 구조

스택은 후입선출(Last In First Out, LIFO) 방식을 따르는 자료구조이다.

마지막에 들어온 요소가 가장 먼저 나가는 특징을 가진다. 

1-1. 스택의 구조 

 * 구조

   - 후입선출(Last In First Out) 방식을 따르는 선형 구조이다.

   - 데이터는 한쪽 끝에서만 추가되거나 제거된다.

 * 접근 방식 

   - 오직 스택의 맨 위(Top)에서만 데이터에 접근이 가능하다.

   - 삽입(push)와 삭제(pop) 작업은 스택의 top에서만 이루어진다.

 * 용도

   - 재귀 알고리즘, 함수 호출, 역순 문자열 생성, 후위 표현식 계산 등에 사용된다.

   - 데이터의 순서를 일시적을 뒤집거나, 가장 최근의 요소에 빠르게 접근할 필요가 있을 때 유용하다.

 * 구현

   - 배열이나 연결 리스트를 사용하여 구현할 수 있다.

   - 연결 리스트를 사용한 구현은 유연성이 더 높으며, 스택의 크기 제한이 없다.

 

1-2. 연결 리스트와 스택

 - 동적 구조 : 두 자료 구조 모두 실행 시간에 크기가 변경될 수 있다. - 기본 연산 : 삽입, 삭제, 조회 등 기본적인 자료 구조 연산을 지원한다.연결 리스트는 유연하고 다양한 위치에서의 삽입 및 삭제가 가능한 반면, 스택은 매우 제한적인 접근 방식(LIFO)을 가지고 있다.스택은 연결 리스트를 사용하여 구현될 수 있으며, 연결 리스트의 appendleft와 popleft 메서드가 각각 스택의 push와 pop 연산에 해당한다. 

1-3. Stack 클래스 구현

 - 노드 클래스(Node)

   * 

스택에 저장될 각 요소를 표현하는 노드 클래스이다.

   * 각 노드는 데이터(data)와 다음 노드를 가리키는 포인터(next)를 가지고 있다.

 - 스택 클래스(Stack)

   * 스택의 기본적인 동작을 구현한다.

   * push : 새로운 데이터를 스택의 맨 위에 추가한다.

   * pop : 스택의 맨 위 데이터를 제거하고 반환한다.

   * peek : 스택의 맨 위 데이터를 확인하지만 제거하지는 않는다.

   * is_empty : 스택이 비어있는지 여부를 반환한다.

 - 메인 함수

   *  스택에 문자 'A', 'B', 'C'를 차례로 추가하고 각 단계에서 peek을 사용하여 맨 위의 데이터를 확인한다.

   *  is_empty 함수를 사용하여 스택이 비어 있지 않은 동안 pop를 호출하여 스택에서 데이터를 제거하고 출력한다.

   * 마지막으로 peek을 호출하여 스택이 비었을 때 상태를 확인한다.