자바 스택과 큐를 구현하는 방법

Stack and Queue

1. Stack(Stack)은 후입선출(LIFO) 데이터 구조

2. Queue(Queue)는 선입선출(FIFO) 구조

스택(Stack)

스택은 배열에 비해 선형 구조입니다. 스택에 해당하는 작업은 배열의 하위 집합입니다.

한 쪽 끝에서만 요소를 추가하고 한쪽 끝에서 요소를 꺼낼 수 있습니다(이 쪽 끝을 스택의 맨 위라고 함).

스택은 컴퓨터 사용에 있어서 컴파일러의 어휘 분석기, Java 가상 머신, 소프트웨어의 실행 취소(Undo) 작업, 브라우저의 반환 작업 등 널리 사용되는 데이터 구조입니다. 컴파일러 등에서 함수 호출 구현

스택 구현

인터페이스	Description	Complexity
void push(E e)	스택에 요소 추가	O(1) Amortized
E pop()	스택의 최상위 요소를 팝합니다	O(1) Spreadequally
E peek()	스택의 최상위 요소 보기	O(1)
int getSize()	Get 스택의 요소 수	O(1)
boolean isEmpty()	스택이 비어 있는지 확인	O(1)

설명: push 및 팝 작업은 마지막에 수행되며 트리거 크기 조정이 가능하지만 균등하게 분산되는 것은 O(1)입니다.
시간 복잡도 분석에 대해 더 알고 싶다면 저자가 나중에 업데이트할 글을 주목해 주세요. O(n)은 어떤 문제를 설명하나요?

스택의 구현은 배열이나 연결리스트를 통해 구현할 수 있습니다. 여기서는 배열을 사용하여 위의 인터페이스를 구현합니다.

스택 설계에서 사용자는 최상위 요소 액세스 및 스택 길이에만 주의하므로 설계 코드는 다음과 같습니다.

독자는 스택 이 데이터 구조를 사용하여 문제를 해결할 수 있습니다. . 20 on LeetCode: 유효한 괄호는 일일 개수: 유효한 괄호를 참조하세요.

Queue

Queue는 배열과 비교할 때 선형 데이터 구조이기도 하며, 대기열에 해당하는 작업은 배열의 하위 집합입니다.

요소는 한쪽 끝(큐의 끝)에서만 추가할 수 있고, 다른 쪽 끝(큐의 헤드)에서만 요소를 꺼낼 수 있습니다.

큐의 적용은 플레이어의 재생 목록, 데이터 흐름 개체, 비동기 데이터 전송 구조(파일 IO, 파이프 통신, 소켓 등)에 반영될 수 있습니다. 물론 가장 직관적인 것은 큐입니다.

큐 구현

Interface	Description	Complexity
void enqueue(E e)	Enqueue	O(1) 균등 공유
E 대기열에서 제거( )	Dequeue	O(n)
E getFront()	큐의 첫 번째 요소 가져오기	O(1)
int getSize()	큐 요소 수 가져오기	O( 1)
boolean isEmpty()	큐가 비어 있는지 확인	O(1)

큐에 들어가는 것은 큐의 끝에서부터 시작되며 크기 조정이 트리거될 수 있으므로 평균은 O(1)입니다. 대기열 제거는 대기열의 선두에 있으며 배열 구현에서는 매번 모든 요소를 ​​O(n)으로 이동해야 합니다.

위 내용은 자바 스택과 큐를 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!