Stack vs Queue

Stack(스택)

1. LIFO(후입선출)

 - 가장 나중에 들어온 값이 가장 먼저 나오는 구조 

 

2. 스택이 사용되는 곳 

 가. 함수의 콜 스택 

 나. 연산자 후위 표기법 

 다. 시스템 스택 

 라. 뒤로가기 버튼 

 

3. 스택이 가지고 있는 함수 

 가. push(): 데이터를 넣는다. 

 나. pop(): 데이터를 꺼낸다. 

 다. isEmpty(): 스택이 비어있는지 확인한다.

 라. isFull(): 스택이 꽉 차있는지 확인한다. 

 

4. 스택포인터

  가. push(), pop()을 할 때 해당 위치를 알고 있어야 하므로, 해당위치를 기억하고 있는 포인터

  나. 스택 포인터의 초기화 값은 -1

 

Queue(큐)

1. FIFO(선입 선출)

- 가장 먼저 들어온 값이 가장 먼저 나오는 구조 

 

2. 큐가 사용되는 곳 

 가. 이벤트 큐 

 나. 데이터 버퍼 

 다. cpu 스케쥴링 

 

3. 큐가 가지고 있는 함수 

 가. enQueue(): 데이터를 넣는다. 

 나. deQueue(): 데이터를 꺼낸다.

 다. isEmpty(): 큐가 비어있는지 확인한다.

 라. isFull(): 큐가 꽉 차있는지 확인한다. 

 

4. 큐의 특징 

 가. 큐에 가장 첫 원소를 front, 끝 원소를 rear라고 부른다. 

 나. 큐는 데이터가 들어올 때 rear로 들어오지만, 나올때는 front 부터 빠진다. 

 다. 접근 방법은 가장 첫 원소와 끝 원소만 가능하다. 

 라. 데이터를 넣고 뺄 때 front와 rear를 통해 해당 값의 위치를 기억한다. 

 

5. 일반 큐의 단점 

 가. 큐의 빈 메모리가 남아있음에도 불구하고, 꽉 차있는 것처럼 판단될 수 있다. 

 나. 이를 개선한 것이 원형 큐이다. 

 다. 원형큐는 논리적으로 배열의 처음과 끝이 연결되어 있는 구조이다. 

 

< 참고자료 >

 

[도서] 자료구조  - 정광식 지음-

 

<Data structures> chapter 4, Stack vs Queue  end

---