스택 ADT와 스택 데이터 구조는 동일한가요?

효율적으로 .

데이터 구조는 하나 이상의 특정 추상 데이터 유형 을 구현할 수 있습니다. (ADT)는 운영 계약 및 복잡성

데이터 구조는 ADT에서 제공하는 계약의 구체적인 구현입니다.

의미 :

1. ADT는 사용자 관점에서 추상 표현입니다

2. DS는 구체적 표현이며, 사용자 관점에서 아닙니다

간단히 말하면 :

1. 스택은 ADT 이며 사용자가 사용할 푸시, 팝 등이 있어야 함을 지정합니다.

2. 스택 (대기열과 같은 다른 ADT와 마찬가지로) 는 배열 또는 목록 (연결된 목록 등)

요약 :

스택은 DS가 아니고 ADT이며 다음을 사용하여 구현됩니다. 다른 DS.

도움이 되었기를 바랍니다.

행운을 빕니다

답변

스택

스택은 후입 선출 (LIFO) 원칙에 따라 삽입 및 제거되는 개체의 컨테이너입니다. 푸시 다운 스택에서는 항목을 스택으로 푸시 및 팝 스택에서 항목. 스택은 제한된 액세스 데이터 구조입니다. 요소는 맨 위에서 만 스택에서 추가 및 제거 할 수 있습니다. push 는 항목을 스택 맨 위에 추가하고 pop 은 항목을 맨 위에서 제거합니다. . 유용한 비유는 책 더미를 생각하는 것입니다. 상단 책만 제거 할 수 있으며 상단에 새 책을 추가 할 수도 있습니다.

스택은 재귀 데이터 구조입니다. 다음은 스택의 구조적 정의입니다.

애플리케이션

• 스택을 사용하는 가장 간단한 방법은 단어를 뒤집는 것입니다. 주어진 단어를 한 글자 씩 스택에 밀어 넣은 다음 스택에서 문자를 팝합니다.
• 다른 응용 프로그램은 텍스트 편집기의 “실행 취소”메커니즘입니다. 이 작업은 모든 텍스트 변경 사항을 스택에 유지하여 수행됩니다. 역 추적 . 이것은 일련의 요소에서 가장 최근 데이터 요소에 액세스해야하는 경우의 프로세스입니다. 미로 나 미로를 생각하면 입구에서 출구로가는 길을 어떻게 찾나요? 막 다른 골목에 도달하면 뒤로 물러나야합니다. 하지만 어디로 되돌아 갈까요? 이전 선택 지점으로 이동합니다. 따라서 각 선택 지점에서 가능한 모든 선택 항목을 스택에 저장합니다. 그런 다음 역 추적은 단순히 스택에서 다음 선택 항목을 선택하는 것을 의미합니다.
• 언어 처리 : 매개 변수 및 지역 변수를위한 공간은 내부적으로 stack.compiler의 구문 검사를 사용하여 생성됩니다. 중괄호 일치에 대한 구문 검사는 stack.support를 사용하여 구현됩니다. 재귀 용

구현

표준 클래스 라이브러리에서 데이터 유형 스택은 adapter 클래스 : 스택이 다른 데이터 구조 위에 구축됨을 의미합니다. 스택의 기본 구조는 배열, 벡터, ArrayList, 연결된 목록 또는 기타 컬렉션 기본 데이터 구조의 유형에 관계없이 스택은 동일한 기능을 구현해야합니다.이는 고유 한 인터페이스를 제공하여 달성됩니다.

public interface StackInterface

{

public void push(AnyType e);

public AnyType pop();

public AnyType peek();

public boolean isEmpty();

}

다음 그림은 구성 별 구현 아이디어를 보여줍니다.

위의 인터페이스 외에 다른 구현 요구 사항은 모든 스택 작업이

일정 시간 O (1) 에서 실행되어야한다는 것입니다.

. 일정 시간이란 스택 크기에 관계없이 연산에 k 나노초의 계산 시간이 걸리는 일정한 k가 있음을 의미합니다.

배열 기반 구현