스택과 대기열의 차이점

• 2019

스택과 큐는 둘 다 비 기본 데이터 구조입니다. 스택과 큐의 주된 차이점은 스택이 데이터 요소를 액세스하고 추가하는 데 LIFO (LAST in first out) 메서드를 사용하는 반면 Queue는 FIFO (First In First Out) 메서드를 사용하여 데이터 요소에 액세스하고 추가한다는 점입니다.

스택에는 데이터 요소를 밀어 넣기 및 팝핑 할 수있는 단 하나의 끝이 있습니다. 큐는 데이터 요소를 대기열에 넣고 대기열에두기 위해 양쪽 끝이 열려 있습니다.

스택 및 큐는 데이터 요소를 저장하는 데 사용되는 데이터 구조이며 실제로는 일부 실제 환경에 기반합니다. 예를 들어, 스택은 CD 스택을 가져 와서 CD 스택 맨 위에 놓을 수 있습니다. 마찬가지로 대기열은 극장 티켓의 대기열로, 대기열의 맨 앞에 서있는 사람이 먼저 처리되고 새로운 사람이 도착하면 대기열의 후면 (대기열의 뒤쪽 끝에)에 나타납니다.

비교 차트

비교 근거	스택	열
작동 원리	LIFO (최후 동의)	FIFO (선입 선출)
구조	동일한 끝은 요소를 삽입하고 삭제하는 데 사용됩니다.	한쪽 끝이 삽입에 사용됩니다. 즉, 뒤쪽 끝과 다른 쪽 끝은 요소 삭제에 사용됩니다 (예 : 프런트 엔드).
사용 된 포인터의 수	하나	2 개 (단순 대기열 경우)
수행 된 작업	푸시 앤 팝	큐 삽입 및 큐 풀 해제
빈 상태 검사	상위 == -1	앞 == -1 || 전면 == 후면 + 1
전체 상태 검사	상위 == 최대 - 1	후면 == 최대 - 1
변형	변종이 없습니다.	순환 대기열, 우선 순위 대기열, 이중 종료 대기열과 같은 변형이 있습니다.
이행	보다 단순한	비교적 복잡한

스택 정의

스택은 프리미티브가 아닌 선형 데이터 구조입니다. 새 항목이 추가되고 기존 요소가 스택 상단 (TOS)이라고하는 한쪽 끝에서만 삭제되는 순서 목록입니다. 스택의 모든 삭제 및 삽입은 스택의 맨 위에서 이루어 지므로 마지막으로 추가 된 요소가 스택에서 맨 처음 제거됩니다. 그래서 스택을 LIFO (Last-In-First-Out) 유형의 목록이라고합니다.

스택에서 자주 액세스되는 요소는 최상위 요소 인 반면 사용 가능한 마지막 요소는 스택의 맨 아래에 있음에 유의하십시오.

예

당신 중 일부는 비스킷 (또는 포핀 스)을 먹을 수 있습니다. 당신이 가정하면, 덮개의 한쪽 면만 찢어지고 비스킷은 하나씩 꺼내집니다. 이것은 팝핑 (popping)이라고 불리는 것이며, 나중에 약간의 비스킷을 얼마 동안 보존하려는 경우 푸시라고하는 동일한 찢어진 끝을 통해 팩에 넣을 것입니다.

대기열 정의

대기열은 비선형 유형의 범주에 속하는 선형 데이터 구조입니다. 유사한 유형의 요소 모음입니다. 새로운 요소의 추가는 뒤쪽이라는 한쪽 끝에서 이루어집니다. 마찬가지로 기존 요소의 삭제는 프런트 엔드라고하는 다른 끝에서 발생하며 논리적으로 FIFO (First In First Out) 유형의 목록입니다.

예

일상 생활에서 우리는 원하는 서비스를 기다리는 많은 상황에 직면하게됩니다. 서비스를 받기 위해 기다릴 라인을 기다려야합니다. 이 대기 대기열은 대기열로 생각할 수 있습니다.

스택과 대기열의 주요 차이점

1. Stack은 LIFO 메커니즘을 따르는 반면, Queue는 FIFO 메커니즘을 따라 요소를 추가하고 제거합니다.
2. 스택에서는 동일한 끝을 사용하여 요소를 삽입하고 삭제합니다. 반대로 큐에 두 개의 다른 끝이 사용되어 요소를 삽입하고 삭제합니다.
3. 스택에는 열린 단 하나만 있기 때문에 하나의 포인터 만 사용하여 스택의 맨 위를 참조해야합니다. 그러나 큐는 두 개의 포인터를 사용하여 큐의 앞쪽과 뒤쪽을 참조합니다.
4. Stack은 대기열에있는 동안 대기열 및 대기열로 알려진 두 가지 작업을 수행합니다.
5. 스택 구현은 쉽지만 큐 구현은 까다 롭습니다.
6. 대기열에는 순환 대기열, 우선 순위 대기열, 이중 종료 대기열 등의 변형이 있습니다. 반대로 스택에는 변형이 없습니다.

스택 구현

스택은 두 가지 방법으로 적용 할 수 있습니다.

