entityMap|blocks|key|5nskl|text|版本A(高效推送)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3419s|推送：|unordered-list-item|3lvpp|在queue1中入队|5lnaq|​|9to0u|流行：|e3d6l|当queue1的大小大于1时，将从queue1出列的项目输送到queue2|dre70|出列并返回queue1的最后一项，然后切换queue1和queue2的名称|7nrp5|bjb8o|版本B(高效pop)：|et6ca|46no5|在queue2中入队|fmfbb|将queue1的所有项都放入queue2中，然后切换queue1和queue2的名称|fkbg3|80rf|auibc|从queue1排队|h5sm^0|0|0|0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|12|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|13|9|@]|A|@]|B|$]]|$2|F|4|G|6|7|8|14|9|@]|A|@]|B|$]]|$2|H|4|I|6|7|8|15|9|@]|A|@]|B|$]]|$2|J|4|K|6|E|8|16|9|@]|A|@]|B|$]]|$2|L|4|M|6|7|8|17|9|@]|A|@]|B|$]]|$2|N|4|O|6|7|8|18|9|@]|A|@]|B|$]]|$2|P|4|I|6|7|8|19|9|@]|A|@]|B|$]]|$2|Q|4|R|6|7|8|1A|9|@]|A|@]|B|$]]|$2|S|4|D|6|E|8|1B|9|@]|A|@]|B|$]]|$2|T|4|U|6|7|8|1C|9|@]|A|@]|B|$]]|$2|V|4|W|6|7|8|1D|9|@]|A|@]|B|$]]|$2|X|4|I|6|7|8|1E|9|@]|A|@]|B|$]]|$2|Y|4|K|6|E|8|1F|9|@]|A|@]|B|$]]|$2|Z|4|10|6|7|8|1G|9|@]|A|@]|B|$]]|$2|11|4|I|6|7|8|1H|9|@]|A|@]|B|$]]]]

Version A (efficient push):

<ul>
<li>push: 

<ul>
<li>enqueue in queue1</li>
</ul></li>
<li>pop:

<ul>
<li>while size of queue1 is bigger than 1, pipe dequeued items from queue1 into queue2</li>
<li>dequeue and return the last item of queue1, then switch the names of queue1 and queue2</li>
</ul></li>
</ul>

Version B (efficient pop):

<ul>
<li>push:

<ul>
<li>enqueue in queue2</li>
<li>enqueue all items of queue1 in queue2, then switch the names of queue1 and queue2</li>
</ul></li>
<li>pop:

<ul>
<li>deqeue from queue1</li>
</ul></li>
</ul>

entityMap|blocks|key|904gq|text|最简单(也可能是唯一的)方法是将新元素推入空队列，然后将另一个元素从队列中取出，并将其排入先前的空队列中。通过这种方式，最新的总是排在队列的前面。这将是版本B，对于版本A，您只需通过将除最后一个以外的元素出列到第二个队列中来逆转该过程。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|8d8aa|步骤0：|empt7|"Stack"
%2B---%2B---%2B---%2B---%2B---%2B
%7C+++%7C+++%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B

Queue+A++++++++++++++++Queue+B
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B
%7C+++%7C+++%7C+++%7C+++%7C+++%7C++%7C+++%7C+++%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B|code-block|syntax|javascript|16l15|步骤1：|9cqc9|"Stack"
%2B---%2B---%2B---%2B---%2B---%2B
%7C+1+%7C+++%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B

Queue+A++++++++++++++++Queue+B
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B
%7C+1+%7C+++%7C+++%7C+++%7C+++%7C++%7C+++%7C+++%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B|es7uf|步骤2：|806bc|"Stack"
%2B---%2B---%2B---%2B---%2B---%2B
%7C+2+%7C+1+%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B

Queue+A++++++++++++++++Queue+B
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B
%7C+++%7C+++%7C+++%7C+++%7C+++%7C++%7C+2+%7C+1+%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B|9kj4l|步骤3：|2j6bv|"Stack"
%2B---%2B---%2B---%2B---%2B---%2B
%7C+3+%7C+2+%7C+1+%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B

Queue+A++++++++++++++++Queue+B
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B
%7C+3+%7C+2+%7C+1+%7C+++%7C+++%7C++%7C+++%7C+++%7C+++%7C+++%7C+++%7C
%2B---%2B---%2B---%2B---%2B---%2B++%2B---%2B---%2B---%2B---%2B---%2B^0|0|0|0|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|V|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|W|9|@]|A|@]|B|$]]|$2|E|4|F|6|G|8|X|9|@]|A|@]|B|$H|I]]|$2|J|4|K|6|7|8|Y|9|@]|A|@]|B|$]]|$2|L|4|M|6|G|8|Z|9|@]|A|@]|B|$H|I]]|$2|N|4|O|6|7|8|10|9|@]|A|@]|B|$]]|$2|P|4|Q|6|G|8|11|9|@]|A|@]|B|$H|I]]|$2|R|4|S|6|7|8|12|9|@]|A|@]|B|$]]|$2|T|4|U|6|G|8|13|9|@]|A|@]|B|$H|I]]]]

The easiest (and maybe only) way of doing this is by pushing new elements into the empty queue, and then dequeuing the other and enqeuing into the previously empty queue. With this way the latest is always at the front of the queue. This would be version B, for version A you just reverse the process by dequeuing the elements into the second queue except for the last one.

Step 0:

<pre><code>"Stack"
+---+---+---+---+---+
| | | | | |
+---+---+---+---+---+

Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
</code></pre>

Step 1:

<pre><code>"Stack"
+---+---+---+---+---+
| 1 | | | | |
+---+---+---+---+---+

Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 1 | | | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
</code></pre>

Step 2:

<pre><code>"Stack"
+---+---+---+---+---+
| 2 | 1 | | | |
+---+---+---+---+---+

Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| | | | | | | 2 | 1 | | | |
+---+---+---+---+---+ +---+---+---+---+---+
</code></pre>

Step 3:

<pre><code>"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 | | |
+---+---+---+---+---+

Queue A Queue B
+---+---+---+---+---+ +---+---+---+---+---+
| 3 | 2 | 1 | | | | | | | | |
+---+---+---+---+---+ +---+---+---+---+---+
</code></pre>

entityMap|blocks|key|ats91|text|这是我的答案--“流行”是低效的。似乎所有立即浮现在脑海中的算法都有N个复杂度，其中N是列表的大小:无论你是选择在“pop”上做工作还是在“推”上做工作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|e5nvc|交换列表和第四个列表的算法可能会更好，因为不需要计算大小，尽管您仍然需要循环并与empty进行比较。|e1or1|你可以通过注意到队列中最后一个元素的信息只能通过知道队列的大小来获得，并且你必须销毁数据才能到达那个元素，因此第二个队列，你可以证明这个算法不能比N更快。|72ouh|让这个过程变得更快的唯一方法就是一开始就不使用队列。|6q6n2|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+%2B+q2.size

++++@property
++++def+isempty(self):
++++++++if+self.size+>+0:
+++++++++++return+True
++++++++else
+++++++++++return+False|code-block|syntax|javascript^0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|N|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|O|9|@]|A|@]|B|$]]|$2|E|4|F|6|7|8|P|9|@]|A|@]|B|$]]|$2|G|4|H|6|7|8|Q|9|@]|A|@]|B|$]]|$2|I|4|J|6|K|8|R|9|@]|A|@]|B|$L|M]]]]

Here's my answer - where the 'pop' is inefficient.
Seems that all algorithms that come immediately to mind have N complexity, where N is the size of the list: whether you choose to do work on the 'pop' or do work on the 'push'

The algorithm where lists are traded back and fourth may be better, 
 as a size calculation is not needed, although you still need to loop and compare with empty.

you can prove this algorithm cannot be written faster than N by noting that the information about the last element in a queue is only available through knowing the size of the queue, and that you must destroy data to get to that element, hence the 2nd queue.

The only way to make this faster is to not to use queues in the first place.

<pre><code>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 &gt; 0:
 return True
 else
 return False
</code></pre>

entityMap|blocks|key|8kub1|text|import+java.util.*;

/**
+*
+*+@author+Mahmood
+*/
public+class+StackImplUsingQueues+{

++++Queue+q1+=+new+LinkedList();
++++Queue+q2+=+new+LinkedList();

++++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+=+"+%2B+s1.pop());
++++++++System.out.println("2nd+=+"+%2B+s1.pop());
++++++++System.out.println("3rd+=+"+%2B+s1.pop());
++++++++System.out.println("4th+=+"+%2B+s1.pop());
++++++++System.out.println("5th+=+"+%2B+s1.pop());
++++++++System.out.println("6th+=+"+%2B+s1.pop());
++++++++System.out.println("7th+=+"+%2B+s1.pop());
++++++++System.out.println("8th+=+"+%2B+s1.pop());
++++++++System.out.println("9th+=+"+%2B+s1.pop());
++++++++System.out.println("10th=+"+%2B+s1.pop());
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>import java.util.*;

/**
 *
 * @author Mahmood
 */
public class StackImplUsingQueues {

 Queue&lt;Integer&gt; q1 = new LinkedList&lt;Integer&gt;();
 Queue&lt;Integer&gt; q2 = new LinkedList&lt;Integer&gt;();

 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 &gt; 0; i--) {
 q2.add(q1.remove());
 }
 q1.add(data);
 for (int j = q2.size(); j &gt; 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());
 }
}
</code></pre>

entityMap|blocks|key|6s74d|text|如前所述，单个队列不就可以做到这一点吗？它可能不太实用，但有点圆滑。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|6kkjg|push(x):
enqueue(x)
for(queueSize+-+1)
+++enqueue(dequeue())

