|
1 | | -packagecom.fishercoder.solutions; |
2 | | - |
3 | 1 | importjava.util.LinkedList; |
4 | 2 | importjava.util.Queue; |
5 | | -/** |
6 | | - * 225. Implement Stack using Queues |
7 | | - * |
8 | | - * Implement the following operations of a stack using queues. |
9 | | -
|
10 | | - push(x) -- Push element x onto stack. |
11 | | - pop() -- Removes the element on top of the stack. |
12 | | - top() -- Get the top element. |
13 | | - empty() -- Return whether the stack is empty. |
14 | | -
|
15 | | - Notes: |
16 | | - You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid. |
17 | | - Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. |
18 | | - You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). |
19 | | - Update (2015-06-11): |
20 | | - The class name of the Java function had been updated to MyStack instead of Stack.*/ |
21 | | - |
22 | | -publicclass_225 { |
23 | | - |
24 | | -publicstaticclassSolution1 { |
25 | | -classMyStack { |
26 | | - |
27 | | -Queue<Integer>q =newLinkedList(); |
28 | | - |
29 | | -// Push element x onto stack. |
30 | | -publicvoidpush(intx) { |
31 | | -q.offer(x); |
32 | | -for (inti =1;i <q.size();i++) { |
33 | | -q.offer(q.remove()); |
34 | | - } |
35 | | - } |
36 | | - |
37 | | -// Removes the element on top of the stack. |
38 | | -publicvoidpop() { |
39 | | -q.poll(); |
40 | | - } |
41 | | - |
42 | | -// Get the top element. |
43 | | -publicinttop() { |
44 | | -returnq.peek(); |
45 | | - } |
46 | 3 |
|
47 | | -// Return whether the stack is empty. |
48 | | -publicbooleanempty() { |
49 | | -returnq.isEmpty(); |
50 | | - } |
51 | | - } |
52 | | - } |
| 4 | +publicclassMyStack { |
| 5 | +publicQueue<Integer>queue1; |
| 6 | +publicQueue<Integer>queue2; |
| 7 | +publicintflag; |
| 8 | +publicintsize; |
| 9 | +publicMyStack() { |
| 10 | +queue1=newLinkedList<Integer>(); |
| 11 | +queue2=newLinkedList<Integer>(); |
| 12 | +flag=1; |
| 13 | +size=0; |
| 14 | + } |
| 15 | + |
| 16 | +publicvoidpush(intx) { |
| 17 | +if(flag==1){ |
| 18 | +queue1.offer(x); |
| 19 | + }else{ |
| 20 | +queue2.offer(x); |
| 21 | + } |
| 22 | +size++; |
| 23 | + } |
| 24 | + |
| 25 | +publicintpop() { |
| 26 | +intvalue; |
| 27 | +if(flag==1){ |
| 28 | +while(queue1.size()>1){ |
| 29 | +queue2.offer(queue1.poll()); |
| 30 | + } |
| 31 | +value=queue1.poll(); |
| 32 | +flag=2; |
| 33 | + }else{ |
| 34 | +while(queue2.size()>1){ |
| 35 | +queue1.offer(queue2.poll()); |
| 36 | + } |
| 37 | +value=queue2.poll(); |
| 38 | +flag=1; |
| 39 | + } |
| 40 | +size--; |
| 41 | +returnvalue; |
| 42 | + } |
| 43 | + |
| 44 | +publicinttop() { |
| 45 | +if(flag==1){ |
| 46 | +while(queue1.size()>1){ |
| 47 | +queue2.offer(queue1.poll()); |
| 48 | + } |
| 49 | +intvalue=queue1.poll(); |
| 50 | +queue2.offer(value); |
| 51 | +flag=2; |
| 52 | +returnvalue; |
| 53 | + }else{ |
| 54 | +while(queue2.size()>1){ |
| 55 | +queue1.offer(queue2.poll()); |
| 56 | + } |
| 57 | +intvalue=queue2.poll(); |
| 58 | +queue1.offer(value); |
| 59 | +flag=1; |
| 60 | +returnvalue; |
| 61 | + } |
| 62 | + } |
| 63 | + |
| 64 | +publicbooleanempty() { |
| 65 | +returnsize==0?true:false; |
| 66 | + } |
53 | 67 | } |