비슷한 질문은 이전 질문을 받았다 가 , 그러나 여기에서 문제는 스택으로 두 개의 큐를 사용하여, 그것의 반대입니다. 질문…
자신의 표준 운영과 두 개의 큐를 감안할 때 ( enqueue, dequeue, isempty, size), 표준 운영과 스택을 구현 ( pop, push, isempty, size).
솔루션 에는 두 가지 버전 이 있어야합니다 .
- 버전 A : 아이템을 밀 때 스택이 효율적이어야합니다. 과
- 버전 B : 아이템을 쓸 때 스택이 효율적이어야합니다.
특정 언어 구현보다 알고리즘에 관심이 있습니다. 그러나 친숙한 언어로 표현 된 솔루션을 환영합니다.자바,씨#,파이썬,vb,자바 스크립트,PHP).
답변
버전 A (효율적인 푸시) :
- 푸시:
- queue1에 넣다
- 팝:
- queue1의 크기가 1보다 큰 동안 큐에서 대기 한 항목을 queue1에서 queue2로 파이프
- queue1의 마지막 항목을 대기열에서 빼고 반환 한 다음 queue1과 queue2의 이름을 전환하십시오.
버전 B (효율적인 팝) :
- 푸시:
- queue2에 넣다
- queue2의 모든 queue1 항목을 대기열에 넣은 다음 queue1 및 queue2의 이름을 전환하십시오.
- 팝:
- queue1에서 deqeue
답변
이 작업을 수행하는 가장 쉬운 방법은 새 요소를 빈 대기열로 푸시 한 다음 다른 요소를 대기열에서 빼고 이전의 빈 대기열로 대기열에 넣는 것입니다. 이 방법으로 최신은 항상 대기열의 맨 앞에 있습니다. 이것은 버전 B입니다. 버전 A의 경우 마지막 큐를 제외하고 요소를 두 번째 큐로 큐에서 빼서 프로세스를 반대로합니다.
0 단계 :
"Stack"
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
1 단계:
"Stack"
+---+---+---+---+---+
| 1 | | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 1 | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
2 단계:
"Stack"
+---+---+---+---+---+
| 2 | 1 | | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | 2 | 1 | | | |
+---+---+---+---+---+ +---+---+---+---+---+
3 단계 :
"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 | | |
+---+---+---+---+---+
Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 3 | 2 | 1 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
답변
하나의 대기열 로이 작업을 수행 할 수 있습니다.
푸시:
- 새로운 요소를 큐에 넣습니다.
n큐의 요소 수인 경우 요소n-1시간 을 제거하고 삽입하십시오 .
팝:
- 대기열에서 빼다
.
push 1
front
+----+----+----+----+----+----+
| 1 | | | | | | insert 1
+----+----+----+----+----+----+
push2
front
+----+----+----+----+----+----+
| 1 | 2 | | | | | insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | 2 | 1 | | | | remove and insert 1
+----+----+----+----+----+----+
insert 3
front
+----+----+----+----+----+----+
| | 2 | 1 | 3 | | | insert 3
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | 1 | 3 | 2 | | remove and insert 2
+----+----+----+----+----+----+
front
+----+----+----+----+----+----+
| | | | 3 | 2 | 1 | remove and insert 1
+----+----+----+----+----+----+
샘플 구현 :
int stack_pop (queue_data *q)
{
return queue_remove (q);
}
void stack_push (queue_data *q, int val)
{
int old_count = queue_get_element_count (q), i;
queue_insert (q, val);
for (i=0; i<old_count; i++)
{
queue_insert (q, queue_remove (q));
}
}
답변
import java.util.*;
/**
*
* @author Mahmood
*/
public class StackImplUsingQueues {
Queue<Integer> q1 = new LinkedList<Integer>();
Queue<Integer> q2 = new LinkedList<Integer>();
public int pop() {
if (q1.peek() == null) {
System.out.println("The stack is empty, nothing to return");
int i = 0;
return i;
} else {
int pop = q1.remove();
return pop;
}
}
public void push(int data) {
if (q1.peek() == null) {
q1.add(data);
} else {
for (int i = q1.size(); i > 0; i--) {
q2.add(q1.remove());
}
q1.add(data);
for (int j = q2.size(); j > 0; j--) {
q1.add(q2.remove());
}
}
}
public static void main(String[] args) {
StackImplUsingQueues s1 = new StackImplUsingQueues();
// Stack s1 = new Stack();
s1.push(1);
s1.push(2);
s1.push(3);
s1.push(4);
s1.push(5);
s1.push(6);
s1.push(7);
s1.push(8);
s1.push(9);
s1.push(10);
// s1.push(6);
System.out.println("1st = " + s1.pop());
System.out.println("2nd = " + s1.pop());
System.out.println("3rd = " + s1.pop());
System.out.println("4th = " + s1.pop());
System.out.println("5th = " + s1.pop());
System.out.println("6th = " + s1.pop());
System.out.println("7th = " + s1.pop());
System.out.println("8th = " + s1.pop());
System.out.println("9th = " + s1.pop());
System.out.println("10th= " + s1.pop());
}
}
답변
하나의 대기열을 사용하여 스택을 구현할 수 있습니까? 두 개의 대기열을 사용할 수 있지만 단일 대기열을 고려하는 것이 더 효율적입니다. 코드는 다음과 같습니다.
public void Push(T val)
{
queLower.Enqueue(val);
}
public T Pop()
{
if (queLower.Count == 0 )
{
Console.Write("Stack is empty!");
return default(T);
}
if (queLower.Count > 0)
{
for (int i = 0; i < queLower.Count - 1;i++ )
{
queLower.Enqueue(queLower.Dequeue ());
}
}
return queLower.Dequeue();
}
답변
queue<int> q1, q2;
int i = 0;
void push(int v) {
if( q1.empty() && q2.empty() ) {
q1.push(v);
i = 0;
}
else {
if( i == 0 ) {
while( !q1.empty() ) q2.push(q1.pop());
q1.push(v);
i = 1-i;
}
else {
while( !q2.empty() ) q1.push(q2.pop());
q2.push(v);
i = 1-i;
}
}
}
int pop() {
if( q1.empty() && q2.empty() ) return -1;
if( i == 1 ) {
if( !q1.empty() )
return q1.pop();
else if( !q2.empty() )
return q2.pop();
}
else {
if( !q2.empty() )
return q2.pop();
else if( !q1.empty() )
return q1.pop();
}
}
답변
내 대답은 ‘팝’이 비효율적 인 곳입니다. 즉시 생각 나는 모든 알고리즘에는 N 복잡성이 있습니다. 여기서 N은 목록의 크기입니다. ‘팝’에 대한 작업을 선택하든 ‘푸시’에 대한 작업을 선택하든
크기를 계산할 필요가 없기 때문에 목록을 다시 교환하고 네 번째로 교환하는 알고리즘이 더 나을 수 있습니다. 빈과 비교하고 반복해야합니다.
큐의 마지막 요소에 대한 정보는 큐의 크기를 알아야만 사용할 수 있으며 해당 요소에 도달하기 위해 데이터를 삭제해야하므로 두 번째 큐에이 알고리즘을 N보다 빠르게 작성할 수 없음을 증명할 수 있습니다. .
이를보다 빠르게하는 유일한 방법은 우선 대기열을 사용하지 않는 것입니다.
from data_structures import queue
class stack(object):
def __init__(self):
q1= queue
q2= queue #only contains one item at most. a temp var. (bad?)
def push(self, item):
q1.enque(item) #just stick it in the first queue.
#Pop is inefficient
def pop(self):
#'spin' the queues until q1 is ready to pop the right value.
for N 0 to self.size-1
q2.enqueue(q1.dequeue)
q1.enqueue(q2.dequeue)
return q1.dequeue()
@property
def size(self):
return q1.size + q2.size
@property
def isempty(self):
if self.size > 0:
return True
else
return False