pop(x):
dequeue()|code-block|syntax|javascript^0|0^^$0|$]|1|@$2|3|4|5|6|7|8|H|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|I|9|@]|A|@]|B|$F|G]]]]

As has been mentioned, wouldn't a single queue do the trick? It's probably less practical but is a bit slicker.

<pre><code>push(x):
enqueue(x)
for(queueSize - 1)
 enqueue(dequeue())

pop(x):
dequeue()
</code></pre>

entityMap|blocks|key|2tbsi|text|queue+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();
+++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>queue&lt;int&gt; q1, q2;
int i = 0;

void push(int v) {
 if( q1.empty() &amp;&amp; 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() &amp;&amp; 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();
 }
}
</code></pre>

entityMap|blocks|key|14t2k|text|我们可以只使用一个队列来实现堆栈吗？我可以使用两个队列，但考虑单个队列会更有效率。代码如下：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|a7v7b|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%2B%2B+)
++++++++++++{
++++++++++++++++queLower.Enqueue(queLower.Dequeue+());
+++++++++++}
++++++++++++++++++++}

++++++++return+queLower.Dequeue();

++++}|code-block|syntax|javascript^0|0^^$0|$]|1|@$2|3|4|5|6|7|8|H|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|I|9|@]|A|@]|B|$F|G]]]]

Can we just use one queue to implement a stack? I can use two queues, but considering single queue would be more efficient. Here is the code:

<pre><code> 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 &gt; 0)
 {
 for (int i = 0; i &lt; queLower.Count - 1;i++ )
 {
 queLower.Enqueue(queLower.Dequeue ());
 }
 }

 return queLower.Dequeue();

 }
</code></pre>

entityMap|blocks|key|7jf0m|text|我们可以用一个队列做到这一点：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|10u0h|推送：|2t8na|将新元素入队。|ordered-list-item|gip5|如果n是队列中元素的数量，然后删除并插入元素n-1时间。|offset|length|style|CODE|bl703|流行：|2ev7s|出队。|767n6|push+1


front+++++++++++++++++++++
%2B----%2B----%2B----%2B----%2B----%2B----%2B
%7C+1++%7C++++%7C++++%7C++++%7C++++%7C++++%7C++++insert+1
%2B----%2B----%2B----%2B----%2B----%2B----%2B


push2

front+++++++++++++++++++++
%2B----%2B----%2B----%2B----%2B----%2B----%2B
%7C+1++%7C+2++%7C++++%7C++++%7C++++%7C++++%7C++++insert+2
%2B----%2B----%2B----%2B----%2B----%2B----%2B

+++++front+++++++++++++++++++++
%2B----%2B----%2B----%2B----%2B----%2B----%2B
%7C++++%7C+2++%7C++1+%7C++++%7C++++%7C++++%7C++++remove+and+insert+1
%2B----%2B----%2B----%2B----%2B----%2B----%2B




+insert+3


++++++front+++++++++++++++++++++
%2B----%2B----%2B----%2B----%2B----%2B----%2B
%7C++++%7C+2++%7C++1+%7C++3+%7C++++%7C++++%7C++++insert+3
%2B----%2B----%2B----%2B----%2B----%2B----%2B

+++++++++++front+++++++++++++++++++++
%2B----%2B----%2B----%2B----%2B----%2B----%2B
%7C++++%7C++++%7C++1+%7C++3+%7C++2+%7C++++%7C++++remove+and+insert+2
%2B----%2B----%2B----%2B----%2B----%2B----%2B

++++++++++++++++front+++++++++++++++++++++
%2B----%2B----%2B----%2B----%2B----%2B----%2B
%7C++++%7C++++%7C++++%7C++3+%7C++2+%7C++1+%7C++++remove+and+insert+1
%2B----%2B----%2B----%2B----%2B----%2B----%2B|code-block|syntax|javascript|7v0a2|示例实现：|b5ce1|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^0|0|0|0|2|1|M|3|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|10|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|11|9|@]|A|@]|B|$]]|$2|E|4|F|6|G|8|12|9|@]|A|@]|B|$]]|$2|H|4|I|6|G|8|13|9|@$J|14|K|15|L|M]|$J|16|K|17|L|M]]|A|@]|B|$]]|$2|N|4|O|6|7|8|18|9|@]|A|@]|B|$]]|$2|P|4|Q|6|G|8|19|9|@]|A|@]|B|$]]|$2|R|4|S|6|T|8|1A|9|@]|A|@]|B|$U|V]]|$2|W|4|X|6|7|8|1B|9|@]|A|@]|B|$]]|$2|Y|4|Z|6|T|8|1C|9|@]|A|@]|B|$U|V]]]]

We can do this with one queue:

push:

<ol>
<li>enqueue new element.</li>
<li>If <code>n</code> is the number of elements in the queue, then remove and insert element <code>n-1</code> times.</li>
</ol>

pop:

<ol>
<li>dequeue</li>
</ol>

.

<pre><code>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
+----+----+----+----+----+----+
</code></pre>

Sample implementation:

<pre><code>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&lt;old_count; i++)
 {
 queue_insert (q, queue_remove (q));
 }
}
</code></pre>

entityMap|blocks|key|epcls|text|这里还有一个解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|ouiq|对于推送：-Add队列1中的第一个元素。-When添加第二个元素，依此类推，首先将队列2中的元素排队，然后将队列1中的所有元素复制到queue2中。-for+POP只是从您插入的最后一个元素的队列中将该元素出队。|86k1v|所以，|bc1b9|public+void+push(int+data){
if+(queue1.isEmpty()){
++++queue1.enqueue(data);
}++else+{
queue2.enqueue(data);
while(!queue1.isEmpty())
Queue2.enqueue(queue1.dequeue());
//EXCHANGE+THE+NAMES+OF+QUEUE+1+and+QUEUE2|code-block|syntax|javascript|995rt|}}|7uv3f|public+int+pop(){
int+popItem=queue2.dequeue();
return+popItem;
}'|fb5dj|有一个问题，我想不通，如何重命名队列？^0|0|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|R|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|S|9|@]|A|@]|B|$]]|$2|E|4|F|6|7|8|T|9|@]|A|@]|B|$]]|$2|G|4|H|6|I|8|U|9|@]|A|@]|B|$J|K]]|$2|L|4|M|6|7|8|V|9|@]|A|@]|B|$]]|$2|N|4|O|6|I|8|W|9|@]|A|@]|B|$J|K]]|$2|P|4|Q|6|7|8|X|9|@]|A|@]|B|$]]]]

Here's one more solution: 

for PUSH : 
-Add first element in queue 1.
-When adding second element and so on,
 Enqueue the element in queue 2 first and then copy all the element from queue 1 to queue2. 
-for POP just dequeue the element from the queue from you inserted the last element. 

So, 

<pre><code>public void push(int data){
if (queue1.isEmpty()){
 queue1.enqueue(data);
} else {
queue2.enqueue(data);
while(!queue1.isEmpty())
Queue2.enqueue(queue1.dequeue());
//EXCHANGE THE NAMES OF QUEUE 1 and QUEUE2
</code></pre>

}
 }

<pre><code>public int pop(){
int popItem=queue2.dequeue();
return popItem;
}'
</code></pre>

There is one problem, I am not able to figure out, how to rename the queues???

entityMap|blocks|key|6ukkl|text|这是我的解决方案，在平均情况下适用于O(1)。有两个队列：in和out。参见下面的伪代码：|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|9vh9s|PUSH(X)+=+in.enqueue(X)

POP:+X+=
++if+(out.isEmpty+and+!in.isEmpty)
++++DUMP(in,+out)
++return+out.dequeue

DUMP(A,+B)+=
++if+(!A.isEmpty)
++++x+=+A.dequeue()
++++DUMP(A,+B)
++++B.enqueue(x)|code-block|syntax|javascript^0|T|2|W|3|0^^$0|$]|1|@$2|3|4|5|6|7|8|L|9|@$A|M|B|N|C|D]|$A|O|B|P|C|D]]|E|@]|F|$]]|$2|G|4|H|6|I|8|Q|9|@]|E|@]|F|$J|K]]]]

Here is my solution that works for O(1) in average case. There are two queues: <code>in</code> and <code>out</code>. See pseudocode bellow:

<pre><code>PUSH(X) = in.enqueue(X)

POP: X =
 if (out.isEmpty and !in.isEmpty)
 DUMP(in, out)
 return out.dequeue

DUMP(A, B) =
 if (!A.isEmpty)
 x = A.dequeue()
 DUMP(A, B)
 B.enqueue(x)
</code></pre>

entityMap|blocks|key|b41i2|text|下面是一些简单的伪代码，push是O(n)，pop+/+peek是O(1)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|6so9t|Qpush+=+Qinstance()
Qpop+=+Qinstance()

def+stack.push(item):
++++Qpush.add(item)
++++while+Qpop.peek()+!=+null:+//transfer+Qpop+into+Qpush
++++++++Qpush.add(Qpop.remove())+
++++swap+=+Qpush
++++Qpush+=+Qpop
++++Qpop+=+swap

def+stack.pop():
++++return+Qpop.remove()

def+stack.peek():
++++return+Qpop.peek()|code-block|syntax|javascript^0|0^^$0|$]|1|@$2|3|4|5|6|7|8|H|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|I|9|@]|A|@]|B|$F|G]]]]

Here is some simple pseudo code, push is O(n), pop / peek is O(1):

<pre><code>Qpush = Qinstance()
Qpop = Qinstance()

