미완성 글입니다.
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를 동시에 수행
배열을 사용해서 구현하는 경우도 있다고 들었다. 그러나 노드의 삽입 / 삭제가 필요하므로 배열을 이용한 구현시 복잡한 연산을 추가해야 할 것을 고려해 양방향 연결리스트로 구현했다.
typedef struct s_node
{
int data; //노드의 값
struct s_node *next; //연결된 다음 노드
struct s_node *prev; //연결된 이전 노드
} t_node
연결리스트를 이용한 구현이기 때문에 메모리누수 검사가 필수다!