Stack과 Queue

스택(Stack)

스택은 LIFO(Last In First Out) 법칙을 분리하여 데이터 구조로 , 마지막으로 삽입된 요소가 가장 먼저 팝됩니다. 즉, 삽입 및 삭제 작업이 끝에서만 발생한다는 의미입니다.

LIFO(후입선출)

프링글스통을 상상하면 편하다. 우리가 통에 감자칩을 여러개 넣고 맨아래 감자칩을 빼려면 위에 감자칩부터 먼저 빼야할 것이다.

스택 데이터 구조의 표현:

스택은 LIFO(마지막에 들어간 요소가 먼저 나감) 원칙을 따르므로 마지막으로 푸시된 요소가 먼저 팝됩니다.

스택의 종류:

• 고정 크기 스택 : 이름에서 알 수 있듯이 고정 크기 스택은 고정된 크기를 가지며 동적으로 커지거나 줄어들 수 없습니다. 스택이 가득 차 있고 요소를 추가하려고 하면 오버플로 오류가 발생합니다. 스택이 비어 있고 요소를 제거하려고 하면 언더플로 오류가 발생합니다.
• 동적 크기 스택 : 동적 크기 스택은 동적으로 커지거나 줄어들 수 있습니다. 스택이 가득 차면 새 요소를 수용하기 위해 자동으로 크기가 커지고, 스택이 비어 있으면 크기가 줄어듭니다. 이 유형의 스택은 연결 리스트를 사용하여 구현되며, 스택의 크기를 쉽게 조정할 수 있습니다.

스택의 기본 작업:

스택에서 조작을 하기 위해서는 특정 연산이 제공됩니다.

• push()를 사용하여 스택에 요소를 삽입합니다.
• 스택에서 요소를 제거하려면 pop()을 사용 합니다.
• top() 스택의 맨 위 요소를 반환합니다.
• isEmpty()는 스택이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
• isFull()은 스택이 가득 찼으면 true를 반환하고 그렇지 않으면 false를 반환합니다.

스택에 항목을 추가합니다. 스택이 가득 차면 Overflow condition 이라고 합니다 .

푸시 작업 알고리즘:

• 스택에 요소를 푸시하기 전에 스택이 가득 찼는 지 확인합니다 .
• 스택이 가득 찬 경우 (top == capacity-1) , Stack Overflow가 발생하여 스택에 요소를 삽입할 수 없습니다.
• 그렇지 않으면, top의 값을 1 증가시키고 (top = top + 1) 새로운 값이 최상위 위치 에 삽입됩니다 .
• 스택의 용량 에 도달할 때까지 요소를 스택에 넣을 수 있습니다 .

스택에서의 팝 연산

스택에서 항목을 제거합니다. 항목은 푸시된 순서의 역순으로 팝됩니다. 스택이 비어 있으면 Underflow condition이라고 합니다 .

팝 연산을 위한 알고리즘:

• 스택에서 요소를 팝하기 전에 스택이 비어 있는지 확인합니다 .
• 스택이 비어 있는 경우(top == -1), 스택 언더플로가 발생 하고 스택에서 어떤 요소도 제거할 수 없습니다.
• 그렇지 않으면, 우리는 top에 값을 저장하고, top의 값을 1 감소시킨 후 (top = top - 1) 저장된 top 값을 반환합니다.

스택에서 Top 또는 Peek 작업

스택의 맨 위 요소를 반환합니다.

이 작업들을 위한 알고리즘:

• 스택의 맨 위 요소를 반환하기 전에 스택이 비어 있는지 확인합니다.
• 스택이 비어 있으면(top == -1), 단순히 "스택이 비어 있습니다"를 출력합니다.
• 그렇지 않으면 index = top 에 저장된 요소를 반환합니다 .

스택에서 isEmpty 작업:

스택이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

isEmpty 작업에 대한 알고리즘 :

• 스택에서 top 의 값을 확인합니다 .
• (top == -1) 이면 스택이 비어 있으므로 true를 반환합니다 .
• 그렇지 않으면 스택이 비어 있지 않으므로 false를 반환합니다 .

스택에서 isFull 작업 :

스택이 가득 찼으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

isFull 연산을 위한 알고리즘:

• 스택에서 top 의 값을 확인합니다 .
• (top == capacity-1) 이면 스택이 가득 찼 으므로 true를 반환합니다 .
• 그렇지 않으면 스택이 가득 차지 않았으므로 false를 반환합니다 .

 

 

스택의 응용 분야:

