3 개의 스택으로 큐를 구현하는 방법은 무엇입니까?

3 개의 스택으로 큐를 구현하는 방법은 무엇입니까?

---

나는 알고리즘 책 ( Robert Sedgewick과 Kevin Wayne의 Algorithms, 4th Edition) 에서이 질문을 보았습니다.

3 개의 스택이있는 큐 각 대기열 작업이 일정한 수의 스택 작업을 수행하도록 3 개의 스택으로 대기열을 구현하십시오. 경고 : 난이도가 높습니다.

2 스택으로 대기열을 만드는 방법을 알고 있지만 3 스택으로 솔루션을 찾을 수 없습니다. 어떤 아이디어?

(오, 이것은 숙제가 아닙니다 :))

---

요약

• 6 개의 스택으로 알려진 O (1) 알고리즘
• O (1) 알고리즘은 3 개의 스택으로 알려져 있지만 실제로 추가 내부 데이터 구조를 갖는 지연 평가를 사용하므로 솔루션을 구성하지 않습니다.
• Sedgewick 근처의 사람들은 원래 질문의 모든 제약 조건 내에서 3- 스택 솔루션을 인식하지 못한다고 확인했습니다.

세부

이 링크 뒤에는 두 가지 구현이 있습니다. http://www.eecs.usma.edu/webs/people/okasaki/jfp95/index.html

그중 하나는 3 개의 스택이있는 O (1)이지만 지연 실행을 사용하여 실제로 추가 중간 데이터 구조 (클로저)를 만듭니다.

다른 하나는 O (1)이지만 SIX 스택을 사용합니다. 그러나 지연 실행없이 작동합니다.

업데이트 : 오카 사키의 논문은 여기에 있습니다 : http://www.eecs.usma.edu/webs/people/okasaki/jfp95.ps 그리고 그는 게으른 평가가있는 O (1) 버전에 대해 실제로 2 스택 만 사용하는 것으로 보입니다. 문제는 실제로 게으른 평가에 기반한다는 것입니다. 문제는 지연 평가없이 3 스택 알고리즘으로 변환 할 수 있는지입니다.

업데이트 : 또 다른 관련 알고리즘은 컴퓨팅 및 조합에 관한 제 7 차 연례 회의에서 출판 된 Holger Petersen의 논문 "Stacks vs Deques"에 설명되어 있습니다. Google 도서에서 기사를 찾을 수 있습니다. 225-226 페이지를 확인하십시오. 그러나이 알고리즘은 실제로 실시간 시뮬레이션이 아니라 3 개의 스택에서 이중 엔드 큐의 선형 시뮬레이션입니다.

gusbro : "@Leonel이 며칠 전에 말했듯이, Sedgewick 교수가 해결책을 알았거나 어떤 실수가 있었는지 확인하는 것이 공정하다고 생각했습니다. 그래서 나는 그에게 편지를 보냈습니다. 자신을 제외하고는 프린스턴의 동료로부터) 나는 여러분과 공유하고 싶습니다. 그는 기본적으로 그는 3 개의 스택을 사용하는 알고리즘은없고 다른 평가 (게으른 평가를 사용하지 않는 것)를 알고 있다고 알고있었습니다. 우리가 이미 답을보고있는 것으로 알고있는 6 개의 스택입니다. 따라서 알고리즘을 찾기 위해 질문이 아직 열려있는 것 같습니다 (또는 찾을 수 없음을 증명합니다). "

---

좋아, 이것은 정말로 어렵고 내가 얻을 수있는 유일한 해결책은 Kobayashi Maru 테스트에 대한 Kirks 솔루션을 기억합니다 (어쨌든 속임수) : 아이디어는 스택 스택을 사용하고 목록을 모델링하는 데 사용한다는 것입니다 ). 나는 작업을 en / dequeue라고하고 밀어서 팝하면 다음과 같이됩니다.

queue.new() : Stack1 = Stack.new(<Stack>);  
              Stack2 = Stack1;  

enqueue(element): Stack3 = Stack.new(<TypeOf(element)>); 
                  Stack3.push(element); 
                  Stack2.push(Stack3);
                  Stack3 = Stack.new(<Stack>);
                  Stack2.push(Stack3);
                  Stack2 = Stack3;                       

dequeue(): Stack3 = Stack1.pop(); 
           Stack1 = Stack1.pop();
           dequeue() = Stack1.pop()
           Stack1 = Stack3;