def stack.push(item):
 Qpush.add(item)
 while Qpop.peek() != null: //transfer Qpop into Qpush
 Qpush.add(Qpop.remove()) 
 swap = Qpush
 Qpush = Qpop
 Qpop = swap

def stack.pop():
 return Qpop.remove()

def stack.peek():
 return Qpop.peek()
</code></pre>

entityMap|blocks|key|9grc9|text|假设S1和S2是在队列实现中使用的两个堆栈。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|fqugm|struct+Stack+
{+struct+Queue+*Q1;
++struct+Queue+*Q2;
}|code-block|syntax|javascript|b2hsj|我们确保一个队列始终为空。|uass|推送操作：无论哪个队列不为空，都在其中插入元素。|4lt3o|检查队列Q1是否为空。如果Q1为空，则将其中的元素排入队列。|unordered-list-item|e3mns|否则，将元素EnQueue到Q1中。|7n4at|Push+(struct+Stack+*S,+int+data)+++++{++++++if(isEmptyQueue(S->Q1)++++++++++EnQueue(S->Q2,+data);+++++else+EnQueue(S->Q1,+data);+++++}|offset|length|style|CODE|6snhs|时间复杂度:+O(1)|228q3|Pop操作：将n-1个元素转移到其他队列中，并从队列中删除最后一个元素以执行弹出操作。|fofr9|如果队列Q1不为空，那么将n-1个元素从Q1转移到Q2，然后DeQueue+Q1的最后一个元素并返回它。|cmeqq|如果队列Q2不为空，那么将n-1个元素从Q2转移到Q1，然后DeQueue+Q2的最后一个元素并返回它。|5e37k|`|2snp9|int+Pop(struct+Stack+*S){
int+i,+size;
if(IsEmptyQueue(S->Q2))+
{
size=size(S->Q1);
i=0;
while(iQ2,+Dequeue(S->Q1))+;
++i%2B%2B;
}
return+DeQueue(S->Q1);++
}
else{
size=size(S->Q2);
while(iQ1,+Dequeue(S->Q2))+;
i%2B%2B;
}
return+DeQueue(S->Q2);
}+}|987ml|时间复杂度:+pop操作的运行时间是O(n)，因为每次调用pop时，我们都将所有元素从一个队列转移到oter。^0|0|0|0|0|0|0|0|3Q|0|0|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|1A|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|1B|9|@]|A|@]|B|$F|G]]|$2|H|4|I|6|7|8|1C|9|@]|A|@]|B|$]]|$2|J|4|K|6|7|8|1D|9|@]|A|@]|B|$]]|$2|L|4|M|6|N|8|1E|9|@]|A|@]|B|$]]|$2|O|4|P|6|N|8|1F|9|@]|A|@]|B|$]]|$2|Q|4|R|6|7|8|1G|9|@$S|1H|T|1I|U|V]]|A|@]|B|$]]|$2|W|4|X|6|7|8|1J|9|@]|A|@]|B|$]]|$2|Y|4|Z|6|7|8|1K|9|@]|A|@]|B|$]]|$2|10|4|11|6|N|8|1L|9|@]|A|@]|B|$]]|$2|12|4|13|6|N|8|1M|9|@]|A|@]|B|$]]|$2|14|4|15|6|7|8|1N|9|@]|A|@]|B|$]]|$2|16|4|17|6|E|8|1O|9|@]|A|@]|B|$F|G]]|$2|18|4|19|6|7|8|1P|9|@]|A|@]|B|$]]]]

Let S1 and S2 be the two Stacks to be used in the implementation of queues.

<pre><code>struct Stack 
{ struct Queue *Q1;
 struct Queue *Q2;
}
</code></pre>

We make sure that one queue is empty always.

Push operation :
Whichever queue is not empty, insert the element in it.

<ul>
<li>Check whether queue Q1 is empty or not. If Q1 is empty then Enqueue the element in it.</li>
<li>Otherwise EnQueue the element into Q1.</li>
</ul>

<code>Push (struct Stack *S, int data)
 { 
 if(isEmptyQueue(S-&gt;Q1)
 EnQueue(S-&gt;Q2, data);
 else EnQueue(S-&gt;Q1, data);
 }
</code> 

Time Complexity: O(1)

Pop Operation: Transfer n-1 elements to other queue and delete last from queue for performing pop operation.

<ul>
<li>If queue Q1 is not empty then transfer n-1 elements from Q1 to Q2 and then, DeQueue the last element of Q1 and return it.</li>
<li>If queue Q2 is not empty then transfer n-1 elements from Q2 to Q1 and then, DeQueue the last element of Q2 and return it.</li>
</ul>

`

<pre><code>int Pop(struct Stack *S){
int i, size;
if(IsEmptyQueue(S-&gt;Q2)) 
{
size=size(S-&gt;Q1);
i=0;
while(i&lt;size-1)
{ EnQueue(S-&gt;Q2, Dequeue(S-&gt;Q1)) ;
 i++;
}
return DeQueue(S-&gt;Q1); 
}
else{
size=size(S-&gt;Q2);
while(i&lt;size-1)
EnQueue(S-&gt;Q1, Dequeue(S-&gt;Q2)) ;
i++;
}
return DeQueue(S-&gt;Q2);
} }
</code></pre>

Time Complexity: Running Time of pop Operation is O(n) as each time pop is called, we are transferring all the elements from one queue to oter.

entityMap|blocks|key|6qbsd|text|#include+
using+namespace+std;
queueQ;
stackStk;
void+PRINT(stackss+,+queueqq)+{
++++while(+ss.size()+)+{
++++++++cout+<<+ss.top()+<<+"+"+;
++++++++ss.pop();
++++}
++++puts("");
++++while(+qq.size()+)+{
++++++++cout+<<+qq.front()+<<+"+"+;
++++++++qq.pop();
++++}
++++puts("\n----------------------------------");
}
void+POP()+{
++++queueTmp+;
++++while(+Q.size()+>+1+)+{
++++++++Tmp.push(+Q.front()++);
++++++++Q.pop();
++++}
++++cout+<<+Q.front()+<<+"+"+<<+Stk.top()+<<+endl;
++++Q.pop()+,+Stk.pop()+;
++++Q+=+Tmp+;
}
void+PUSH(int+x+)+{
++++Q.push(x);
++++Stk.push(x);
}
int+main()+{
++++while(+true+)+{
++++++++string+typ+;
++++++++cin+>>+typ+;
++++++++if(+typ+==+"push"+)+{
++++++++++++int+x+;
++++++++++++cin+>>+x;
++++++++++++PUSH(x);
++++++++}+else+POP();
++++++++PRINT(Stk,Q);
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>#include &lt;bits/stdc++.h&gt;
using namespace std;
queue&lt;int&gt;Q;
stack&lt;int&gt;Stk;
void PRINT(stack&lt;int&gt;ss , queue&lt;int&gt;qq) {
 while( ss.size() ) {
 cout &lt;&lt; ss.top() &lt;&lt; " " ;
 ss.pop();
 }
 puts("");
 while( qq.size() ) {
 cout &lt;&lt; qq.front() &lt;&lt; " " ;
 qq.pop();
 }
 puts("\n----------------------------------");
}
void POP() {
 queue&lt;int&gt;Tmp ;
 while( Q.size() &gt; 1 ) {
 Tmp.push( Q.front() );
 Q.pop();
 }
 cout &lt;&lt; Q.front() &lt;&lt; " " &lt;&lt; Stk.top() &lt;&lt; endl;
 Q.pop() , Stk.pop() ;
 Q = Tmp ;
}
void PUSH(int x ) {
 Q.push(x);
 Stk.push(x);
}
int main() {
 while( true ) {
 string typ ;
 cin &gt;&gt; typ ;
 if( typ == "push" ) {
 int x ;
 cin &gt;&gt; x;
 PUSH(x);
 } else POP();
 PRINT(Stk,Q);
 }
}
</code></pre>

entityMap|blocks|key|dfbhj|text|这是我的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|fqb29|概念_后面：：push(struct+Stack*+S,int+data)：：此函数将Q1中的第一个元素和Q2中的其余元素排入队列pop(struct+Stack*+S)：：如果Q2不为空，则将所有elem传输到Q1并返回Q2中的最后一个elem，否则(表示Q2为空)将所有elem传输到Q2并返回Q1中的最后一个elem|offset|length|style|CODE|eurdl|效率_后面：：push(struct+Stack*S,int+data)：：o(1)//因为每个数据只有一个队列pop(struct+Stack*+S)：：o(N)//因为每个pop传输最差的n-1个数据。|aia1p|#include
#include
struct+Queue{
++++int+front;
++++int+rear;
++++int+*arr;
++++int+size;
++++};
struct+Stack+{
++++struct+Queue+*Q1;
++++struct+Queue+*Q2;
++++};
struct+Queue*+Qconstructor(int+capacity)
{
++++struct+Queue+*Q=malloc(sizeof(struct+Queue));
++++Q->front=Q->rear=-1;
++++Q->size=capacity;
++++Q->arr=malloc(Q->size*sizeof(int));
++++return+Q;
++++}
int+isEmptyQueue(struct+Queue+*Q)
{
++++return+(Q->front==-1);
++++}
int+isFullQueue(struct+Queue+*Q)
{
++++return+((Q->rear%2B1)+%25+Q->size+==Q->front);
++++}
void+enqueue(struct+Queue+*Q,int+data)
{
++++if(isFullQueue(Q))
++++++++{
++++++++++++printf("Queue+overflow\n");
++++++++++++return;}
++++Q->rear=Q->rear%2B1+%25+Q->size;
++++Q->arr[Q->rear]=data;
++++if(Q->front==-1)
++++++++Q->front=Q->rear;
++++++++}
int+dequeue(struct+Queue+*Q)
{
++++if(isEmptyQueue(Q)){
++++++++printf("Queue+underflow\n");
++++++++return;
++++++++}
++++int+data=Q->arr[Q->front];
++++if(Q->front==Q->rear)
++++++++Q->front=-1;
++++else
++++Q->front=Q->front%2B1+%25+Q->size;
++++return+data;
++++}
///////////////////////*************main+algo****************////////////////////////
struct+Stack*+Sconstructor(int+capacity)
{
++++struct+Stack+*S=malloc(sizeof(struct+Stack));
++++S->Q1=Qconstructor(capacity);
++++S->Q2=Qconstructor(capacity);
++++return+S;
}
void+push(struct+Stack+*S,int+data)
{
++++if(isEmptyQueue(S->Q1))
++++++++enqueue(S->Q1,data);
++++else
++++++++enqueue(S->Q2,data);
++++}
int+pop(struct+Stack+*S)
{
++++int+i,tmp;
++++if(!isEmptyQueue(S->Q2)){
++++++++for(i=S->Q2->front;i<=S->Q2->rear;i%2B%2B){
++++++++++++tmp=dequeue(S->Q2);
++++++++++++if(isEmptyQueue(S->Q2))
++++++++++++++++return+tmp;
++++++++++++else
++++++++++++++++enqueue(S->Q1,tmp);
++++++++++++++++}
++++++++++++}
++++else{
++++++++for(i=S->Q1->front;i<=S->Q1->rear;i%2B%2B){
++++++++++++tmp=dequeue(S->Q1);
++++++++++++if(isEmptyQueue(S->Q1))
++++++++++++++++return+tmp;
++++++++++++else
++++++++++++++++enqueue(S->Q2,tmp);
++++++++++++++++}
++++++++++++}
++++++++}
////////////////*************end+of+main+algo+my+algo************
///////////////*************push()+O(1);;;;pop()+O(n);;;;*******/////
main()
{
++++int+size;
++++printf("Enter+the+number+of+elements+in+the+Stack(made+of+2+queue's)::\n");
++++scanf("%25d",&size);
++++struct+Stack+*S=Sconstructor(size);
++++push(S,1);
++++push(S,2);
++++push(S,3);
++++push(S,4);
++++printf("%25d\n",pop(S));
++++push(S,5);
++++printf("%25d\n",pop(S));
++++printf("%25d\n",pop(S));
++++printf("%25d\n",pop(S));
++++printf("%25d\n",pop(S));
++++}|code-block|syntax|javascript^0|0|7|U|1T|K|0|7|T|1K|K|0^^$0|$]|1|@$2|3|4|5|6|7|8|P|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|Q|9|@$E|R|F|S|G|H]|$E|T|F|U|G|H]]|A|@]|B|$]]|$2|I|4|J|6|7|8|V|9|@$E|W|F|X|G|H]|$E|Y|F|Z|G|H]]|A|@]|B|$]]|$2|K|4|L|6|M|8|10|9|@]|A|@]|B|$N|O]]]]