1. 정적 구현 은 배열을 사용하여 스택을 만듭니다. 정적 구현은 손쉬운 기법이지만 유연한 작성 방법이 아닙니다. 크기를 선언 할 수 없기 때문에 프로그램 설계 중에 스택 크기 선언을 수행해야합니다. 또한 메모리 사용과 관련하여 정적 구현은 그리 효율적이지 않습니다. (스택을 구현하기위한) 배열은 (프로그램 설계시에) 연산의 시작 전에 선언되기 때문에. 정렬 될 요소의 수가 스택에서 매우 적 으면 정적으로 할당 된 메모리가 낭비됩니다. 반면에 스택에 저장할 요소의 수가 더 많으면 배열의 크기를 변경하여 용량을 늘릴 수 없으므로 새로운 요소를 수용 할 수 있습니다.
2. 동적 구현 은 연결된 목록 표현이라고도하며 포인터를 사용하여 데이터 구조의 스택 유형을 구현합니다.

대기열 구현

대기열은 두 가지 방법으로 구현 될 수 있습니다.

1. 정적 구현 : 배열을 사용하여 큐를 구현하는 경우, 디자인 타임에 또는 처리가 시작되기 전에 배열의 크기를 선언해야하기 때문에 대기열에 저장하려는 정확한 요소 수를 미리 확인해야합니다. 이 경우 배열의 시작 부분이 대기열의 맨 앞에 오며 배열의 마지막 위치는 대기열의 뒷면으로 작동합니다. 다음 관계는 배열을 사용하여 구현 될 때 전체 요소가 대기열에 있음을 나타냅니다.
   앞 - 뒤 + 1
   "rear <front"이면 대기열에 요소가 없거나 대기열이 항상 비어있게됩니다.
2. 동적 인 구현 : 포인터를 사용하여 큐를 구현하면 링크 된 표현의 노드가 배열 표현의 해당 요소보다 많은 메모리 공간을 사용한다는 단점이 있습니다. 각 노드에는 적어도 두 개의 필드가 있으므로 하나의 데이터 필드는 다른 노드의 주소를 저장하는 반면, 연결된 표현은 데이터 필드 만 존재합니다. 링크 된 표현을 사용하는 장점은 다른 요소 그룹의 중간에 요소를 삽입하거나 삭제해야 할 때 명확 해집니다.

스택 작업

스택에서 작동 할 수있는 기본 작업은 다음과 같습니다.

1. PUSH : 새로운 요소가 스택 맨 위에 추가되면 PUSH 연산이라고합니다. 스택의 요소를 누르면 새 요소가 맨 위에 삽입되므로 요소를 추가합니다. 각 푸시 조작 후 상단이 1 씩 증가합니다. 배열이 꽉 차고 새 요소를 추가 할 수 없으면 STACK-FULL 조건 또는 STACK OVERFLOW라고합니다. PUSH OPERATION - C의 기능 :
   스택 고려는 다음과 같이 선언됩니다.
   int stack [5], top = -1;
void push()
{
int item;
if (top < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
top = top + 1;
stack [top] = item;
}
else
{
printf (" Stack is full");
}
}
2. POP : 스택 맨 위에서 요소를 삭제하면이를 POP 작업이라고합니다. 스택은 팝 동작마다 1 씩 감소합니다. 요소가 스택에 남아 있지 않고 팝이 수행되면 스택이 비어 있음을 의미하는 STACK UNDERFLOW 조건이 발생합니다. POP 작동 - C의 기능 :
   스택 고려는 다음과 같이 선언됩니다.
   int stack [5], top = -1;
void pop()
{
int item;
if (top >= 4)
{
item = stack [top];
top = top - 1;
printf ("Number deleted is = %d", item) ;
}
else
{
printf (" Stack is empty");
}
}

대기열에 대한 작업

대기열에서 수행 할 수있는 기본 작업은 다음과 같습니다.

1. 큐 삽입 : 요소를 큐에 삽입합니다. C :
   대기열은 다음과 같이 선언됩니다.
   int queue [5], Front = -1 and rear = -1;
void add ()
{
int item;
if ( rear < 4)
{
printf ("Enter the number") ;
scan ("%d", & item) ;
if (front == -1)
{
front =0 ;
rear =0 ;
}
else
{
rear = rear + 1;
}
queue [rear] = item ;
}
else
{
printf ("Queue is full") ;
}
}

2. Dequeue : 큐에서 요소를 삭제합니다. C :
   대기열은 다음과 같이 선언됩니다.
   int queue [5], Front = -1 and rear = -1;
void delete ()
{
int item;
if ( front ! = -1)
{
item = queue [ front ] ;
if (front == rear)
{
front =-1 ;
rear =-1 ;
}
else
{
front = front + 1;
printf ("Number deleted is = %d", item) ;
}
}
else
{
printf ("Queue is empty") ;
}
}

스택의 응용

• 컴파일러에서 구문 분석.
• 자바 가상 머신.
• 워드 프로세서에서 실행 취소하십시오.
• 웹 브라우저의 뒤로 단추.
• 프린터 용 포스트 스크립트 언어.
• 컴파일러에서 함수 호출 구현.

대기열 응용 프로그램

• 데이터 버퍼
• 비동기 데이터 전송 (파일 IO, 파이프, 소켓).
• 공유 리소스 (프린터, 프로세서)에 대한 요청 할당.
• 트래픽 분석.
• 슈퍼마켓에 가지고있을 출납원 수를 결정하십시오.

결론

스택 및 큐는 작업 메커니즘, 구조, 구현, 변형과 같은 특정 방식으로 선형 데이터 구조가 다르지만 둘 다 요소를 목록에 저장하고 요소의 추가 및 삭제와 같이 목록에서 작업을 수행하는 데 사용됩니다. 다른 유형의 대기열을 사용하여 단순 대기열에 대한 제한이 있지만.