• 함수 호출: 스택은 함수 호출의 반환 주소를 추적하는 데 사용되며, 이를 통해 함수 실행이 완료된 후 프로그램이 올바른 위치로 돌아갈 수 있습니다.
• 재귀: 스택은 재귀 함수 호출의 로컬 변수와 반환 주소를 저장하는 데 사용되며, 이를 통해 프로그램은 재귀의 현재 상태를 추적할 수 있습니다.
• 표현식의 평가: 스택은 후위 표기법(역 폴란드 표기법)의 표현식을 평가하는 데 사용됩니다.
• 구문 분석: 스택은 프로그래밍 언어와 기타 공식 언어의 구문 유효성을 검사하는 데 사용됩니다.
• 메모리 관리: 스택은 일부 운영 체제와 프로그래밍 언어에서 메모리를 할당하고 관리하는 데 사용됩니다.
• Next Greater , Previous Greater , Next Smaller , Previous Smaller , 히스토그램의 가장 큰 영역 및 스톡 스팬 문제 와 같은 널리 알려진 문제를 해결하는 데 사용됩니다 .

스택의 장점:

• 단순성: 스택은 간단하고 이해하기 쉬운 데이터 구조이므로 다양한 애플리케이션에 적합합니다.
• 효율성: 스택에 대한 푸시 및 팝 작업은 상수 시간 (O(1)) 안에 수행될 수 있어 데이터에 효율적으로 액세스할 수 있습니다.
• 후입선출(LIFO): 스택은 LIFO 원칙을 따르며, 스택에 추가된 마지막 요소가 가장 먼저 제거되도록 합니다. 이 동작은 함수 호출 및 표현식 평가와 같은 여러 시나리오에서 유용합니다.
• 제한된 메모리 사용: 스택은 푸시된 요소만 저장하면 되므로 다른 데이터 구조에 비해 메모리 효율성이 높습니다.

스택의 단점:

• 제한된 접근: 스택의 요소는 맨 위에서만 접근할 수 있으므로 스택 중간의 요소를 검색하거나 수정하는 것이 어렵습니다.
• 오버플로우 가능성: 스택에 수용 가능한 것보다 더 많은 요소가 입력되면 오버플로우 오류가 발생하여 데이터 손실이 발생합니다.
• 임의 접근에 적합하지 않음: 스택은 요소에 대한 임의 접근을 허용하지 않으므로 특정 순서로 요소에 접근해야 하는 애플리케이션에 적합하지 않습니다.
• 제한된 용량: 스택은 고정된 용량을 가지므로, 저장해야 할 요소의 수가 알려지지 않았거나 변동성이 큰 경우 제한이 될 수 있습니다.

큐(Queue)

큐 는 FIFO(선입선출) 원칙을 따르는 선형 데이터 구조 이므로 먼저 삽입된 요소가 먼저 꺼내집니다.

큐의 FIFO 원칙:

FIFO 원칙은 대기열에 추가된 첫 번째 요소가 가장 먼저 제거되거나 처리된다는 것을 나타냅니다. 따라서 대기열은 티켓을 구매하기 위해 기다리는 사람들의 줄과 같으며, 줄을 선 첫 번째 사람이 가장 먼저 서비스를 받는 사람입니다. (즉, 선착순).

큐의 기본 용어

• 프런트: 큐에서 서비스될 준비가 된 항목의 위치, 즉 큐에서 제거될 첫 번째 항목을 큐의 프런트 라고 합니다. 큐의 헤드 라고도 합니다 .
• 뒤: 큐의 마지막 항목, 즉 가장 최근에 추가된 항목의 위치를 ​​큐의 뒤 라고 합니다. 큐의 꼬리 라고도 합니다 .
• 크기: 크기는 대기열에 있는 현재 요소 수 를 나타냅니다 .
• 용량: 용량은 큐가 보유할 수 있는 최대 요소 수 를 나타냅니다 .

큐의 표현

대기열 작업

1. 인큐:

인큐 작업은 큐의 끝에 요소를 추가(또는 저장)합니다 .

단계:

1. 큐가 가득 찼는 지 확인합니다 . 그렇다면 오버플로 오류를 반환하고 종료합니다.
2. 대기열이 가득 차지 않았다면 뒤쪽 포인터를 다음으로 사용 가능한 위치로 증가시킵니다 .
3. 요소를 뒤쪽에 삽입합니다.

2. 대기열에서 빼기: 

Dequeue 작업은 큐의 앞에 있는 요소를 제거합니다. Dequeue 작업을 수행하기 위해 다음 단계를 수행합니다.

1. 큐가 비어 있는지 확인합니다 . 그렇다면 언더플로 오류를 반환합니다.
2. 앞쪽 의 요소를 제거하세요 .
3. 앞쪽 포인터 를 다음 요소로 증가시킵니다 .

3. 피크 또는 프런트 작업: 

이 작업은 요소를 제거하지 않고 프런트 엔드에 있는 요소를 반환합니다.

