자료구조(6/10)- 스택, 큐, 덱

OS내부의 많은 시스템이  스택과 큐를 기반으로 하며,

그래프와 트리 순회도 결국은 스택과 큐로 한다. 깊이 우선 탐색은 스택을 이용하는 순회이고, 너비우선 탐색은 큐를 기반으로 한다. 등등

스택과 큐에 대해서, 효율적인 스택과 큐를 구현하는 법에 대해서 알아보장

 

1. 스택: 데이터를 차곡차곡 쌓는다

한쪽만 출입구인 ㄷ 자모양에 데이터를 넣고 뺀다.

PUSH, POP => LIFO(last in first out: 가장마지막에 들어온애가 가장 먼저 나간다)

 

<ADT>

STACK

- Object : LIFO 객체

- Operation: 

 1) empty() : boolean  비었니?

 2) push(data) : void 삽입

 3) pop() : element 삭제(반환도 동시에)

 4) peek() : element 반환만

 

 

2. 큐: 데이터로 줄 세우기

기본적인 줄서기를 생각하면 된다. 먼저 온 사람이 먼저 입장한다.

FIFO(first in first out: 먼저 온애가 먼저 나간다)

 

<ADT>

Queue

- Object : FIFO 객체

- Operation: 

 1) empty() : boolean  비었니?

 2) full(): boolean 꽉 찼니? 

 3) enqueue(data) : 큐의 맨 뒤에 데이터 삽입

 4) dequeue() : element 큐의 맨 처음 데이터를 삭제하면서 반환(앞으로 pop같은 느낌)

 5) peek() : element 큐의 맨 처음 데이터를 삭제하지 않고 반환만(앞으로 peek같은 느낌)

 

 

2-1. 원형 큐

 

 

3. 덱: 스택으로도 큐로도 사용할 수 있다(양방향 큐)

<ADT>

Deque

- Operation: 

 1) empty() : boolean  비었니?

 2) full(): boolean 꽉 찼니? 

 3) insertFront(data) : 덱의 맨 앞에 데이터 삽입

 4) insertRear(data) : 덱의 맨 뒤에 데이터 삽입

 5) popFront() : element 덱의 맨 처음 데이터를 삭제하면서 반환

 6) popRear() : element 덱의 맨 앞 데이터를 삭제하면서 반환

 7) peekFront() : element 덱의 맨 앞 데이터를 삭제하지 않고 반환(앞으로 peak같은 느낌)

 8) peekRear() : element 덱의 맨 처음 데이터를 삭제하지 않고 반환만(뒤으로 peek같은 느낌)