Here's my solution..

Concept_Behind::
<code>push(struct Stack* S,int data)</code>::This function enqueue first element in Q1 and rest in Q2
<code>pop(struct Stack* S)</code>::if Q2 is not empty the transfers all elem's into Q1 and return the last elem in Q2
else(which means Q2 is empty ) transfers all elem's into Q2 and returns the last elem in Q1

Efficiency_Behind::
<code>push(struct Stack*S,int data)</code>::O(1)//since single enqueue per data
<code>pop(struct Stack* S)</code>::O(n)//since tranfers worst n-1 data per pop.

<pre><code>#include&lt;stdio.h&gt;
#include&lt;stdlib.h&gt;
struct Queue{
 int front;
 int rear;
 int *arr;
 int size;
 };
struct Stack {
 struct Queue *Q1;
 struct Queue *Q2;
 };
struct Queue* Qconstructor(int capacity)
{
 struct Queue *Q=malloc(sizeof(struct Queue));
 Q-&gt;front=Q-&gt;rear=-1;
 Q-&gt;size=capacity;
 Q-&gt;arr=malloc(Q-&gt;size*sizeof(int));
 return Q;
 }
int isEmptyQueue(struct Queue *Q)
{
 return (Q-&gt;front==-1);
 }
int isFullQueue(struct Queue *Q)
{
 return ((Q-&gt;rear+1) % Q-&gt;size ==Q-&gt;front);
 }
void enqueue(struct Queue *Q,int data)
{
 if(isFullQueue(Q))
 {
 printf("Queue overflow\n");
 return;}
 Q-&gt;rear=Q-&gt;rear+1 % Q-&gt;size;
 Q-&gt;arr[Q-&gt;rear]=data;
 if(Q-&gt;front==-1)
 Q-&gt;front=Q-&gt;rear;
 }
int dequeue(struct Queue *Q)
{
 if(isEmptyQueue(Q)){
 printf("Queue underflow\n");
 return;
 }
 int data=Q-&gt;arr[Q-&gt;front];
 if(Q-&gt;front==Q-&gt;rear)
 Q-&gt;front=-1;
 else
 Q-&gt;front=Q-&gt;front+1 % Q-&gt;size;
 return data;
 }
///////////////////////*************main algo****************////////////////////////
struct Stack* Sconstructor(int capacity)
{
 struct Stack *S=malloc(sizeof(struct Stack));
 S-&gt;Q1=Qconstructor(capacity);
 S-&gt;Q2=Qconstructor(capacity);
 return S;
}
void push(struct Stack *S,int data)
{
 if(isEmptyQueue(S-&gt;Q1))
 enqueue(S-&gt;Q1,data);
 else
 enqueue(S-&gt;Q2,data);
 }
int pop(struct Stack *S)
{
 int i,tmp;
 if(!isEmptyQueue(S-&gt;Q2)){
 for(i=S-&gt;Q2-&gt;front;i&lt;=S-&gt;Q2-&gt;rear;i++){
 tmp=dequeue(S-&gt;Q2);
 if(isEmptyQueue(S-&gt;Q2))
 return tmp;
 else
 enqueue(S-&gt;Q1,tmp);
 }
 }
 else{
 for(i=S-&gt;Q1-&gt;front;i&lt;=S-&gt;Q1-&gt;rear;i++){
 tmp=dequeue(S-&gt;Q1);
 if(isEmptyQueue(S-&gt;Q1))
 return tmp;
 else
 enqueue(S-&gt;Q2,tmp);
 }
 }
 }
////////////////*************end of main algo my algo************
///////////////*************push() O(1);;;;pop() O(n);;;;*******/////
main()
{
 int size;
 printf("Enter the number of elements in the Stack(made of 2 queue's)::\n");
 scanf("%d",&amp;size);
 struct Stack *S=Sconstructor(size);
 push(S,1);
 push(S,2);
 push(S,3);
 push(S,4);
 printf("%d\n",pop(S));
 push(S,5);
 printf("%d\n",pop(S));
 printf("%d\n",pop(S));
 printf("%d\n",pop(S));
 printf("%d\n",pop(S));
 }
</code></pre>

entityMap|blocks|key|9rkvg|text|import+java.util.LinkedList;
import+java.util.Queue;


