दिलचस्प पोस्ट
Com.google.android.gms नहीं मिल सका: प्ले-सेवाओं: 3.1.5 9 3.2.25 4.0.30 4.1.32 4.2.40 4.2.42 4.3.23 4.4.52 5.0.77 5.0.8 9 5.2.08 6.1। 11 6.1.71 6.5.87 मर्ज किए गए सभी गिट शाखाओं को मैं कैसे हटा सकता हूं? संकलित नहीं किए गए नेस्टेड तर्क मैं जावास्क्रिप्ट के साथ एक लिंक पर प्रोग्राममैटिक रूप से कैसे क्लिक करूं? कैसे jQuery में पिछले बच्चे तत्व का चयन करें? आईओएस – एक दृश्य के माध्यम से सभी को छूते हैं डीएनएस। गेटहोस्ट एंट्री से आईपीवी 4 पते प्राप्त करें अद्वितीय / यादृच्छिक नामों के साथ फाइलें स्टोर करें क्यों मुख्य विधि में SwingUtilities.invokeLater का उपयोग करें? एक UILabel में पाठ की पिक्सेल की चौड़ाई जावास्क्रिप्ट स्विच बनाम अगर … और अगर … और एक बड़ी SQL स्क्रिप्ट निष्पादित करें (GO कमांड्स के साथ) किसी अन्य ऐप से सेटिंग ऐप खोलना जब तक फ़ाइल पूरी तरह से लिखित नहीं हो जाती तब तक प्रतीक्षा करें कर्सर को जावास्क्रिप्ट प्रतिलिपि में इनपुट फील्ड के अंत तक कूदने से रोकें

दो स्टैक का प्रयोग करके कतार कैसे कार्यान्वित करें?

मान लें कि हमारे पास दो स्टैक हैं और कोई अन्य अस्थायी चर नहीं है।

क्या केवल दो स्टैक का प्रयोग करके कतार डेटा संरचना "निर्माण" करना संभव है?

वेब के समाधान से एकत्रित समाधान "दो स्टैक का प्रयोग करके कतार कैसे कार्यान्वित करें?"

2 स्टैक रखें, चलो उन्हें inbox और outbox कहते हैं।

एन्क्यू :

  • नए तत्व को inbox पर पुश करें

डेक्यू :

  • यदि outbox रिक्त है, तो प्रत्येक तत्व को inbox से पॉप करके और इसे outbox पर धकेलने से outbox

  • पॉप और outbox से शीर्ष तत्व लौटाएं

इस पद्धति का उपयोग करते हुए, प्रत्येक तत्व प्रत्येक स्टैक में एक बार होगा – प्रत्येक तत्व का अर्थ दो बार धकेल दिया जाएगा और दो बार पॉप कर दिया जाएगा, जिससे निरंतर समय-समय पर परिचालन किया जाएगा।

यहां जावा में एक कार्यान्वयन है:

 public class Queue<E> { private Stack<E> inbox = new Stack<E>(); private Stack<E> outbox = new Stack<E>(); public void queue(E item) { inbox.push(item); } public E dequeue() { if (outbox.isEmpty()) { while (!inbox.isEmpty()) { outbox.push(inbox.pop()); } } return outbox.pop(); } } 

ए – एक स्टैक रिवर्स कैसे करें

दो स्टैक का उपयोग करने के लिए क्यूई का निर्माण कैसे करें, आपको समझना चाहिए कि स्टैक क्रिस्टल को कैसे साफ़ करना है। याद रखें कि स्टैक कैसे काम करता है, यह आपकी रसोई पर डिश स्टैक के समान है। आखिरी धोया वाला डिब्बे साफ स्टैक के शीर्ष पर होगा, जिसे कंप्यूटर विज्ञान में एल एस्ट आई एन एफ इस्ट ओट (लिफ़ो) कहा जाता है।

नीचे की तरह एक बोतल की तरह हमारे ढेर की कल्पना कर सकते हैं;

यहां छवि विवरण दर्ज करें

