제6장. 자료구조 stack 과que

스택과 큐는 각각 배열과 linked list 로 구현할 수 있다.

 

 

 

1. 스택

1) 데이터의 삽입과 삭제가 한쪽 방향에서만 일어나는 구조를 스택이라고 한다.

2) 스택은 가장 나중에 삽입된 데이터가 가장 먼저 나오는  LIFO 후입선출의 자료구조이다.

삽입 : push 삭제 : pop

1.1 배열로 구현한 스택

 

 

삽입)

Int stack_size = 5; 스택이 가득찼을 때 top은 스택의 크기와 같다 If (top이 스택 크기와 같은가) then     스택이 가득 차서 데이터를 삽입하지 못함 else     데이터를 스택의 top 위치에 삽입     top을 1 증가

 

top = 5, stacksize = 5

삭제)

 

If (top이 0인가) then     스택이 비어서 데이터를 삭제하지 못함 else     top을 1 감소     데이터를 담을 변수에 top 위치의 값을 복사

1.2 연결리스트로 구현한 스택

: 리스트로 구현한 스택은 배열로 구현한 스택과 달리 주기억장치의 용량이 허용하는 한 데이터를 삽입할 수 있음

 

삽입)

 

삭제)

 

 

 

2. 큐

1) 데이터가 한쪽 방향으로 삽입되고 반대 방향으로 삭제되는 구조를 스택이라고 한다.

2) 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 FIFO 선입선출의 자료구조이다.

front는 첫 번째 데이터가 저장된 배열의 인덱스

rear는 새로운 데이터가 삽입될 배열의 인덱스

 

2.1 배열로 구현한 큐

삽입)

Int stack_size = 5; 큐가 가득찼을 때 rear는 큐의 크기와 같다 If (rear가 큐의 크기와 같은가) then     큐가 가득 차서 데이터를 삽입하지 못함 else     데이터를 큐의 rear 위치에 삽입     rear를 1 증가

삭제)

 

If (front와 rear가 같은가) then     큐가 비어서 데이터를 삭제하지 못함 else     데이터를 담을 변수에 front 위치의 값을 복사     front를 1 증가

기본 큐는 font가 앞으로 다시 갈 수 없기 때문에 한번 지나가면 앞공간이 비어있더라도 이용할 수 없다.

데이터가 끝 부분에 몰려 있으면 앞쪽에 빈 공간이 있어도 삽입하지 못함

결국 삽입 한번과 삭제 한번을 번갈아 하는 것을 계속 반복할 수 없음

 

2.2 원형 큐(circular queue)

배열로 구현한 큐의 이러한 문제를 해결하기 위해 나온 것이 원형큐(circular queue)이다.

if문으로 rear를 8에서 1로 바꾼다.

큐는 원형큐를 기본이라고 볼 수 있다.

 

2.3 연결리스트로 구현한 큐

 

삽입)

 

 

삭제)