public+class+StackQueue+{

++++static+Queue+Q1+=+new+LinkedList();
++++static+Queue+Q2+=+new+LinkedList();
++++public+static+void+main(String+args[])+{



++++++++push(24);
++++++++push(34);
++++++++push(4);
++++++++push(10);
++++++++push(1);
++++++++push(43);
++++++++push(21);
++++++++System.out.println("Popped+element+is++"%2Bpop());
++++++++System.out.println("Popped+element+is++"%2Bpop());
++++++++System.out.println("Popped+element+is++"%2Bpop());


++++}

++++public+static+void+push(int+data)+{

++++++++Q1.add(data);

++++}

++++public+static+int+pop()+{

++++++++if(Q1.isEmpty())+{
++++++++System.out.println("Cannot+pop+elements+,++Stack+is+Empty+!!");+
++++++++return+-1;
++++++++}
++++++++else
++++++++{
++++++++while(Q1.size()+>+1)+{
++++++++++++Q2.add(Q1.remove());
++++++++}
++++++++int+element+=+Q1.remove();
++++++++Queue+temp+=+new+LinkedList();
++++++++temp+=+Q1;
++++++++Q1+=+Q2;
++++++++Q2+=+temp;
++++++++return+element;
++++++++}
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>import java.util.LinkedList;
import java.util.Queue;


public class StackQueue {

 static Queue&lt;Integer&gt; Q1 = new LinkedList&lt;Integer&gt;();
 static Queue&lt;Integer&gt; Q2 = new LinkedList&lt;Integer&gt;();
 public static void main(String args[]) {



 push(24);
 push(34);
 push(4);
 push(10);
 push(1);
 push(43);
 push(21);
 System.out.println("Popped element is "+pop());
 System.out.println("Popped element is "+pop());
 System.out.println("Popped element is "+pop());


 }

 public static void push(int data) {

 Q1.add(data);

 }

 public static int pop() {

 if(Q1.isEmpty()) {
 System.out.println("Cannot pop elements , Stack is Empty !!"); 
 return -1;
 }
 else
 {
 while(Q1.size() &gt; 1) {
 Q2.add(Q1.remove());
 }
 int element = Q1.remove();
 Queue&lt;Integer&gt; temp = new LinkedList&lt;Integer&gt;();
 temp = Q1;
 Q1 = Q2;
 Q2 = temp;
 return element;
 }
 }
}
</code></pre>

entityMap|blocks|key|3ecn8|text|#include+"stdio.h"
#include+"stdlib.h"

typedef+struct+{
++++int+*q;
++++int+size;
++++int+front;
++++int+rear;
}+Queue;
typedef+struct+{
++++Queue+*q1;
++++Queue+*q2;
}+Stack;

int+queueIsEmpty(Queue+*q)+{
++++if+(q->front+==+-1+&&+q->rear+==+-1)+{
++++++++printf("\nQUEUE+is+EMPTY\n");
++++++++return+1;
++++}
++++return+0;
}
int+queueIsFull(Queue+*q)+{
++++if+(q->rear+==+q->size-1)+{
++++++++return+1;
++++}
++++return+0;
}
int+queueTop(Queue+*q)+{
++++if+(queueIsEmpty(q))+{
++++++++return+-1;
++++}
++++return+q->q[q->front];
}
int+queuePop(Queue+*q)+{
++++if+(queueIsEmpty(q))+{
++++++++return+-1;
++++}
++++int+item+=+q->q[q->front];
++++if+(q->front+==+q->rear)+{
++++++++q->front+=+q->rear+=+-1;
++++}
++++else+{
++++++++q->front%2B%2B;
++++}
++++return+item;
}
void+queuePush(Queue+*q,+int+val)+{
++++if+(queueIsFull(q))+{
++++++++printf("\nQUEUE+is+FULL\n");
++++++++return;
++++}
++++if+(queueIsEmpty(q))+{
++++++++q->front%2B%2B;
++++++++q->rear%2B%2B;
++++}+else+{
++++++++q->rear%2B%2B;
++++}
++++q->q[q->rear]+=+val;
}
Queue+*queueCreate(int+maxSize)+{
++++Queue+*q+=+(Queue*)malloc(sizeof(Queue));
++++q->front+=+q->rear+=+-1;
++++q->size+=+maxSize;
++++q->q+=+(int*)malloc(sizeof(int)*maxSize);
++++return+q;
}
/*+Create+a+stack+*/
void+stackCreate(Stack+*stack,+int+maxSize)+{
++++Stack+**s+=+(Stack**)+stack;
++++*s+=+(Stack*)malloc(sizeof(Stack));
++++(*s)->q1+=+queueCreate(maxSize);
++++(*s)->q2+=+queueCreate(maxSize);
}

/*+Push+element+x+onto+stack+*/
void+stackPush(Stack+*stack,+int+element)+{
++++Stack+**s+=+(Stack**)+stack;
++++queuePush((*s)->q2,+element);
++++while+(!queueIsEmpty((*s)->q1))+{
++++++++int+item+=+queuePop((*s)->q1);
++++++++queuePush((*s)->q2,+item);
++++}
++++Queue+*tmp+=+(*s)->q1;
++++(*s)->q1+=+(*s)->q2;
++++(*s)->q2+=+tmp;
}

/*+Removes+the+element+on+top+of+the+stack+*/
void+stackPop(Stack+*stack)+{
++++Stack+**s+=+(Stack**)+stack;
++++queuePop((*s)->q1);
}

/*+Get+the+top+element+*/
int+stackTop(Stack+*stack)+{
++++Stack+**s+=+(Stack**)+stack;
++++if+(!queueIsEmpty((*s)->q1))+{
++++++return+queueTop((*s)->q1);
++++}
++++return+-1;
}

/*+Return+whether+the+stack+is+empty+*/
bool+stackEmpty(Stack+*stack)+{
++++Stack+**s+=+(Stack**)+stack;
++++if+(queueIsEmpty((*s)->q1))+{
++++++++return+true;
++++}
++++return+false;
}

/*+Destroy+the+stack+*/
void+stackDestroy(Stack+*stack)+{
++++Stack+**s+=+(Stack**)+stack;
++++free((*s)->q1);
++++free((*s)->q2);
++++free((*s));
}

int+main()
{
++Stack+*s+=+NULL;
++stackCreate((Stack*)&s,+10);
++stackPush((Stack*)&s,+44);
++//stackPop((Stack*)&s);
++printf("\n%25d",+stackTop((Stack*)&s));
++stackDestroy((Stack*)&s);
++return+0;
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>#include "stdio.h"
#include "stdlib.h"

typedef struct {
 int *q;
 int size;
 int front;
 int rear;
} Queue;
typedef struct {
 Queue *q1;
 Queue *q2;
} Stack;

int queueIsEmpty(Queue *q) {
 if (q-&gt;front == -1 &amp;&amp; q-&gt;rear == -1) {
 printf("\nQUEUE is EMPTY\n");
 return 1;
 }
 return 0;
}
int queueIsFull(Queue *q) {
 if (q-&gt;rear == q-&gt;size-1) {
 return 1;
 }
 return 0;
}
int queueTop(Queue *q) {
 if (queueIsEmpty(q)) {
 return -1;
 }
 return q-&gt;q[q-&gt;front];
}
int queuePop(Queue *q) {
 if (queueIsEmpty(q)) {
 return -1;
 }
 int item = q-&gt;q[q-&gt;front];
 if (q-&gt;front == q-&gt;rear) {
 q-&gt;front = q-&gt;rear = -1;
 }
 else {
 q-&gt;front++;
 }
 return item;
}
void queuePush(Queue *q, int val) {
 if (queueIsFull(q)) {
 printf("\nQUEUE is FULL\n");
 return;
 }
 if (queueIsEmpty(q)) {
 q-&gt;front++;
 q-&gt;rear++;
 } else {
 q-&gt;rear++;
 }
 q-&gt;q[q-&gt;rear] = val;
}
Queue *queueCreate(int maxSize) {
 Queue *q = (Queue*)malloc(sizeof(Queue));
 q-&gt;front = q-&gt;rear = -1;
 q-&gt;size = maxSize;
 q-&gt;q = (int*)malloc(sizeof(int)*maxSize);
 return q;
}
/* Create a stack */
void stackCreate(Stack *stack, int maxSize) {
 Stack **s = (Stack**) stack;
 *s = (Stack*)malloc(sizeof(Stack));
 (*s)-&gt;q1 = queueCreate(maxSize);
 (*s)-&gt;q2 = queueCreate(maxSize);
}

/* Push element x onto stack */
void stackPush(Stack *stack, int element) {
 Stack **s = (Stack**) stack;
 queuePush((*s)-&gt;q2, element);
 while (!queueIsEmpty((*s)-&gt;q1)) {
 int item = queuePop((*s)-&gt;q1);
 queuePush((*s)-&gt;q2, item);
 }
 Queue *tmp = (*s)-&gt;q1;
 (*s)-&gt;q1 = (*s)-&gt;q2;
 (*s)-&gt;q2 = tmp;
}

/* Removes the element on top of the stack */
void stackPop(Stack *stack) {
 Stack **s = (Stack**) stack;
 queuePop((*s)-&gt;q1);
}

/* Get the top element */
int stackTop(Stack *stack) {
 Stack **s = (Stack**) stack;
 if (!queueIsEmpty((*s)-&gt;q1)) {
 return queueTop((*s)-&gt;q1);
 }
 return -1;
}

/* Return whether the stack is empty */
bool stackEmpty(Stack *stack) {
 Stack **s = (Stack**) stack;
 if (queueIsEmpty((*s)-&gt;q1)) {
 return true;
 }
 return false;
}

/* Destroy the stack */
void stackDestroy(Stack *stack) {
 Stack **s = (Stack**) stack;
 free((*s)-&gt;q1);
 free((*s)-&gt;q2);
 free((*s));
}

int main()
{
 Stack *s = NULL;
 stackCreate((Stack*)&amp;s, 10);
 stackPush((Stack*)&amp;s, 44);
 //stackPop((Stack*)&amp;s);
 printf("\n%d", stackTop((Stack*)&amp;s));
 stackDestroy((Stack*)&amp;s);
 return 0;
}
</code></pre>

entityMap|blocks|key|dmr5d|text|Q1+=+[10,+15,+20,+25,+30]
Q2+=+[]

exp:
{+++
++++dequeue+n-1+element+from+Q1+and+enqueue+into+Q2:+Q2+==+[10,+15,+20,+25]

++++now+Q1+dequeue+gives+"30"+that+inserted+last+and+working+as+stack
}

swap+Q1+and+Q2+then+GOTO+exp|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>Q1 = [10, 15, 20, 25, 30]
Q2 = []

exp:
{ 
 dequeue n-1 element from Q1 and enqueue into Q2: Q2 == [10, 15, 20, 25]

 now Q1 dequeue gives "30" that inserted last and working as stack
}

swap Q1 and Q2 then GOTO exp
</code></pre>

entityMap|blocks|key|ful05|text|import+java.util.LinkedList;
import+java.util.Queue;

class+MyStack+{
++++Queue+queue1+=+new+LinkedList();
++++Queue+queue2+=+new+LinkedList();

++++//+Push+element+x+onto+stack.
++++public+void+push(int+x)+{
++++++++if(isEmpty()){
++++++++++++queue1.offer(x);
++++++++}else{
++++++++++++if(queue1.size()>0){
++++++++++++++++queue2.offer(x);
++++++++++++++++int+size+=+queue1.size();
++++++++++++++++while(size>0){
++++++++++++++++++++queue2.offer(queue1.poll());
++++++++++++++++++++size--;
++++++++++++++++}
++++++++++++}else+if(queue2.size()>0){
++++++++++++++++queue1.offer(x);
++++++++++++++++int+size+=+queue2.size();
++++++++++++++++while(size>0){
++++++++++++++++++++queue1.offer(queue2.poll());
++++++++++++++++++++size--;
++++++++++++++++}
++++++++++++}
++++++++}
++++}

++++//+Removes+the+element+on+top+of+the+stack.
++++public+void+pop()+{
++++++++if(queue1.size()>0){
++++++++++++queue1.poll();
++++++++}else+if(queue2.size()>0){
++++++++++++queue2.poll();
++++++++}
++++}

++++//+Get+the+top+element.+You+can+make+it+more+perfect+just+example
++++public+int+top()+{
+++++++if(queue1.size()>0){
++++++++++++return+queue1.peek();
++++++++}else+if(queue2.size()>0){
++++++++++++return+queue2.peek();
++++++++}
++++++++return+0;
++++}

++++//+Return+whether+the+stack+is+empty.
++++public+boolean+isEmpty()+{
++++++++return+queue1.isEmpty()+&&+queue2.isEmpty();
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>import java.util.LinkedList;
import java.util.Queue;

class MyStack {
 Queue&lt;Integer&gt; queue1 = new LinkedList&lt;Integer&gt;();
 Queue&lt;Integer&gt; queue2 = new LinkedList&lt;Integer&gt;();

 // Push element x onto stack.
 public void push(int x) {
 if(isEmpty()){
 queue1.offer(x);
 }else{
 if(queue1.size()&gt;0){
 queue2.offer(x);
 int size = queue1.size();
 while(size&gt;0){
 queue2.offer(queue1.poll());
 size--;
 }
 }else if(queue2.size()&gt;0){
 queue1.offer(x);
 int size = queue2.size();
 while(size&gt;0){
 queue1.offer(queue2.poll());
 size--;
 }
 }
 }
 }

 // Removes the element on top of the stack.
 public void pop() {
 if(queue1.size()&gt;0){
 queue1.poll();
 }else if(queue2.size()&gt;0){
 queue2.poll();
 }
 }

 // Get the top element. You can make it more perfect just example
 public int top() {
 if(queue1.size()&gt;0){
 return queue1.peek();
 }else if(queue2.size()&gt;0){
 return queue2.peek();
 }
 return 0;
 }

 // Return whether the stack is empty.
 public boolean isEmpty() {
 return queue1.isEmpty() &amp;&amp; queue2.isEmpty();
 }
}
</code></pre>

entityMap|blocks|key|lsbj|text|只使用一个队列的Python代码|type|unstyled|depth|inlineStyleRanges|entityRanges|data|be64m|class+Queue(object):
++++def+__init__(self):
++++++++self.items=[]
++++def+enqueue(self,item):
++++++++self.items.insert(0,item)
++++def+dequeue(self):
++++++++if(not+self.isEmpty()):
++++++++++++return++self.items.pop()
++++def+isEmpty(self):
++++++++return++self.items==[]
++++def+size(self):
++++++++return+len(self.items)



class+stack(object):
++++++++def+__init__(self):
++++++++++++self.q1=+Queue()


++++++++def+push(self,+item):
++++++++++++self.q1.enqueue(item)+


++++++++def+pop(self):
++++++++++++c=self.q1.size()
++++++++++++while(c>1):
++++++++++++++++self.q1.enqueue(self.q1.dequeue())
++++++++++++++++c-=1
++++++++++++return+self.q1.dequeue()



++++++++def+size(self):
++++++++++++return+self.q1.size()+


++++++++def+isempty(self):
++++++++++++if+self.size+>+0:
+++++++++++++++return+True
++++++++++++else:
+++++++++++++++return+False|code-block|syntax|javascript^0|0^^$0|$]|1|@$2|3|4|5|6|7|8|H|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|I|9|@]|A|@]|B|$F|G]]]]