4. 크기 작업:

이 연산은 대기열에 있는 요소의 개수를 반환합니다.

5. isEmpty 작업: 

이 연산은 대기열이 비어 있는지 여부를 나타내는 부울 값을 반환합니다.

6. isFull Operation: 

이 연산은 대기열이 가득 찼는지 여부를 나타내는 부울 값을 반환합니다.

큐 데이터 구조 구현

다음 데이터 구조를 사용하여 큐를 구현할 수 있습니다.

• 배열을 사용한 Queue 구현 
• 연결리스트를 이용한 구현

큐의 종류

큐 데이터 구조는 4가지 유형으로 분류될 수 있습니다.

1. 단순 큐: 단순 큐는 단순히 FIFO 구조를 따릅니다 . 큐의 뒤쪽에만 요소를 삽입하고 앞쪽에서만 요소를 제거할 수 있습니다.
2. 양단 큐(Deque) : 양단 큐에서는 삽입 및 삭제 작업이 양쪽 끝에서 모두 수행될 수 있습니다. 두 가지 유형이 있습니다.
   • 입력 제한 큐: 이것은 간단한 큐입니다. 이 유형의 큐에서 입력은 한쪽 끝에서만 가져올 수 있지만 삭제는 어느 쪽 끝에서나 할 수 있습니다.
   • 출력 제한 큐: 이것도 간단한 큐입니다. 이 유형의 큐에서는 양쪽 끝에서 입력을 받을 수 있지만 삭제는 한쪽 끝에서만 가능합니다.
3. 원형 큐: 이것은 마지막 위치가 첫 번째 위치에 다시 연결되는 특수한 유형의 큐입니다. 여기서도 작업은 FIFO 순서로 수행됩니다.
4. 우선순위 큐 : 우선순위 큐는 요소에 할당된 우선순위에 따라 액세스하는 특수 큐입니다. 두 가지 유형이 있습니다.
   • 오름차순 우선순위 큐: 오름차순 우선순위 큐에서 요소는 우선순위 값의 증가 순서대로 정렬됩니다. 우선순위 값이 가장 작은 요소가 먼저 팝됩니다.
   • 내림차순 우선순위 큐: 내림차순 우선순위 큐에서 요소는 우선순위 값의 감소 순서로 정렬됩니다. 우선순위가 가장 높은 요소가 먼저 팝됩니다.

• 큐의 응용 프로그램:
  • 멀티 프로그래밍: 멀티 프로그래밍은 주 메모리에서 여러 프로그램이 실행되는 것을 의미합니다. 이러한 여러 프로그램을 구성하는 것이 필수적이며 이러한 여러 프로그램은 큐로 구성됩니다. 
  • 네트워크: 네트워크에서 큐는 라우터나 스위치와 같은 장치에서 사용됩니다. 큐의 또 다른 응용 분야는 메일 큐입니다. 메일 큐는 데이터를 저장하고 메일 메시지에 대한 파일을 제어하는 ​​디렉토리입니다.
  • 작업 스케줄링: 컴퓨터에는 특정 수의 작업을 실행하는 작업이 있으며, 이 작업은 차례로 실행되도록 스케줄링됩니다. 이러한 작업은 큐를 사용하여 구성된 프로세서에 하나씩 할당됩니다.
  • 공유 리소스: 큐는 단일 공유 리소스에 대한 대기 목록으로 사용됩니다.
  Queue의 실시간 적용:
  • 느린 장치와 빠른 장치 사이의 버퍼로 작동합니다. 예를 들어 키보드와 CPU, 그리고 네트워크의 두 장치사이에서  버퍼로 작동한다.
  • ATM 부스 라인
  • 티켓 카운터 라인
  • CPU 작업 스케줄링
  큐의 장점:
  • 대량의 데이터를 쉽고 효율적으로 관리할 수 있습니다.
  • 삽입이나 삭제와 같은 작업은 선입 선출 규칙을 따르므로 손쉽게 수행할 수 있습니다.
  • 큐는 특정 서비스를 여러 소비자가 사용할 때 유용합니다.
  • 큐는 프로세스 간 데이터 통신의 속도가 빠릅니다.
  • 큐는 다른 데이터 구조를 구현하는 데 사용될 수 있습니다.
  큐의 단점:
  • 중간에서 요소를 삽입하거나 삭제하는 등의 작업은 시간이 많이 걸린다.
  • 기존 큐에서는 기존 요소가 큐에서 삭제된 경우에만 새로운 요소를 삽입할 수 있습니다.
  • 요소 검색에는 O(N) 시간이 걸립니다.
  • 배열 구현의 경우 큐의 최대 크기를 미리 정의해야 합니다.