यदि हम क्रमशः 1,2,3 को पूर्णांकित करते हैं, तो 3 स्टैक के शीर्ष पर होंगे। क्योंकि पहले 1 को धक्का दिया जाएगा, फिर 2 को 1 के शीर्ष पर रखा जाएगा। अंत में, 3 को स्टैक के शीर्ष पर रखा जाएगा और हमारे स्टैक की नवीनतम स्थिति को एक बोतल के रूप में दर्शाया जाएगा;

यहां छवि विवरण दर्ज करें

बोतल के रूप में अब हमारे स्टैक का प्रतिनिधित्व किया गया है, मूल्य 3,2,1 के साथ आबादी है और हम स्टैक को रिवर्स करना चाहते हैं ताकि स्टैक का शीर्ष तत्व 1 हो और ढेर के नीचे वाला तत्व 3 हो। हम क्या कर सकते हैं? हम बोतल ले जा सकते हैं और इसे उल्टा रख सकते हैं ताकि सभी मान क्रम में उलटाए जाएं?

यहां छवि विवरण दर्ज करें

हाँ हम ऐसा कर सकते हैं, लेकिन यह एक बोतल है। उसी प्रक्रिया को करने के लिए, हमें दूसरी स्टैक की आवश्यकता है जो रिवर्स ऑर्डर में पहले स्टैक तत्वों को स्टोर करने वाला है। चलो हमारे आबादी वाले ढेर को छोड़ दिया और दायें से हमारी नई खाली ढेर। तत्वों के क्रम को उलटने के लिए, हम प्रत्येक तत्व को बाएं स्टैक से पॉप करते हैं, और उन्हें सही ढेर पर धक्का देते हैं। आप देख सकते हैं कि हम नीचे दी गई छवि पर ऐसा क्यों करते हैं;

यहां छवि विवरण दर्ज करें

तो हम जानते हैं कि एक स्टैक को कैसे उलट करना है।

बी – एक पंक्ति के रूप में दो ढेर का उपयोग करना

पिछले भाग में, मैंने समझाया है कि हम स्टैक तत्वों के क्रम को कैसे उलट सकते हैं। यह महत्वपूर्ण था, क्योंकि अगर हम स्टैक पर तत्वों को धक्का और पॉप करते हैं, तो आउटपुट बिल्कुल कतार के रिवर्स ऑर्डर में होगा एक उदाहरण के बारे में सोचकर, चलो एक स्टैक में पूर्णांक {1, 2, 3, 4, 5} की सरणी को दबाएं। यदि हम तत्वों को पॉप करते हैं और स्टैक खाली होने तक उन्हें प्रिंट करते हैं, तो हम आदेश को धक्का देने के रिवर्स ऑर्डर में सरणी प्राप्त करेंगे, जो कि {5, 4, 3, 2, 1} , उसी इनपुट के लिए याद रखें, अगर हम कतार खाली है जब तक कतार dequeue, उत्पादन होगा {1, 2, 3, 4, 5} । तो यह स्पष्ट है कि तत्वों के एक ही इनपुट ऑर्डर के लिए, कतार का आउटपुट स्टैक के आउटपुट का बिल्कुल विपरीत है। जैसा कि हम जानते हैं कि एक अतिरिक्त स्टैक का इस्तेमाल करते हुए स्टैक को कैसे उलट करना है, हम दो स्टैक का उपयोग कर एक कतार का निर्माण कर सकते हैं।

