스택과 큐는 선형 테이블의 대표적인 특수 사례로, 둘 다 연산 제약이 있는 선형 테이블, 즉 연산 위치가 각각의 조건을 만족해야 하며 이러한 조건의 특수성 때문에 각각의 연산을 실현하는 과정을 간결하고 효율적으로 만들 수 있습니다. 이 두 데이터 구조는 또한 매우 널리 사용됩니다.
양이나 소를 위한 나무 또는 대나무 우리
카페테리아의 접시 더미는 스택의 일반적인 예입니다. 스택에서 데이터 항목은 스택의 맨 위 위치에서만 추가하거나 삭제할 수 있습니다. 대기열은 일상 생활에서 흔히 볼 수 있는 시나리오입니다. 서비스 창구 앞에서 서비스를 기다리는 고객들의 줄이 큐를 구성하는 것처럼, 사람들이 줄을 서 있는 것이 큐입니다. 큐에서는 데이터 항목이 한쪽 끝에서 들어오고 다른 쪽 끝에서 나갑니다.
정의: 스택은 한쪽 끝에서만 삽입과 삭제가 가능한 선형 테이블입니다. 삽입과 삭제가 가능한 끝을 스택의 상단이라고 하고, 다른 쪽 끝을 스택의 하단이라고 합니다.
스택 상단에 요소를 삽입하는 것을 스택에 들어가거나 스택을 누르는 것을 스택 진입이라고 하며, 스택 상단에서 요소를 제거하는 것을 스택에서 나가거나 스택에서 뒤로 물러나는 것을 스택 퇴출이라고 합니다.
참고: 스택인 및 스택아웃 작업은 스택의 상단에서만 수행할 수 있으며 실제로 스택의 상단 요소만 볼 수 있고 스택의 상단 아래 모든 요소는 보이지 않으며 상단 이외의 요소에 대한 접근은 허용되지 않습니다.
특성: LIFO
스택 스토리지 및 구현
선형 테이블과 마찬가지로 스택에는 순차 저장과 연쇄 저장이라는 두 가지 주요 저장 방법이 있습니다. 순차 저장 방식은 배열을 사용하여 스택 요소를 저장하므로 순차 스택이 생성됩니다. 연쇄 저장 방식은 연결된 단일 테이블을 사용하여 스택 요소를 저장하므로 연쇄 스택이 생성됩니다.
순차적 스택
순차 스택에서 스택의 요소는 1차원 배열에 저장되며 배열의 아래 첨자가 0인 위치에서 스택의 맨 아래를 정의합니다. 최상위 스택 위치를 표시하는 변수도 있습니다. 최상위 스택 위치는 최상위 스택 포인터라고도 하지만 배열의 아래 첨자일 뿐 실제로는 포인터가 아닙니다.
배열에서 최상위 스택 위치는 정확히 어디를 가리키나요?
하나는 스택의 최상위 요소 바로 옆의 빈 위치에 정의되고, 다른 하나는 스택의 최상위 요소가 위치한 위치에 정의됩니다.
시간 복잡도: 스택 진입 및 퇴출 연산은 스택 상단에서 수행되므로 스택 진입 및 퇴출 시 스택의 기존 요소를 이동할 필요가 없으며, 데이터 이동 시 순차 테이블의 삽입 및 삭제 연산을 피할 수 있습니다. 따라서 순차적 스택 진입 및 퇴출 작업의 시간 복잡도는 O이고, 스택 비어 있음과 스택 가득 찼음을 확인하는 작업의 시간 복잡도는 O입니다.
연쇄 스택
체인 스택은 헤드 위치에서만 작동하는 하나의 연결된 테이블로 생각할 수 있습니다. 헤드 포인터가 가리키는 끝은 스택의 상단으로, 테이블의 끝은 스택의 하단으로 사용됩니다. 들어오는 작업과 나가는 작업 모두 헤드 포인터를 통해 수행할 수 있습니다. 연쇄 스택에서는 헤드 포인터만 정의할 수 있고 테일 포인터와 헤드 노드는 정의하지 않은 상태로 둘 수 있습니다.
시간 복잡도: 수신 및 발신 작업의 시간 복잡도는 순차 스택과 마찬가지로 O입니다.
순차 스택과 연쇄 스택 비교
- 순차 스택은 고정 길이의 1차원 배열을 미리 적용하여 처음부터 끝까지 완전히 채워야 하므로 스택에 요소가 적을 경우 공간을 크게 낭비하게 됩니다.
- 체인 스택은 길이가 가변적이지만 각 요소에는 포인터 필드가 필요하므로 구조적 오버헤드가 발생합니다.
- 두 구현 방식 간에 본질적인 차이는 없습니다. 스택의 최대 요소 수를 미리 예측할 수 없는 경우 연쇄 스택만 사용할 수 있고, 최대 요소 수를 알 수 있는 경우 순차 스택을 사용할 수 있습니다.
- 스택의 스택이 스택 작업에서 스택 작업이 더 자주 발생하면 체인 스택을 사용하면 시스템 기능을 자주 호출하고 노드가 점유 한 공간을 신청하고 해제 할 수 있습니다. 각 노드가 차지하는 공간이 작으면 공간을 여러 번 적용하고 해제하면 메모리에 많은 조각이 생깁니다.