isEmtpy(): Stack1.isEmpty();

(StackX = StackY는 내용의 복사가 아니라 참조의 사본 일뿐입니다. 쉽게 설명 할 수 있습니다. 또한 3 개의 스택 배열을 사용하고 인덱스를 통해 액세스 할 수 있습니다. 인덱스 변수의 값만 변경하면됩니다. ). 모든 것은 스택 작업 조건에서 O (1)에 있습니다.

그리고 네, 우리는 3 개 이상의 스택을 암시하기 때문에 논쟁의 여지가 있음을 알고 있지만 다른 사람들에게 좋은 아이디어를 줄 수 있습니다.

편집 : 설명 예 :

 | | | |3| | | |
 | | | |_| | | |
 | | |_____| | |
 | |         | |
 | |   |2|   | |
 | |   |_|   | |
 | |_________| |
 |             |
 |     |1|     |
 |     |_|     |
 |_____________|

Stack1을 보여주기 위해 작은 ASCII 아트로 여기에서 시도했습니다.

모든 요소는 단일 요소 스택으로 래핑됩니다 (따라서 형식이 안전한 스택 스택 만 있음).

You see to remove we first pop the first element (the stack containing here element 1 and 2). Then pop the next element and unwrap there the 1. Afterwards we say that the first poped stack is now our new Stack1. To speak a little more functional - these are lists implement by stacks of 2 elements where the top element ist cdr and the first/below top element is car. The other 2 are helping stacks.

Esp tricky is the inserting, as you have somehow have to dive deep into the nested stacks to add another element. Thats why Stack2 is there. Stack2 is always the innermost stack. Adding is then just pushing an element in and then pushing ontop a new Stack2 (and thats why we are not allowed to touch Stack2 in our dequeue operation).

---

I am going to attempt a proof to show that it can't be done.

---

Suppose there is a queue Q that is simulated by 3 stacks, A, B and C.

Assertions

• ASRT0 := Furthermore, assume that Q can simulate operations {queue,dequeue} in O(1). This means that there exists a specific sequence of stack push/pops for every queue/dequeue operation to be simulated.

• Without loss of generality, assume the queue operations are deterministic.

Let the elements queued into Q be numbered 1, 2, ..., based on their order of queue, with the first element that is queued into Q being defined as 1, the second one as 2, and so on.

Define

• Q(0) := The state of Q when there are 0 elements in Q (and thus 0 elements in A, B and C)
• Q(1) := The state of Q (and A, B and C) after 1 queue operation on Q(0)
• Q(n) := The state of Q (and A, B and C) after n queue operations on Q(0)

Define

• |Q(n)| := the number of elements in Q(n) (therefore |Q(n)| = n)
• A(n) := the state of the stack A when the state of Q is Q(n)
• |A(n)| := the number of elements in A(n)

And similar definitions for stacks B and C.

Trivially,

|Q(n)| = |A(n)| + |B(n)| + |C(n)|

---

|Q(n)| is obviously unbounded on n.

Therefore, at least one of |A(n)|, |B(n)| or |C(n)| is unbounded on n.

WLOG1, suppose stack A is unbounded and stacks B and C are bounded.

Define * B_u := an upper bound of B * C_u := an upper bound of C * K := B_u + C_u + 1

WLOG2, for an n such that |A(n)| > K, select K elements from Q(n). Suppose that 1 of those elements is in A(n + x), for all x >= 0, i.e. the element is always in stack A no matter how many queue operations are done.

• X := that element

Then we can define

• Abv(n) := the number of items in stack A(n) that is above X

• Blo(n) := the number of elements in stack A(n) that is below X

  |A(n)| = Abv(n) + Blo(n)

ASRT1 := The number of pops required to dequeue X from Q(n) is at least Abv(n)

From (ASRT0) and (ASRT1), ASRT2 := Abv(n) must be bounded.

If Abv(n) is unbounded, then if 20 dequeues are required to dequeue X from Q(n), it will require at least Abv(n)/20 pops. Which is unbounded. 20 can be any constant.

Therefore,

ASRT3 := Blo(n) = |A(n)| - Abv(n)

must be unbounded.

---

WLOG3, we can select the K elements from the bottom of A(n), and one of them is in A(n + x) for all x >= 0