हमारी कतार मॉडल में दो स्टैक शामिल होंगे। एक स्टैक enqueue ऑपरेशन के लिए इस्तेमाल किया जाएगा (बाईं ओर # 1 स्टैक, इनपुट स्टैक कहा जाएगा), dequeue ऑपरेशन (दाईं ओर स्टैक # 2, आउटपुट स्टैक के रूप में कॉल किया जाएगा) के लिए एक और स्टैक का उपयोग किया जाएगा नीचे दी गई छवि देखें;

यहां छवि विवरण दर्ज करें

हमारा छद्म कोड नीचे दिया गया है;


एन्क्यू ऑपरेशन

 Push every input element to the Input Stack 

डेक्यू ऑपरेशन

 If ( Output Stack is Empty) pop every element in the Input Stack and push them to the Output Stack until Input Stack is Empty pop from Output Stack 

चलो क्रमशः integers {1, 2, 3} enqueue। इंटीजर्स को इनपुट स्टैक ( स्टैक # 1 ) पर धकेल दिया जाएगा जो बाईं तरफ स्थित है;

यहां छवि विवरण दर्ज करें

तो अगर हम एक dequeue ऑपरेशन निष्पादित करेंगे तो क्या होगा? जब भी कोई डेक्यू ऑपरेशन निष्पादित होता है, तो कतार यह जांचने जा रहा है कि आउटपुट स्टैक खाली है या नहीं (ऊपर छद्म-कोड देखें) यदि आउटपुट स्टैक खाली है, तो इनपुट स्टैक आउटपुट पर निकाला जा रहा है ताकि तत्व इनपुट स्टैक का उलट हो जाएगा मान वापस करने से पहले, कतार की स्थिति नीचे दी जाएगी;

यहां छवि विवरण दर्ज करें

आउटपुट स्टैक (स्टैक # 2) में तत्वों का क्रम देखें यह स्पष्ट है कि हम आउटपुट स्टैक से तत्वों को पॉप कर सकते हैं ताकि आउटपुट एक जैसा हो, जैसा कि हम कतार से हटाए गए हैं इस प्रकार, यदि हम दो dequeue परिचालन निष्पादित करते हैं, तो पहले हम क्रमशः {1, 2} प्राप्त करेंगे। फिर तत्व 3 आउटपुट स्टैक का एकमात्र तत्व होगा, और इनपुट स्टैक खाली होगा। यदि हम तत्व 4 और 5 को एंज्यू करते हैं, तो कतार की स्थिति निम्नानुसार होगी;

यहां छवि विवरण दर्ज करें

अब आउटपुट स्टैक खाली नहीं है, और अगर हम एक डेक्यू ऑपरेशन निष्पादित करते हैं, तो आउटपुट स्टैक से केवल 3 ही पॉप आउट हो जाएंगे। तब राज्य को नीचे देखा जाएगा;

यहां छवि विवरण दर्ज करें

दोबारा, अगर हम पहले डेक्यू ऑपरेशन पर दो और डेक्यू ऑपरेशन्स निष्पादित करते हैं, तो क्यू जांच करेगी कि आउटपुट स्टैक खाली है, जो सच है। फिर इनपुट स्टैक के तत्वों को पॉप आउट करें और उन्हें आउटपुट स्टैक को इनट्यूप करें ताकि इनपुट स्टैक रिक्त हो, फिर कतार की स्थिति नीचे दी जाएगी;

यहां छवि विवरण दर्ज करें

देखने के लिए आसान, दो dequeue कार्यों का उत्पादन होगा {4, 5}

सी – दो ढेर के साथ निर्मित कतार का कार्यान्वयन

यहां जावा में एक कार्यान्वयन है मैं स्टैक के मौजूदा कार्यान्वयन का उपयोग नहीं करने जा रहा हूं, इसलिए उदाहरण यहां पहिया को फिर से बदलने वाला है;

सी -1) मायस्टैक क्लास: एक सरल स्टैक कार्यान्वयन

 public class MyStack<T> { // inner generic Node class private class Node<T> { T data; Node<T> next; public Node(T data) { this.data = data; } } private Node<T> head; private int size; public void push(T e) { Node<T> newElem = new Node(e); if(head == null) { head = newElem; } else { newElem.next = head; head = newElem; // new elem on the top of the stack } size++; } public T pop() { if(head == null) return null; T elem = head.data; head = head.next; // top of the stack is head.next size--; return elem; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void printStack() { System.out.print("Stack: "); if(size == 0) System.out.print("Empty !"); else for(Node<T> temp = head; temp != null; temp = temp.next) System.out.printf("%s ", temp.data); System.out.printf("\n"); } } 

सी – 2) मायक्वाइज क्लास: क्यूई इंप्लिमेंटेशन दो स्टैक का उपयोग करना

 public class MyQueue<T> { private MyStack<T> inputStack; // for enqueue private MyStack<T> outputStack; // for dequeue private int size; public MyQueue() { inputStack = new MyStack<>(); outputStack = new MyStack<>(); } public void enqueue(T e) { inputStack.push(e); size++; } public T dequeue() { // fill out all the Input if output stack is empty if(outputStack.isEmpty()) while(!inputStack.isEmpty()) outputStack.push(inputStack.pop()); T temp = null; if(!outputStack.isEmpty()) { temp = outputStack.pop(); size--; } return temp; } public int size() { return size; } public boolean isEmpty() { return size == 0; } } 

सी – 3) डेमो कोड

 public class TestMyQueue { public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<>(); // enqueue integers 1..3 for(int i = 1; i <= 3; i++) queue.enqueue(i); // execute 2 dequeue operations for(int i = 0; i < 2; i++) System.out.println("Dequeued: " + queue.dequeue()); // enqueue integers 4..5 for(int i = 4; i <= 5; i++) queue.enqueue(i); // dequeue the rest while(!queue.isEmpty()) System.out.println("Dequeued: " + queue.dequeue()); } } 

सी – 4) नमूना आउटपुट

 Dequeued: 1 Dequeued: 2 Dequeued: 3 Dequeued: 4 Dequeued: 5 

आप केवल एक स्टैक का उपयोग करके एक कतार का अनुकरण कर सकते हैं। दूसरी (अस्थायी) स्टैक को सम्मिलित विधि पर रिकर्सिव कॉल के कॉल स्टैक द्वारा सिम्युटेड किया जा सकता है।

सिद्धांत एक ही रहता है जब कतार में एक नया तत्व डालता है:

  • अपने ऑर्डर को बदलने के लिए आपको तत्वों को एक स्टैक से दूसरे अस्थायी स्टैक तक स्थानांतरित करना होगा।
  • फिर अस्थायी स्टैक पर डालने के लिए नया तत्व डालें
  • फिर तत्वों को मूल स्टैक पर वापस स्थानांतरित करें
  • नया तत्व स्टैक के नीचे होगा, और सबसे पुराना तत्व शीर्ष पर है (पहले पॉप होना है)

केवल एक स्टैक का उपयोग कर एक पंक्ति वर्ग, निम्नानुसार होगा:

 public class SimulatedQueue<E> { private java.util.Stack<E> stack = new java.util.Stack<E>(); public void insert(E elem) { if (!stack.empty()) { E topElem = stack.pop(); insert(elem); stack.push(topElem); } else stack.push(elem); } public E remove() { return stack.pop(); } } 

ब्रायन का जवाब क्लासिक रूप से सही है वास्तव में, यह लगातार निरंतर समय के साथ सतत कार्यात्मक कतारों को लागू करने के सर्वोत्तम तरीकों में से एक है। यह इसलिए है क्योंकि कार्यात्मक प्रोग्रामिंग में हमारे पास एक बहुत अच्छी लगातार स्टैक (लिंक्ड सूची) है। ब्रायन ने जिस तरीके से दो सूचियों का इस्तेमाल किया है, उसका वर्णन करते हुए, नकल की अश्लील राशि की आवश्यकता के बिना एक तेज कतार को लागू करना संभव है।

एक छोटी सी के रूप में, यह साबित करना संभव है कि आप दो स्टैक के साथ कुछ भी कर सकते हैं। ऐसा इसलिए है क्योंकि दो-स्टैक ऑपरेशन पूरी तरह से एक सार्वभौमिक ट्यूरिंग मशीन की परिभाषा को पूरा करता है। हालांकि, जैसा कि फॉरट दर्शाता है, यह हमेशा आसान नहीं होता है। 🙂

समय की जटिलताओं बदतर होगी, यद्यपि। एक अच्छी कतार का कार्यान्वयन निरंतर समय में सब कुछ करता है

संपादित करें

निश्चित नहीं है कि मेरा उत्तर नीचे क्यों उतारा गया है यदि हम कार्यक्रम करते हैं, तो हम समय की जटिलता की परवाह करते हैं, और एक पंक्ति बनाने के लिए दो मानक स्टैक का प्रयोग करना अक्षम है। यह एक बहुत मान्य और प्रासंगिक बिंदु है। अगर किसी और को यह अधिक गिरावट की आवश्यकता महसूस हो रही है, तो मुझे यह जानने में दिलचस्पी होगी कि क्यों

थोड़ा और विस्तार : दो स्टैक का प्रयोग सिर्फ एक कतार के मुकाबले खराब क्यों है: यदि आप दो स्टैक का उपयोग करते हैं, और किसी को डेक्यू आउट करते हैं, तो आउटबॉक्स रिक्त है, आपको इनबॉक्स के नीचे जाने के लिए रैखिक समय की आवश्यकता है (जैसा कि आप देख सकते हैं डेव के कोड में)

आप सिंगल-लिंक्ड सूची के रूप में एक कतार को लागू कर सकते हैं (प्रत्येक तत्व अगले-डाला तत्व को इंगित करता है), धक्का देने के लिए अंतिम डालने वाले तत्व में एक अतिरिक्त सूचक रखते हुए (या इसे एक चक्रीय सूची बनाते हुए)। इस डेटा संरचना पर कतार और डेक्यू को कार्यान्वित करना निरंतर समय में करना आसान है। यह सबसे बुरा-मामला निरंतर समय है, नहीं amortized और, जैसा कि टिप्पणियां इस स्पष्टीकरण के लिए पूछने लगती हैं, सबसे खराब स्थिति निरंतर समय amortized निरंतर समय से कड़ाई से बेहतर है।

कतार को कार्यान्वित करने के लिए क्यू और स्टैक का प्रयोग करें जिसे q1 को लागू करने के लिए स्टैक 1 और स्टैक 2 करें।

क्यू दो तरीकों से लागू किया जा सकता है:

विधि 1 (enQueue ऑपरेशन महंगा बनाकर)

यह विधि यह सुनिश्चित करती है कि नये प्रविष्ट किए गए तत्व हमेशा स्टैक 1 के शीर्ष पर है, जिससे कि डेक्यूई ऑपरेशन केवल स्टैक 1 से चले गए। स्टैक 1 के शीर्ष पर तत्व को डालने के लिए, स्टैक 2 का उपयोग किया जाता है।

 enQueue(q, x) 1) While stack1 is not empty, push everything from stack1 to stack2. 2) Push x to stack1 (assuming size of stacks is unlimited). 3) Push everything back to stack1. deQueue(q) 1) If stack1 is empty then error 2) Pop an item from stack1 and return it. 

