미완성 글입니다.

0. 서브젝트

• a와 b라는 두개의 스택이 주어짐

• b스택은 빈 스택임

• 다음의 연산만으로 스택 a에 모든 자료를 오름차순 정렬해야 함

  • sa : 스택 a의 top 두개의 원소를 교환

  • sb : 스택 b의 top 두개의 원소를 교환

  • ss : sa와 sb를 동시에 수행

  ---

  • pa : 스택 b의 top을 스택 a의 top으로 이동시킴

  • pb : 스택 a의 top을 스택 b의 top으로 이동시킴

  • pp : pa와 pb를 동시에 수행

  ---

  • ra : 스택 a의 원소들을 하나씩 올림. top은 가장 하위 노드가 됨

  • rb : 스택 b의 원소들을 하나씩 올림. top은 가장 하위 노드가 됨

  • rr : ra와 rb를 동시에 수행

  ---

  • rra : 스택 a의 원소들을 하나씩 내림. 가장 하위 노드는 top이 됨

  • rrb : 스택 b의 원소들을 하나씩 내림. 가장 하위 노드는 top이 됨

  • rrr : rra와 rrb를 동시에 수행

---

1. 자료구조

1.1 양방향 연결리스트

배열을 사용해서 구현하는 경우도 있다고 들었다. 그러나 노드의 삽입 / 삭제가 필요하므로 배열을 이용한 구현시 복잡한 연산을 추가해야 할 것을 고려해 양방향 연결리스트로 구현했다.

typedef struct s_node
{
  int data;				//노드의 값
  struct s_node *next;	//연결된 다음 노드
  struct s_node *prev;	//연결된 이전 노드
} t_node

---

2. 구현

2.1. 파싱

2.2. 모래시계 정렬

2.3. 적은 수의 인자 정렬

---

3. 메모리 누수 검사

연결리스트를 이용한 구현이기 때문에 메모리누수 검사가 필수다!