Python Code Using Only One Queue 

<pre><code> class Queue(object):
 def __init__(self):
 self.items=[]
 def enqueue(self,item):
 self.items.insert(0,item)
 def dequeue(self):
 if(not self.isEmpty()):
 return self.items.pop()
 def isEmpty(self):
 return self.items==[]
 def size(self):
 return len(self.items)



class stack(object):
 def __init__(self):
 self.q1= Queue()


 def push(self, item):
 self.q1.enqueue(item) 


 def pop(self):
 c=self.q1.size()
 while(c&gt;1):
 self.q1.enqueue(self.q1.dequeue())
 c-=1
 return self.q1.dequeue()



 def size(self):
 return self.q1.size() 


 def isempty(self):
 if self.size &gt; 0:
 return True
 else:
 return False
</code></pre>

entityMap|blocks|key|664en|text|下面是完整的c#代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|dpdr3|它已经用单队列实现，|l8to|推送：|d4na5|1.+add+new+element.
2.+Remove+elements+from+Queue+(totalsize-1)+times+and+add+back+to+the+Queue|code-block|syntax|javascript|5u47d|流行：|apfbi|normal+remove





+using+System;
++++using+System.Collections.Generic;
++++using+System.Linq;
++++using+System.Text;
++++using+System.Threading.Tasks;

++++namespace+StackImplimentationUsingQueue
++++{
++++++++class+Program
++++++++{
++++++++++++public+class+Node
++++++++++++{
++++++++++++++++public+int+data;
++++++++++++++++public+Node+link;
++++++++++++}
++++++++++++public+class+Queue
++++++++++++{
++++++++++++++++public+Node+rear;
++++++++++++++++public+Node+front;
++++++++++++++++public+int+size+=+0;
++++++++++++++++public+void+EnQueue(int+data)
++++++++++++++++{
++++++++++++++++++++Node+n+=+new+Node();
++++++++++++++++++++n.data+=+data;
++++++++++++++++++++n.link+=+null;
++++++++++++++++++++if+(rear+==+null)
++++++++++++++++++++++++front+=+rear+=+n;
++++++++++++++++++++else
++++++++++++++++++++{
++++++++++++++++++++++++rear.link+=+n;
++++++++++++++++++++++++rear+=+n;
++++++++++++++++++++}
++++++++++++++++++++size%2B%2B;
++++++++++++++++++++Display();
++++++++++++++++}
++++++++++++++++public+Node+DeQueue()
++++++++++++++++{
++++++++++++++++++++Node+temp+=+new+Node();
++++++++++++++++++++if+(front+==+null)
++++++++++++++++++++++++Console.WriteLine("Empty");
++++++++++++++++++++else
++++++++++++++++++++{
++++++++++++++++++++++++temp+=+front;
++++++++++++++++++++++++front+=+front.link;
++++++++++++++++++++++++size--;
++++++++++++++++++++}
++++++++++++++++++++Display();
++++++++++++++++++++return+temp;
++++++++++++++++}
++++++++++++++++public+void+Display()
++++++++++++++++{
++++++++++++++++++++if+(size+==+0)
++++++++++++++++++++++++Console.WriteLine("Empty");
++++++++++++++++++++else
++++++++++++++++++++{
++++++++++++++++++++++++Console.Clear();
++++++++++++++++++++++++Node+n+=+front;
++++++++++++++++++++++++while+(n+!=+null)
++++++++++++++++++++++++{
++++++++++++++++++++++++++++Console.WriteLine(n.data);
++++++++++++++++++++++++++++n+=+n.link;
++++++++++++++++++++++++}
++++++++++++++++++++}
++++++++++++++++}
++++++++++++}
++++++++++++public+class+Stack
++++++++++++{
++++++++++++++++public+Queue+q;
++++++++++++++++public+int+size+=+0;
++++++++++++++++public+Node+top;
++++++++++++++++public+Stack()
++++++++++++++++{
++++++++++++++++++++q+=+new+Queue();
++++++++++++++++}
++++++++++++++++public+void+Push(int+data)
++++++++++++++++{
++++++++++++++++++++Node+n+=+new+Node();
++++++++++++++++++++n.data+=+data;
++++++++++++++++++++q.EnQueue(data);
++++++++++++++++++++size%2B%2B;
++++++++++++++++++++int+counter+=+size;
++++++++++++++++++++while+(counter+>+1)
++++++++++++++++++++{
++++++++++++++++++++++++q.EnQueue(q.DeQueue().data);
++++++++++++++++++++++++counter--;
++++++++++++++++++++}
++++++++++++++++}
++++++++++++++++public+void+Pop()
++++++++++++++++{
++++++++++++++++++++q.DeQueue();
++++++++++++++++++++size--;
++++++++++++++++}
++++++++++++}
++++++++++++static+void+Main(string[]+args)
++++++++++++{
++++++++++++++++Stack+s=+new+Stack();
++++++++++++++++for+(int+i+=+1;+i+<=+3;+i%2B%2B)
++++++++++++++++++++s.Push(i);
++++++++++++++++for+(int+i+=+1;+i+<+3;+i%2B%2B)
++++++++++++++++++++s.Pop();
++++++++++++++++Console.ReadKey();
++++++++++++}
++++++++}
++++}^0|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|P|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|Q|9|@]|A|@]|B|$]]|$2|E|4|F|6|7|8|R|9|@]|A|@]|B|$]]|$2|G|4|H|6|I|8|S|9|@]|A|@]|B|$J|K]]|$2|L|4|M|6|7|8|T|9|@]|A|@]|B|$]]|$2|N|4|O|6|I|8|U|9|@]|A|@]|B|$J|K]]]]

here is the complete working code in c# :

It has been implemented with Single Queue,

push:

<pre><code>1. add new element.
2. Remove elements from Queue (totalsize-1) times and add back to the Queue
</code></pre>

pop:

<pre><code>normal remove





 using System;
 using System.Collections.Generic;
 using System.Linq;
 using System.Text;
 using System.Threading.Tasks;

 namespace StackImplimentationUsingQueue
 {
 class Program
 {
 public class Node
 {
 public int data;
 public Node link;
 }
 public class Queue
 {
 public Node rear;
 public Node front;
 public int size = 0;
 public void EnQueue(int data)
 {
 Node n = new Node();
 n.data = data;
 n.link = null;
 if (rear == null)
 front = rear = n;
 else
 {
 rear.link = n;
 rear = n;
 }
 size++;
 Display();
 }
 public Node DeQueue()
 {
 Node temp = new Node();
 if (front == null)
 Console.WriteLine("Empty");
 else
 {
 temp = front;
 front = front.link;
 size--;
 }
 Display();
 return temp;
 }
 public void Display()
 {
 if (size == 0)
 Console.WriteLine("Empty");
 else
 {
 Console.Clear();
 Node n = front;
 while (n != null)
 {
 Console.WriteLine(n.data);
 n = n.link;
 }
 }
 }
 }
 public class Stack
 {
 public Queue q;
 public int size = 0;
 public Node top;
 public Stack()
 {
 q = new Queue();
 }
 public void Push(int data)
 {
 Node n = new Node();
 n.data = data;
 q.EnQueue(data);
 size++;
 int counter = size;
 while (counter &gt; 1)
 {
 q.EnQueue(q.DeQueue().data);
 counter--;
 }
 }
 public void Pop()
 {
 q.DeQueue();
 size--;
 }
 }
 static void Main(string[] args)
 {
 Stack s= new Stack();
 for (int i = 1; i &lt;= 3; i++)
 s.Push(i);
 for (int i = 1; i &lt; 3; i++)
 s.Pop();
 Console.ReadKey();
 }
 }
 }
</code></pre>

entityMap|blocks|key|ankm3|text|这是一个非常简单的解决方案，它使用一个队列并提供像Stack这样的功能。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|ebsrr|public+class+CustomStack
{
++++Queue+que+=+new+Queue();

++++public+void+push(T+t)+//+STACK+=+LIFO+/+QUEUE+=+FIFO
++++{

++++++++if(+que.Count+==+0)
++++++++{
++++++++++++que.Enqueue(t);
++++++++}
++++++++else
++++++++{
++++++++++++que.Enqueue(t);
++++++++++++for+(int+i+=+0;+i+<+que.Count-1;+i%2B%2B)
++++++++++++{
++++++++++++++++var+data+=+que.Dequeue();

++++++++++++++++que.Enqueue(data);
++++++++++++}
++++++++}

++++}

++++public+void+pop()
++++{

++++++++Console.WriteLine("\nStack+Implementation:");
++++++++foreach+(var+item+in+que)
++++++++{
++++++++++++Console.Write("\n"+%2B+item.ToString()+%2B+"\t");
++++++++}

++++++++var+data+=+que.Dequeue();
++++++++Console.Write("\n+Dequeing+:"+%2B+data);
++++}

++++public+void+top()
++++{

++++++++Console.Write("\n+Top+:"+%2B+que.Peek());
++++}


}|code-block|syntax|javascript|7teqt|因此，在上面名为"CustomStack“的类中，我所做的只是检查队列是否为空，如果为空，则插入一个，然后依次插入，然后删除插入。按照这个逻辑，第一个将排在最后。例如:在队列中，我插入了1，现在尝试插入2。第二次删除1，然后再次插入，这样它就会变成相反的顺序。|1kmsq|谢谢你。^0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|L|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|M|9|@]|A|@]|B|$F|G]]|$2|H|4|I|6|7|8|N|9|@]|A|@]|B|$]]|$2|J|4|K|6|7|8|O|9|@]|A|@]|B|$]]]]

Here is very simple solution which uses one Queue and gives functionality like Stack.

<pre><code>public class CustomStack&lt;T&gt;
{
 Queue&lt;T&gt; que = new Queue&lt;T&gt;();

 public void push(T t) // STACK = LIFO / QUEUE = FIFO
 {

 if( que.Count == 0)
 {
 que.Enqueue(t);
 }
 else
 {
 que.Enqueue(t);
 for (int i = 0; i &lt; que.Count-1; i++)
 {
 var data = que.Dequeue();

 que.Enqueue(data);
 }
 }

 }

 public void pop()
 {

 Console.WriteLine("\nStack Implementation:");
 foreach (var item in que)
 {
 Console.Write("\n" + item.ToString() + "\t");
 }

 var data = que.Dequeue();
 Console.Write("\n Dequeing :" + data);
 }

 public void top()
 {

 Console.Write("\n Top :" + que.Peek());
 }


}
</code></pre>

So in the above class named "CustomStack" what I am doing is just checking the queue for empty , if empty then insert one and from then on wards insert and then remove insert. By this logic first will come last.
Example : In queue I inserted 1 and now trying to insert 2. Second time remove 1 and again insert so it becomes in reverse order.

Thank you.

entityMap|blocks|key|b9et8|text|下面是一个非常简单的Java解决方案，它支持高效的推送操作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|5pbuu|算法-|a9775|声明两个队列q1和q2。|ordered-list-item|1f7gr|推送操作-将元素入队到队列q1。|anl1b|弹出操作-确保队列q2不为空。如果为空，则将除最后一个元素之外的所有元素从q1中出列，并逐个将其排入q2。将q1中的最后一个元素排出队列，并将其存储为弹出的元素。交换队列q1和q2。返回存储的弹出元素。|4ua60|窥视操作-确保队列q2不为空。如果为空，则将除最后一个元素之外的所有元素从q1中出列，并逐个将其排入q2。将最后一个元素从q1中排出队列，并将其存储为peeked元素。将其排回队列q2，并交换队列q1和q2。返回存储的peeked元素。|5gf9b|以下是上述算法的代码：|7uokb|class+MyStack+{

++++java.util.Queue+q1;
++++java.util.Queue+q2;
++++int+SIZE+=+0;

++++/**+Initialize+your+data+structure+here.+*/
++++public+MyStack()+{
++++++++q1+=+new+LinkedList();
++++++++q2+=+new+LinkedList();

++++}

++++/**+Push+element+x+onto+stack.+*/
++++public+void+push(int+x)+{
++++++++q1.add(x);
++++++++SIZE+%2B%2B;

++++}

++++/**+Removes+the+element+on+top+of+the+stack+and+returns+that+element.+*/
++++public+int+pop()+{
++++++++ensureQ2IsNotEmpty();
++++++++int+poppedEle+=+q1.remove();
++++++++SIZE--;
++++++++swapQueues();
++++++++return+poppedEle;
++++}

++++/**+Get+the+top+element.+*/
++++public+int+top()+{
++++++++ensureQ2IsNotEmpty();
++++++++int+peekedEle+=+q1.remove();
++++++++q2.add(peekedEle);
++++++++swapQueues();
++++++++return+peekedEle;
++++}

++++/**+Returns+whether+the+stack+is+empty.+*/
++++public+boolean+empty()+{
++++++++return+q1.isEmpty()+&&+q2.isEmpty();

++++}

++++/**+move+all+elements+from+q1+to+q2+except+last+element+*/
++++public+void+ensureQ2IsNotEmpty()+{
++++++++for(int+i=0;+i+temp+=+q1;
++++++++q1+=+q2;
++++++++q2+=+temp;
++++}
}|code-block|syntax|javascript^0|0|0|0|0|0|0|0^^$0|$]|1|@$2|3|4|5|6|7|8|U|9|@]|A|@]|B|$]]|$2|C|4|D|6|7|8|V|9|@]|A|@]|B|$]]|$2|E|4|F|6|G|8|W|9|@]|A|@]|B|$]]|$2|H|4|I|6|G|8|X|9|@]|A|@]|B|$]]|$2|J|4|K|6|G|8|Y|9|@]|A|@]|B|$]]|$2|L|4|M|6|G|8|Z|9|@]|A|@]|B|$]]|$2|N|4|O|6|7|8|10|9|@]|A|@]|B|$]]|$2|P|4|Q|6|R|8|11|9|@]|A|@]|B|$S|T]]]]

Below is a very simple Java solution which supports the push operation efficient.

Algorithm -

<ol>
<li>Declare two Queues q1 and q2.</li>
<li>Push operation - Enqueue element to queue q1.</li>
<li>Pop operation - Ensure that queue q2 is not empty. If it is empty,
then dequeue all the elements from q1 except the last element and
enqueue it to q2 one by one. Dequeue the last element from q1 and
store it as the popped element. Swap the queues q1 and q2. Return
the stored popped element.</li>
<li>Peek operation - Ensure that queue q2 is not empty. If it is empty,
then dequeue all the elements from q1 except the last element and
enqueue it to q2 one by one. Dequeue the last element from q1 and
store it as the peeked element. Enqueue it back to queue q2 and swap
the queues q1 and q2. Return the stored peeked element.</li>
</ol>

Below is the code for above algorithm -

<pre><code>class MyStack {

 java.util.Queue&lt;Integer&gt; q1;
 java.util.Queue&lt;Integer&gt; q2;
 int SIZE = 0;

 /** Initialize your data structure here. */
 public MyStack() {
 q1 = new LinkedList&lt;Integer&gt;();
 q2 = new LinkedList&lt;Integer&gt;();

 }

 /** Push element x onto stack. */
 public void push(int x) {
 q1.add(x);
 SIZE ++;

 }

 /** Removes the element on top of the stack and returns that element. */
 public int pop() {
 ensureQ2IsNotEmpty();
 int poppedEle = q1.remove();
 SIZE--;
 swapQueues();
 return poppedEle;
 }

 /** Get the top element. */
 public int top() {
 ensureQ2IsNotEmpty();
 int peekedEle = q1.remove();
 q2.add(peekedEle);
 swapQueues();
 return peekedEle;
 }

 /** Returns whether the stack is empty. */
 public boolean empty() {
 return q1.isEmpty() &amp;&amp; q2.isEmpty();

 }

 /** move all elements from q1 to q2 except last element */
 public void ensureQ2IsNotEmpty() {
 for(int i=0; i&lt;SIZE-1; i++) {
 q2.add(q1.remove());
 }
 }

 /** Swap queues q1 and q2 */
 public void swapQueues() {
 Queue&lt;Integer&gt; temp = q1;
 q1 = q2;
 q2 = temp;
 }
}
</code></pre>