विधि 2 (डेकुएयू ऑपरेशन महंगा बनाकर)

इस पद्धति में, एन-क्यू ऑपरेशन में, नए तत्व को स्टैक 1 के शीर्ष पर दर्ज किया गया है। डे-क्यूई ऑपरेशन में, अगर स्टैक 2 खाली है तो सभी तत्व स्टैक 2 पर ले जाया जाता है और अंत में स्टैक 2 के शीर्ष पर लौटा जाता है

 enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 3) Pop the element from stack2 and return it. 

विधि 2 निश्चित रूप से विधि 1 से बेहतर है। विधि 1 सभी दो तत्वों को दो पंक्तियों में ले जाता है, जबकि विधि 2 (डेकुए्यू ऑपरेशन में) एक बार तत्वों को स्थानांतरित करता है और तत्वों को स्थानांतरित करता है, यदि केवल स्टैक 2 खाली हो।

कतार में दो ढेर को स्टैक 1 और स्टैक 2 के रूप में परिभाषित किया गया है।

एन्क्यू: एयूकेयड तत्व हमेशा स्टैक 1 में धकेल दिया जाता है

Dequeue: स्टैक 2 के शीर्ष को पॉप आउट किया जा सकता है क्योंकि यह पहले तत्व को पंक्ति में डाला जाता है जब स्टैक 2 खाली नहीं होता है। जब स्टैक 2 खाली है, हम सभी तत्वों को स्टैक 1 से पॉप करते हैं और उन्हें स्टैक 2 में एक-एक करके धक्का देते हैं। कतार में पहला तत्व स्टैक 1 के नीचे धकेल दिया जाता है। चूंकि यह स्टैक 2 के शीर्ष पर है, इसे पॉपिंग और ऑपरेशन धक्का जाने के बाद सीधे बाहर किया जा सकता है।

