다음과 같은 숙제가 있습니다.
두 개의 큐를 사용하여 스택 메소드 push (x) 및 pop ()을 구현하십시오.
이것은 나에게 이상하게 보입니다.
- 스택 은 (LIFO) 대기열입니다
- 구현하기 위해 두 개의 대기열이 필요한 이유를 모르겠습니다.
나는 주변을 검색했다 :
몇 가지 해결책을 찾았습니다. 이것이 내가 끝낸 것입니다.
public class Stack<T> {
LinkedList<T> q1 = new LinkedList<T>();
LinkedList<T> q2 = new LinkedList<T>();
public void push(T t) {
q1.addFirst(t);
}
public T pop() {
if (q1.isEmpty()) {
throw new RuntimeException(
"Can't pop from an empty stack!");
}
while(q1.size() > 1) {
q2.addFirst( q1.removeLast() );
}
T popped = q1.pop();
LinkedList<T> tempQ = q1;
q1 = q2;
q2 = tempQ;
return popped;
}
}
그러나 단일 대기열을 사용하는 것의 이점이 무엇인지 이해하지 못합니다. 두 대기열 버전은 무의미하게 복잡해 보입니다.
우리가 푸시를 2보다 효율적으로 선택하고 (위에서 한 것처럼) push동일하게 유지하고 pop단순히 마지막 요소를 반복하고 반환해야한다고 가정 해보십시오. 두 경우 모두는 push것 O(1), 그리고이 pop될 것이다 O(n); 그러나 단일 대기열 버전은 훨씬 간단합니다. 단일 for 루프 만 필요합니다.
뭔가 빠졌습니까? 여기에 대한 통찰력이 있으면 감사하겠습니다.
답변
장점은 없습니다 : 순전히 학업입니다.
매우 내가 신입생이 대학에있을 때 오래 전에 나는 유사한 운동했다 1 . for루프 카운터가있는 루프를 사용하여 반복 솔루션을 작성하는 대신 객체 지향 프로그래밍을 사용하여 알고리즘을 구현하는 방법을 학생들에게 가르치는 것이 목표였습니다 . 대신 기존 데이터 구조를 결합하고 재사용하여 목표를 달성하십시오.
Real World TM 에서는이 코드를 사용하지 않습니다 . 이 연습에서 제거해야 할 것은 “상자 밖에서 생각하고”코드를 재사용하는 방법입니다.
구현을 직접 사용하는 대신 코드에서 java.util.Queue 인터페이스 를 사용해야 합니다 .
Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();
이를 통해 Queue원하는 경우 다른 구현 을 사용할 수 있을뿐만 아니라 인터페이스 의 정신을 극복 할 수 있는 2 개의 메소드를 숨길 LinkedList수 Queue있습니다. 여기에는 get(int)과 pop()(코드를 컴파일하는 동안 할당의 제약이 주어진에서, 논리 오류가 있습니다. 귀하의 변수를 선언하는 Queue대신에 LinkedList그것을 발표 할 예정이다). 관련 읽기 : “인터페이스 프로그래밍”이해 및 인터페이스가 유용한 이유는 무엇입니까?
1 여전히 기억합니다. 연습은 Stack 인터페이스의 메소드 만 사용 하고 java.util.Collections다른 “정적 전용”유틸리티 클래스 에는 유틸리티 메소드를 사용하지 않고 Stack 을 되 돌리는 것이 었습니다 . 올바른 솔루션은 다른 데이터 구조를 임시 보유 객체로 사용하는 것입니다. 다른 데이터 구조, 해당 속성 및이를 결합하는 방법을 알아야합니다. 이전에 프로그래밍 한 적이없는 대부분의 CS101 클래스를 발견했습니다.
2 메소드는 여전히 있지만 유형 캐스트 나 리플렉션이 없으면 액세스 할 수 없습니다. 따라서 이러한 비큐 방법을 사용하는 것은 쉽지 않습니다 .
답변
이점이 없습니다. 대기열을 사용하여 스택을 구현하면 시간이 엄청나게 복잡해집니다. (유능한) 프로그래머는“실제 생활”에서 이와 같은 일을하지 않을 것입니다.
그러나 가능합니다. 하나의 추상화를 사용하여 다른 추상화를 구현할 수 있으며 그 반대도 가능합니다. 스택은 두 개의 대기열 측면에서 구현 될 수 있으며, 마찬가지로 두 개의 스택 측면에서 대기열을 구현할 수 있습니다. 이 연습 의 장점은 다음과 같습니다 .
- 당신은 스택을 요약
- 당신은 대기열을 요약
- 알고리즘 사고에 익숙해집니다
- 스택 관련 알고리즘을 배웁니다.
- 알고리즘의 트레이드 오프에 대해 생각하게됩니다.
- 대기열과 스택의 동등성을 실현함으로써 코스의 다양한 주제를 연결합니다
- 실용적인 프로그래밍 경험을 얻습니다
실제로 이것은 훌륭한 운동입니다. 나는 지금 스스로해야한다 🙂
답변
두 개의 스택으로 큐를 만드는 실제적인 목적이 있습니다. 기능적 언어에서 변경 불가능한 데이터 구조를 사용하는 경우 푸시 가능한 항목의 스택으로 푸시하고 팝업 가능한 항목 목록에서 가져올 수 있습니다. 팝 가능한 아이템은 모든 아이템이 튀어 나왔을 때 생성되며, 새로운 팝 가능한 스택은 푸시 가능한 스택의 반대이며, 이제 새로운 푸시 가능한 스택은 비어 있습니다. 효율적입니다.
두 개의 대기열로 구성된 스택은? 크고 빠른 대기열을 사용할 수있는 상황에서는 의미가있을 수 있습니다. 이런 종류의 자바 연습으로는 확실히 쓸모가 없습니다. 그러나 이것이 채널 또는 메시징 큐인 경우에는 의미가 있습니다. (즉 : 앞의 (N-1) 항목을 새 대기열로 이동하기 위해 O (1) 작업으로 N 개의 메시지가 대기열에 추가되었습니다.)
답변
운동 은 실질적인 관점에서 불필요하게 고안되었습니다. 요점은 스택을 구현하기 위해 영리한 방식으로 큐의 인터페이스를 사용하도록하는 것입니다. 예를 들어 “One queue”솔루션을 사용하려면 스택 “pop”작업의 마지막 입력 값을 얻기 위해 큐를 반복해야합니다. 그러나 큐 데이터 구조는 값을 반복 할 수 없으므로 선입 선출 (FIFO)로 값에 액세스하도록 제한됩니다.
답변
다른 사람들이 이미 언급했듯이 실제 이점은 없습니다.
어쨌든, 질문의 두 번째 부분에 대한 하나의 대답, 단순히 하나의 큐를 사용하지 않는 이유는 Java를 넘어서는 것입니다.
Java에서도 Queue인터페이스에는 size()메소드 가 있으며 해당 메소드의 모든 표준 구현은 O (1)입니다.
C / C ++ 프로그래머가 구현할 때 순진 / 정식 연결 목록에 반드시 해당되는 것은 아니며, 첫 번째 요소와 마지막 요소에 대한 포인터를 유지하고 각 요소는 다음 요소에 대한 포인터를 유지합니다.
이 경우 size()O (n)이며 루프에서는 피해야합니다. 아니면 구현이 불투명 만 최소한을 제공 add()하고 remove().
이러한 구현을 통해 먼저 요소 수를 두 번째 큐로 전송하여 요소 수를 세고 요소를 첫 번째 큐로 n-1다시 전송 한 다음 나머지 요소를 반환해야합니다.
즉, Java-land에 살면 아마도 이와 같은 것을 구성하지 않을 것입니다.
답변
그러한 구현에 대한 사용을 상상하기는 어렵지만 사실입니다. 그러나 대부분의 요점은 그것이 가능하다는 것을 증명하는 것 입니다.
그러나 이러한 것들에 대한 실제 사용의 관점에서, 나는 두 가지를 생각할 수 있습니다. 이를 위해 한 가지 용도는이를 위해 설계되지 않은 제한된 환경에서 시스템을 구현하는 것입니다 . 예를 들어, Minecraft의 레드 스톤 블록 은 사람들이 로직 회로 및 전체 CPU를 구현하는 데 사용되는 Turing-complete 시스템을 나타냅니다. 스크립트 기반 게임의 초기에는 많은 최초의 게임 봇도 이런 식으로 구현되었습니다.
그러나이 원칙을 반대로 적용하여 원하지 않는 시스템 에서는 불가능한 것을 보장 할 수 있습니다 . 예를 들어 강력한 구성 시스템은 자산이 될 수 있지만 여전히 사용자에게 제공하지 않을 정도의 전력이 있습니다. 이로 인해 공격자가 구성 언어를 훼손하지 않도록 구성 언어로 할 수있는 작업이 제한되지만이 경우에는 원하는 것입니다.