entityMap|blocks|key|dotaq|text|C#中的高效解决方案|type|unstyled|depth|inlineStyleRanges|entityRanges|data|52ug|public+class+MyStack+{
++++private+Queue+q1+=+new+Queue();
++++private+Queue+q2+=+new+Queue();
++++private+int+count+=+0;

++++/**
+++++*+Initialize+your+data+structure+here.
+++++*/
++++public+MyStack()+{
++++}

++++/**
+++++*+Push+element+x+onto+stack.
+++++*/
++++public+void+Push(int+x)+{
++++++++count%2B%2B;
++++++++q1.Enqueue(x);
++++++++while+(q2.Count+>+0)+{
++++++++++++q1.Enqueue(q2.Peek());
++++++++++++q2.Dequeue();
++++++++}
++++++++var+temp+=+q1;
++++++++q1+=+q2;
++++++++q2+=+temp;
++++}

++++/**
+++++*+Removes+the+element+on+top+of+the+stack+and+returns+that+element.
+++++*/
++++public+int+Pop()+{
++++++++count--;
++++++++return+q2.Dequeue();
++++}

++++/**
+++++*+Get+the+top+element.
+++++*/
++++public+int+Top()+{
++++++++return+q2.Peek();
++++}

++++/**
+++++*+Returns+whether+the+stack+is+empty.
+++++*/
++++public+bool+Empty()+{
++++++++if+(count+>+0)+return+false;
++++++++return+true;
++++}
}|code-block|syntax|javascript^0|0^^$0|$]|1|@$2|3|4|5|6|7|8|H|9|@]|A|@]|B|$]]|$2|C|4|D|6|E|8|I|9|@]|A|@]|B|$F|G]]]]

Efficient solution in C#
<pre class="lang-cs prettyprint-override"><code>public class MyStack {
 private Queue&lt;int&gt; q1 = new Queue&lt;int&gt;();
 private Queue&lt;int&gt; q2 = new Queue&lt;int&gt;();
 private int count = 0;

 /**
 * Initialize your data structure here.
 */
 public MyStack() {
 }

 /**
 * Push element x onto stack.
 */
 public void Push(int x) {
 count++;
 q1.Enqueue(x);
 while (q2.Count &gt; 0) {
 q1.Enqueue(q2.Peek());
 q2.Dequeue();
 }
 var temp = q1;
 q1 = q2;
 q2 = temp;
 }

 /**
 * Removes the element on top of the stack and returns that element.
 */
 public int Pop() {
 count--;
 return q2.Dequeue();
 }

 /**
 * Get the top element.
 */
 public int Top() {
 return q2.Peek();
 }

 /**
 * Returns whether the stack is empty.
 */
 public bool Empty() {
 if (count &gt; 0) return false;
 return true;
 }
}
</code></pre>

entityMap|blocks|key|aoq6v|text|template+
class+stackfmtoq+{
++++queue+q1;
++++queue+q2;
public:
++++void+push(T+data)+{
++++++++while+(!q2.empty())+{
++++++++++++q1.push(q2.front());
++++++++++++q2.pop();
++++++++}
++++++++q2.push(data);
++++++++while+(!q1.empty())+{
++++++++++++q2.push(q1.front());
++++++++++++q1.pop();
++++++++}
++++}
++++T+pop()+{
++++++++if+(q2.empty())+{
++++++++++++cout+<<+"Stack+is+Empty\n";
++++++++++++return+NULL;
++++++++}
++++++++T+ret+=+q2.front();
++++++++q2.pop();
++++++++return+ret;
++++}
++++T+top()+{
++++++++if+(q2.empty())+return+NULL;
++++++++return+q2.front();
++++}
};|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>template &lt;typename T&gt;
class stackfmtoq {
 queue&lt;T&gt; q1;
 queue&lt;T&gt; q2;
public:
 void push(T data) {
 while (!q2.empty()) {
 q1.push(q2.front());
 q2.pop();
 }
 q2.push(data);
 while (!q1.empty()) {
 q2.push(q1.front());
 q1.pop();
 }
 }
 T pop() {
 if (q2.empty()) {
 cout &lt;&lt; &quot;Stack is Empty\n&quot;;
 return NULL;
 }
 T ret = q2.front();
 q2.pop();
 return ret;
 }
 T top() {
 if (q2.empty()) return NULL;
 return q2.front();
 }
};
</code></pre>

entityMap|blocks|key|a4knm|text|import+java.util.Deque;
import+java.util.LinkedList;
import+java.util.Queue;

public+class+ImplementationOfStackUsingTwoQueue+{

++++private+static+Deque+inboxQueue+=+new+LinkedList<>();
++++private+static+Queue+outboxQueue+=+new+LinkedList<>();
++++
++++public+void+pushInStack(Integer+val){
++++++++inboxQueue.add(val);
++++}
++++
++++public+void+popFromStack(){
++++++++
++++++++if(outboxQueue.isEmpty()){
++++++++++++while(!inboxQueue.isEmpty()){
++++++++++++++++outboxQueue.add(inboxQueue.pollLast());
++++++++++++}
++++++++}
++++}
++++
++++public+static+void+main(String[]+args)+{
++++++++
++++++++ImplementationOfStackUsingTwoQueue+obj+=+new+ImplementationOfStackUsingTwoQueue();
++++++++
++++++++obj.pushInStack(1);
++++++++obj.pushInStack(2);
++++++++obj.pushInStack(3);
++++++++obj.pushInStack(4);
++++++++obj.pushInStack(5);
++++++++System.out.println("After+pushing+the+values+in+Queue"+%2B+inboxQueue);
++++++++
++++++++obj.popFromStack();
++++++++System.out.println("After+popping+the+values+from+Queue"+%2B+outboxQueue);++++
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript^0^^$0|$]|1|@$2|3|4|5|6|7|8|E|9|@]|A|@]|B|$C|D]]]]

<pre><code>import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class ImplementationOfStackUsingTwoQueue {

 private static Deque&lt;Integer&gt; inboxQueue = new LinkedList&lt;&gt;();
 private static Queue&lt;Integer&gt; outboxQueue = new LinkedList&lt;&gt;();
 
 public void pushInStack(Integer val){
 inboxQueue.add(val);
 }
 
 public void popFromStack(){
 
 if(outboxQueue.isEmpty()){
 while(!inboxQueue.isEmpty()){
 outboxQueue.add(inboxQueue.pollLast());
 }
 }
 }
 
 public static void main(String[] args) {
 
 ImplementationOfStackUsingTwoQueue obj = new ImplementationOfStackUsingTwoQueue();
 
 obj.pushInStack(1);
 obj.pushInStack(2);
 obj.pushInStack(3);
 obj.pushInStack(4);
 obj.pushInStack(5);
 System.out.println(&quot;After pushing the values in Queue&quot; + inboxQueue);
 
 obj.popFromStack();
 System.out.println(&quot;After popping the values from Queue&quot; + outboxQueue); 
 }
}
</code></pre>

A similar question was asked earlier <a href="https://stackoverflow.com/questions/69192/using-stack-as-queue">there</a>, but the question here is the reverse of it, using two queues as a stack. The question...

Given two queues with their standard operations (<code>enqueue</code>, <code>dequeue</code>, <code>isempty</code>, <code>size</code>), implement a stack with its standard operations (<code>pop</code>, <code>push</code>, <code>isempty</code>, <code>size</code>).

There should be two versions of the solution.

<ul>
<li>Version A: The stack should be efficient when pushing an item; and</li>
<li>Version B: The stack should be efficient when popping an item.</li>
</ul>

I am interested in the algorithm more than any specific language implementations. However, I welcome solutions expressed in languages which I am familiar (<a href="/questions/tagged/java" class="post-tag" title="show questions tagged &#39;java&#39;" rel="tag">java</a>,<a href="/questions/tagged/c%23" class="post-tag" title="show questions tagged &#39;c#&#39;" rel="tag">c#</a>,<a href="/questions/tagged/python" class="post-tag" title="show questions tagged &#39;python&#39;" rel="tag">python</a>,<a href="/questions/tagged/vb" class="post-tag" title="show questions tagged &#39;vb&#39;" rel="tag">vb</a>,<a href="/questions/tagged/javascript" class="post-tag" title="show questions tagged &#39;javascript&#39;" rel="tag">javascript</a>,<a href="/questions/tagged/php" class="post-tag" title="show questions tagged &#39;php&#39;" rel="tag">php</a>).

Implement Stack using Two Queues

Python

Java

 早些时候也提出了类似的问题。there，但这里的问题与之相反，使用两个队列作为堆栈。问题是..。 给定两个队列及其标准操作(enqueue，dequeue，isempty，size)，用它的标准操作实现一个堆栈(pop，push，isempty，size)。 应该有两个解决方案的版本。 版本A：在推送项目时，堆栈应该...

问使用两个队列实现堆栈
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问使用两个队列实现堆栈EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问使用两个队列实现堆栈
EN