निम्न एक ही सी ++ नमूना कोड है:

 template <typename T> class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; }; template<typename T> void CQueue<T>::appendTail(const T& element) { stack1.push(element); } template<typename T> T CQueue<T>::deleteHead() { if(stack2.size()<= 0) { while(stack1.size()>0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.size() == 0) throw new exception("queue is empty"); T head = stack2.top(); stack2.pop(); return head; } 

यह समाधान मेरे ब्लॉग से लिया गया है मेरे ब्लॉग वेबपृष्ठ में चरण-दर-चरण ऑपरेशन सिमुलेशन के साथ अधिक विस्तृत विश्लेषण उपलब्ध है

नीचे तत्व प्राप्त करने के लिए आपको पहले स्टैक से सब कुछ पॉप करना होगा। फिर उन्हें हर "dequeue" ऑपरेशन के लिए दूसरी स्टैक पर वापस डाल दिया।

सी # डेवलपर के लिए यहां पूरा प्रोग्राम है:

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace QueueImplimentationUsingStack { class Program { public class Stack<T> { public int size; public Node<T> head; public void Push(T data) { Node<T> node = new Node<T>(); node.data = data; if (head == null) head = node; else { node.link = head; head = node; } size++; Display(); } public Node<T> Pop() { if (head == null) return null; else { Node<T> temp = head; //temp.link = null; head = head.link; size--; Display(); return temp; } } public void Display() { if (size == 0) Console.WriteLine("Empty"); else { Console.Clear(); Node<T> temp = head; while (temp!= null) { Console.WriteLine(temp.data); temp = temp.link; } } } } public class Queue<T> { public int size; public Stack<T> inbox; public Stack<T> outbox; public Queue() { inbox = new Stack<T>(); outbox = new Stack<T>(); } public void EnQueue(T data) { inbox.Push(data); size++; } public Node<T> DeQueue() { if (outbox.size == 0) { while (inbox.size != 0) { outbox.Push(inbox.Pop().data); } } Node<T> temp = new Node<T>(); if (outbox.size != 0) { temp = outbox.Pop(); size--; } return temp; } } public class Node<T> { public T data; public Node<T> link; } static void Main(string[] args) { Queue<int> q = new Queue<int>(); for (int i = 1; i <= 3; i++) q.EnQueue(i); // q.Display(); for (int i = 1; i < 3; i++) q.DeQueue(); //q.Display(); Console.ReadKey(); } } } 
 public class QueueUsingStacks<T> { private LinkedListStack<T> stack1; private LinkedListStack<T> stack2; public QueueUsingStacks() { stack1=new LinkedListStack<T>(); stack2 = new LinkedListStack<T>(); } public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest ) { while(source.Head!=null) { dest.Push(source.Head.Data); source.Head = source.Head.Next; } } public void Enqueue(T entry) { stack1.Push(entry); } public T Dequeue() { T obj; if (stack2 != null) { Copy(stack1, stack2); obj = stack2.Pop(); Copy(stack2, stack1); } else { throw new Exception("Stack is empty"); } return obj; } public void Display() { stack1.Display(); } } 

हर एन्क्यू ऑपरेशन के लिए, हम स्टैक 1 के शीर्ष पर जोड़ते हैं। प्रत्येक dequeue के लिए, हम स्टैक 1 की सामग्री को स्टैक 2 में खाली करते हैं, और स्टैक के ऊपर तत्व हटा देते हैं। समय की जटिलता dequeue के लिए ओ (एन) है, जैसा कि हमें स्टैक 1 को स्टैक 2 में कॉपी करना है। एन्क्यू की समय की जटिलता एक नियमित स्टैक के समान है

 // Two stacks s1 Original and s2 as Temp one private Stack<Integer> s1 = new Stack<Integer>(); private Stack<Integer> s2 = new Stack<Integer>(); /* * Here we insert the data into the stack and if data all ready exist on * stack than we copy the entire stack s1 to s2 recursively and push the new * element data onto s1 and than again recursively call the s2 to pop on s1. * * Note here we can use either way ie We can keep pushing on s1 and than * while popping we can remove the first element from s2 by copying * recursively the data and removing the first index element. */ public void insert( int data ) { if( s1.size() == 0 ) { s1.push( data ); } else { while( !s1.isEmpty() ) { s2.push( s1.pop() ); } s1.push( data ); while( !s2.isEmpty() ) { s1.push( s2.pop() ); } } } public void remove() { if( s1.isEmpty() ) { System.out.println( "Empty" ); } else { s1.pop(); } } 

मैं इस प्रश्न के उत्तर में जाने के लिए उत्तर दूंगा क्योंकि Go के मानक लाइब्रेरी में बहुत सारे संग्रह नहीं हैं I

चूंकि एक स्टैक वास्तव में लागू करना आसान है, इसलिए मैंने सोचा कि मैं एक डबल समाप्ति कतार को पूरा करने के लिए दो स्टैक का उपयोग करने की कोशिश करूँगा। बेहतर ढंग से समझने के लिए कि मैं अपने जवाब पर कैसे आया हूं, मैंने दो भागों में कार्यान्वयन को अलग कर दिया है, पहला हिस्सा उम्मीद से समझना आसान है, लेकिन यह अधूरा है

 type IntQueue struct { front []int back []int } func (q *IntQueue) PushFront(v int) { q.front = append(q.front, v) } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[0] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { q.back = q.back[1:] } } func (q *IntQueue) PushBack(v int) { q.back = append(q.back, v) } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[0] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { q.front = q.front[1:] } } 

यह मूल रूप से दो ढेर है जहां हम ढेर के नीचे एक-दूसरे के द्वारा छेड़छाड़ की अनुमति देते हैं। मैंने एसटीएल नामकरण सम्मेलनों का भी उपयोग किया है, जहां स्टैक के पारंपरिक धक्का, पॉप, पीक ऑपरेशन के सामने / बैक उपसर्ग है, चाहे वे कतार के आगे या पीछे देखें।

उपरोक्त कोड के साथ यह मुद्दा यह है कि यह बहुत कुशलता से स्मृति का उपयोग नहीं करता है असल में, जब तक आप अंतरिक्ष से बाहर नहीं चलते तब तक यह अंतहीन होता है यह वास्तव में खराब है इसके लिए तय करना है कि जब भी संभव हो तो स्टैक स्पेस के नीचे का उपयोग करें। हमें इसे ट्रैक करने के लिए ऑफसेट शुरू करना होगा क्योंकि गो में एक टुकड़ा एक बार सिकुड़ते सामने सामने नहीं बढ़ सकता है।

 type IntQueue struct { front []int frontOffset int back []int backOffset int } func (q *IntQueue) PushFront(v int) { if q.backOffset > 0 { i := q.backOffset - 1 q.back[i] = v q.backOffset = i } else { q.front = append(q.front, v) } } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[q.backOffset] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { if len(q.back) > 0 { q.backOffset++ } else { panic("Cannot pop front of empty queue.") } } } func (q *IntQueue) PushBack(v int) { if q.frontOffset > 0 { i := q.frontOffset - 1 q.front[i] = v q.frontOffset = i } else { q.back = append(q.back, v) } } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[q.frontOffset] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { if len(q.front) > 0 { q.frontOffset++ } else { panic("Cannot pop back of empty queue.") } } } 

यह बहुत छोटे कार्य हैं लेकिन उनमें से 6 फ़ंक्शन के 3 दूसरे के दर्पण हैं।

सी # में समाधान

  public class Queue<T> where T : class { private Stack<T> input = new Stack<T>(); private Stack<T> output = new Stack<T>(); public void Enqueue(T t) { input.Push(t); } public T Dequeue() { if (output.Count == 0) { while (input.Count != 0) { output.Push(input.Pop()); } } return output.Pop(); } } 

यहां लिंक में लिंक का उपयोग करके जावा में मेरा समाधान है

 class queue<T>{ static class Node<T>{ private T data; private Node<T> next; Node(T data){ this.data = data; next = null; } } Node firstTop; Node secondTop; void push(T data){ Node temp = new Node(data); temp.next = firstTop; firstTop = temp; } void pop(){ if(firstTop == null){ return; } Node temp = firstTop; while(temp != null){ Node temp1 = new Node(temp.data); temp1.next = secondTop; secondTop = temp1; temp = temp.next; } secondTop = secondTop.next; firstTop = null; while(secondTop != null){ Node temp3 = new Node(secondTop.data); temp3.next = firstTop; firstTop = temp3; secondTop = secondTop.next; } } 

}

नोट: इस मामले में, पॉप ऑपरेशन बहुत समय लगता है। इसलिए मैं दो स्टैक का उपयोग कर एक कतार बनाने का सुझाव नहीं दूँगा।

O(1) dequeue() , जो पायथनिक के उत्तर के समान है:

 // time: O(n), space: O(n) enqueue(x): if stack.isEmpty(): stack.push(x) return temp = stack.pop() enqueue(x) stack.push(temp) // time: O(1) x dequeue(): return stack.pop() 

O(1) enqueue() (इस पद में इस उत्तर में इसका उल्लेख नहीं किया गया है, इसलिए यह जवाब), जो बुलबुले को पीछे की तरफ का उपयोग करता है और सबसे नीचे की वस्तु वापस लौटाता है।

 // O(1) enqueue(x): stack.push(x) // time: O(n), space: O(n) x dequeue(): temp = stack.pop() if stack.isEmpty(): x = temp else: x = dequeue() stack.push(temp) return x 

जाहिर है, यह एक अच्छा कोडन व्यायाम है क्योंकि यह अक्षम लेकिन सुरुचिपूर्ण है।

स्विफ्ट में दो स्टैक का उपयोग करते हुए एक कतार का कार्यान्वयन:

 struct Stack<Element> { var items = [Element]() var count : Int { return items.count } mutating func push(_ item: Element) { items.append(item) } mutating func pop() -> Element? { return items.removeLast() } func peek() -> Element? { return items.last } } struct Queue<Element> { var inStack = Stack<Element>() var outStack = Stack<Element>() mutating func enqueue(_ item: Element) { inStack.push(item) } mutating func dequeue() -> Element? { fillOutStack() return outStack.pop() } mutating func peek() -> Element? { fillOutStack() return outStack.peek() } private mutating func fillOutStack() { if outStack.count == 0 { while inStack.count != 0 { outStack.push(inStack.pop()!) } } } } 

दो java.util.Stack ऑब्जेक्ट्स का उपयोग कर कतार का कार्यान्वयन:

 public final class QueueUsingStacks<E> { private final Stack<E> iStack = new Stack<>(); private final Stack<E> oStack = new Stack<>(); public void enqueue(E e) { iStack.push(e); } public E dequeue() { if (oStack.isEmpty()) { if (iStack.isEmpty()) { throw new NoSuchElementException("No elements present in Queue"); } while (!iStack.isEmpty()) { oStack.push(iStack.pop()); } } return oStack.pop(); } public boolean isEmpty() { if (oStack.isEmpty() && iStack.isEmpty()) { return true; } return false; } public int size() { return iStack.size() + oStack.size(); } }