X(n) := that element, for any given n

ASRT4 := Abv(n) >= |A(n)| - K

Whenever an element is queued into Q(n)...

WLOG4, suppose B and C are already filled to their upper bounds. Suppose that the upper bound for elements above X(n) has been reached. Then, a new element enters A.

WLOG5, suppose that as a result, the new element must enter below X(n).

ASRT5 := The number of pops required to put an element below X(n) >= Abv(X(n))

From (ASRT4), Abv(n) is unbounded on n.

Therefore, the number of pops required to put an element below X(n) is unbounded.

---

This contradicts ASRT1, therefore, it is not possible to simulate an O(1) queue with 3 stacks.

---

I.e.

At least 1 stack must be unbounded.

For an element that stays in that stack, the number of elements above it must be bounded, or the dequeue operation to remove that element will be unbounded.

However, if the number of elements above it is bounded, then it will reach a limit. At some point, a new element must enter below it.

Since we can always choose the old element from among one of the lowest few elements of that stack, there can be an unbounded number of elements above it (based on the unbounded size of the unbounded stack).

To enter a new element below it, since there's an unbounded number of elements above it, an unbounded number of pops is required to put the new element below it.

And thus the contradiction.

---

There are 5 WLOG (Without loss of generality) statements. In some sense, they can be intuitively understood to be true (but given that they are 5, it might take some time). The formal proof that no generality is lost can be derived, but is extremely lengthy. They're omitted.

I do admit that such omission might leave the WLOG statements in question. With a programmer's paranoia for bugs, please do verify the WLOG statements if you like to.

The third stack is also irrelevant. What matters is that there's a set of bounded stacks, and a set of unbounded stacks. The minimum needed for an example is 2 stacks. The number of stacks must be, of course, finite.

Lastly, if I am right that there's no proof, then there should be an easier inductive proof available. Probably based on what happens after every queue (keep track of how it affects the worst case of dequeue given the set of all elements in the queue).

---

Note: This is meant to be a comment to the functional implementation of real-time ( constant time worst case ) queues with singly-linked-lists. I can't add comments due to reputation, but it'll be nice if someone could change this to a comment appended to the answer by antti.huima. Then again, it is somewhat long for a comment.

@antti.huima: Linked lists are not the same as a stack.

• s1 = (1 2 3 4) --- a linked list with 4 nodes, each pointing to the one on the right, and holding values 1, 2, 3 and 4

• s2 = popped(s1) --- s2 is now (2 3 4)

At this point, s2 is equivalent to popped(s1), which behaves like a stack. However, s1 is still available for reference!

• s3 = popped(popped(s1)) --- s3 is (3 4)

We can still peek into s1 to get 1, whereas in a proper stack implementation, element 1 is gone from s1!

What does this mean?

• s1 is the reference to the top of the stack
• s2 is the reference to the second element of the stack
• s3 is the reference to the third ...

The additional linked-lists created now each serves as a reference/pointer! A finite number of stacks can't do that.

From what I see in the papers/code, the algorithms all make use of this property of linked-lists to retain references.

Edit: I'm referring only to the 2 and 3 linked-list algorithms make use of this property of linked-lists, as I read them first (they looked simpler). This is not meant to show that they are or are not applicable, just to explain that linked-lists aren't necessarily identical. I'll read the one with 6 when I'm free. @Welbog: Thanks for the correction.

---

Laziness can also simulate pointer-functionality in similar ways.

---

Using linked-list solves a different problem. This strategy can be used to implement real-time queues in Lisp (Or at least Lisps that insist on building everything from linked-lists): Refer to "Real Time Queue Operations in Pure Lisp" (linked to through antti.huima's links). It's also a nice way to design immutable lists with O(1) operation time and shared (immutable) structures.

---

You can do it in amortized constant time with two stacks:

------------- --------------
            | |
------------- --------------

Adding is O(1) and removing is O(1) if the side you want to take from is not empty and O(n) otherwise (split the other stack in two).

The trick is to see that the O(n) operation will only be done every O(n) time (if you split, e.g. in halves). Hence, the average time for an operation is O(1)+O(n)/O(n) = O(1).

While this may seam like a problem, if you are using an imperative language with an array based stack (fastest), you are going to have only amortized constant time anyway.

참고URL : https://stackoverflow.com/questions/5538192/how-to-implement-a-queue-with-three-stacks