Stack & Queue 개념

Stack

스택은 쌓아 올린다는 것을 의미한다. 따라서, 스택의 자료구조는 차곡차곡 쌓아 올린 형태를 보여준다.

Stack

 

특징

• 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다.
• top에 있는 자료는 가장 최근에 들어온 자료를 가리키며, 새로 추가되는 자료는 top에 있는 자료의 위에 쌓인다.
• 스택에서 top을 통해 삽입하는 연산을 ‘push’, top을 통해 삭제하는 연산을 ‘pop’이라고 한다. 따라서, 스택은 시간 순서에 따라 자료가 쌓이기에 가장 마지막에 삽입된 자료가 가장 먼저 삭제된다는 구조적 특징을 지니게 된다.
  • 이러한 구조를 후입선출(LIFO, Last-In-First-Out)구조라고 한다.

Stack Overflow

• 스택이 넘치는 경우

Stack Underflow

• 비어있는 스택에서 원소를 추출하는 경우

---

Queue

큐는 줄 혹은 줄을 서서 기다리는 것을 의미한다. 따라서, 먼저 온 사람이 먼저 업무를 보는 것과 같이 선입선출(FIFO, First-In-First-Out)의 구조를 띈다.

Queue

 

특징

• 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.
  • 이때, 삭제 연산만 수행되는 곳을 front, 삽입 연산만 이루어지는 곳을 rear로 정하여 각각의 연산 작업만 수행된다.
    • Queue의 rear에서 이루어지는 삽입 연산을 enQueue(인큐)
    • Queue의 front에서 이루어지는 삭제 연산을 deQueue(디큐)
• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올 때는 front부터 나온다.
  • 접근 방법은 front와 rear로만 가능
• 가장 먼저 들어온 front 원소가 가장 먼저 삭제
  • 즉, front 원소는 가장 먼저 큐에 들어왔던 첫 번째 원소가 되고 rear 원소는 가장 늦게 들어온 마지막 원소가 된다.

---

Stack과 Queue의 차이점

	Stack	Queue
입출력 방식	LIFO	FIFO
데이터 삭제 시	가장 마지막에 입력된 데이터 삭제	가장 먼저 입력된 데이터 삭제

 

 

Stack과 Queue의 장단점

	Stack	Queue
장점	1. 구현이 쉽다. 2. 원하는 데이터의 접근 속도가 빠르다. (bottom이 고정되어 있으므로)	1. 데이터가 입력된 시간 순서대로 처리가 가능하다.
단점	1. 데이터 최대 개수를 정해야 한다. (bottom에 있는 것을 삭제하려면, top부터 삭제해야 한다.) 2. 데이터의 삽입과 삭제가 비효율적이다.	1. 크기가 제한적이다. 2. 큐의 앞 부분이 비어도 데이터를 삽입할 수 없다. 3. 큐가 비어있을 때도 rear가 맨 뒤에 있을 경우에는 Not Empty라고 판단할 수 없다.