Terapkan Stack menggunakan Dua Antrian

142

Pertanyaan serupa diajukan sebelumnya di sana , tetapi pertanyaan di sini adalah kebalikannya, menggunakan dua antrian sebagai tumpukan. Pertanyaan...

Mengingat dua antrian dengan operasi standar ( enqueue, dequeue, isempty, size), menerapkan stack dengan operasi standar ( pop, push, isempty, size).

Seharusnya ada dua versi solusinya.

  • Versi A : Tumpukan harus efisien saat mendorong item; dan
  • Versi B : Tumpukan harus efisien saat memunculkan item.

Saya tertarik pada algoritma lebih dari implementasi bahasa tertentu. Namun, saya menyambut solusi yang dinyatakan dalam bahasa yang saya kenal (,,,,,).

TechTravelThink
sumber
6
Tentu itu! CLRS - 10.1-6 ( tinyurl.com/clrs-ex-10-1-6 )
rampion
1
One Stack, Two Queues memberikan solusi elegan yang Popberfungsi dalam $ O (1) $ dan Pushbekerja dalam $ O (\ sqrt {n}) $ waktu diamortisasi.
hengxin
1
@rampion Sekarang CLRS - 10.1-7. :)
nsane
Posting terkait Ini adalah satu lagi masalah menarik untuk mengimplementasikan stack menggunakan hanya satu antrian di sini .
RBT

Jawaban:

194

Versi A (dorongan efisien):

  • Dorong:
    • enqueue in queue1
  • pop:
    • sementara ukuran antrian1 lebih besar dari 1, pipa item dequeued dari antrian1 ke antrian2
    • dequeue dan kembalikan item terakhir dari queue1, lalu alihkan nama queue1 dan queue2

Versi B (pop efisien):

  • Dorong:
    • enqueue in queue2
    • enqueue semua item dari queue1 di queue2, lalu alihkan nama queue1 dan queue2
  • pop:
    • deqeue dari queue1
Svante
sumber
4
Versi B tampaknya mengalami masalah: apakah maksud Anda enqueue semua item dari queue2 ke queue1 kecuali elemen terakhir (lalu alihkan nama q1 dan q2)?
Icerman
Komentar Icerman masuk akal bagi saya. Versi B dari jawabannya perlu diedit. Saya tidak memiliki izin edit. Bisakah seseorang tolong edit jawaban ini?
eeerahul
2
@eeerahul: Saya sudah memeriksanya lagi, dan jawabannya benar. Pada saat Icerman tampaknya ingin enqueue semua item dari queue2 ke queue1, queue2 hanya terdiri dari item yang baru, sehingga komentar tidak tidak masuk akal.
Svante
Apakah Versi A benar? push 1, push 2, push 3, push 4. pop 4. push 5, push 6, push 7, push 8. pop 8. pop 7. Sepertinya algoritma itu akan muncul 3 bukannya 7. Algoritme Anda sepertinya tepat di pandangan pertama karena kami mungkin dapat beralasan sebagai: pada dasarnya Anda akan selalu muncul elemen enqueued terakhir dalam Antrian 1. Tapi itu adalah elemen dorongan terakhir hanya jika Anda telah mengantri sebelumnya. Jika Anda muncul berkali-kali berturut-turut, itu tidak perlu benar.
user127.0.0.1
1
@ user127.0.0.1: Tampaknya Anda lupa mengganti antrian di akhir setiap pop. Ada invarian bahwa setelah setiap push dan setiap pop, semua item dalam antrian1, sedangkan antrian2 kosong.
Svante
68

Cara termudah (dan mungkin satu-satunya) untuk melakukan ini adalah dengan mendorong elemen baru ke dalam antrian kosong, dan kemudian mengeluarkan yang lain dan enqeuing ke antrian yang sebelumnya kosong. Dengan cara ini yang terbaru selalu ada di depan antrian. Ini akan menjadi versi B, untuk versi A Anda hanya membalikkan proses dengan membagi elemen ke dalam antrian kedua kecuali yang terakhir.

Langkah 0:

"Stack"
+---+---+---+---+---+
|   |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Langkah 1:

"Stack"
+---+---+---+---+---+
| 1 |   |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 1 |   |   |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Langkah 2:

"Stack"
+---+---+---+---+---+
| 2 | 1 |   |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
|   |   |   |   |   |  | 2 | 1 |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+

Langkah 3:

"Stack"
+---+---+---+---+---+
| 3 | 2 | 1 |   |   |
+---+---+---+---+---+

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+
Samuel
sumber
1
Logika untuk ini tidak masuk akal. Ambil langkah dari Langkah 2 ke Langkah 3. Ketika saya "menekan" 3, bagaimana saya bisa mendekor elemen di Antrian B sedemikian rupa sehingga saya mendapatkan 3 2 1 di Antrian A? Jika saya dequeue B ke enqueue A, saya hanya bisa mendapatkan elemen dalam urutan 2, 1. Jika saya kemudian menambahkan 3, saya akan mendapatkan urutan 3, 1, 2. Jika menaruh dorongan saya pertama, dan kemudian dequeue / enqueue, saya mendapatkan 1, 2, 3.
tsurantino
mengapa tidak membuat operasi deque mahal daripada membuat operasi enqueue mahal?
Divij Sehgal
49

Kita dapat melakukan ini dengan satu antrian:

Dorong:

  1. enqueue elemen baru.
  2. Jika njumlah elemen dalam antrian, maka hapus dan masukkan elemen n-1kali.

pop:

  1. dequeue

.

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
+----+----+----+----+----+----+

Implementasi sampel:

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));
  }
}
phoxis
sumber
9
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());
    }
}
Mahmood Akhtar
sumber
Adakah yang bisa menjelaskan login di belakang metode push dalam kode di atas? Sejauh yang saya mengerti, yang pertama untuk loop adalah menghapus semua elemen ke q2 sampai q1 memiliki satu elemen yang tersisa. Tolong koreksi saya jika saya salah.
John
4

Bisakah kita menggunakan satu antrian untuk mengimplementasikan stack? Saya dapat menggunakan dua antrian, tetapi mempertimbangkan satu antrian akan lebih efisien. Ini kodenya:

    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();

    }
Min Zhou
sumber
Saya kira dalam metode pop, untuk kondisi loop harus saya <queLower.Count - 2 saat Anda menginisialisasi variabel i dengan 0.
vignesh
3
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();
   }
}
hiddenboy
sumber
2

Inilah jawaban saya - di mana 'pop' tidak efisien. Tampaknya semua algoritme yang langsung muncul di benak Anda memiliki kompleksitas N, di mana N adalah ukuran daftar: apakah Anda memilih untuk bekerja pada 'pop' atau bekerja pada 'push'

Algoritma tempat daftar diperdagangkan kembali dan keempat mungkin lebih baik, karena perhitungan ukuran tidak diperlukan, meskipun Anda masih perlu mengulang dan membandingkan dengan yang kosong.

Anda dapat membuktikan algoritma ini tidak dapat ditulis lebih cepat dari N dengan mencatat bahwa informasi tentang elemen terakhir dalam antrian hanya tersedia dengan mengetahui ukuran antrian, dan bahwa Anda harus memusnahkan data untuk sampai ke elemen itu, maka antrian ke-2 .

Satu-satunya cara untuk mempercepat ini adalah dengan tidak menggunakan antrian sejak awal.

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
FlipMcF
sumber
2

Berikut adalah solusi saya yang berfungsi untuk O (1) dalam kasus rata-rata. Ada dua antrian: indan out. Lihat pseudocode di bawah:

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)
Vladimir Kostyukov
sumber
2
Di sana Anda menggunakan 2 antrian dan 1 tumpukan untuk mensimulasikan 1 tumpukan!
BeniBela
Apakah maksud Anda tumpukan rekursi implisit?
Vladimir Kostyukov
1

Seperti yang telah disebutkan, bukankah satu antrian akan berhasil? Ini mungkin kurang praktis tetapi sedikit lebih licin.

push(x):
enqueue(x)
for(queueSize - 1)
   enqueue(dequeue())

pop(x):
dequeue()
dhackner
sumber
1

Berikut adalah beberapa kode pseudo sederhana, push adalah O (n), pop / mengintip adalah O (1):

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()
dansalmo
sumber
1

Biarkan S1 dan S2 menjadi dua tumpukan untuk digunakan dalam implementasi antrian.

struct Stack 
{ struct Queue *Q1;
  struct Queue *Q2;
}

Kami memastikan bahwa satu antrian kosong selalu.

Operasi push: Antrian mana pun yang tidak kosong, masukkan elemen di dalamnya.

  • Periksa apakah antrian Q1 kosong atau tidak. Jika Q1 kosong maka Enqueue elemen di dalamnya.
  • Kalau tidak, EnQueue elemen ke Q1.

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

Kompleksitas Waktu: O (1)

Operasi Pop: Transfer elemen n-1 ke antrian lain dan hapus yang terakhir dari antrian untuk melakukan operasi pop.

  • Jika antrian Q1 tidak kosong maka transfer elemen n-1 dari Q1 ke Q2 lalu, DeQueue elemen terakhir dari Q1 dan kembalikan.
  • Jika antrian Q2 tidak kosong maka transfer elemen n-1 dari Q2 ke Q1 lalu, DeQueue elemen terakhir dari Q2 dan kembalikan.

`

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

Kompleksitas Waktu: Menjalankan Waktu operasi pop adalah O (n) karena setiap kali pop dipanggil, kami mentransfer semua elemen dari satu antrian ke oter.

Rahul Gandhi
sumber
1
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
Ankur Lathiya
sumber
1
import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    Queue<Integer> queue1 = new LinkedList<Integer>();
    Queue<Integer> queue2 = new LinkedList<Integer>();

    // 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();
    }
}
Swapnil Gangrade
sumber
0

Inilah satu solusi lagi:

untuk PUSH: -Tambahkan elemen pertama dalam antrian 1. -Ketika menambahkan elemen kedua dan seterusnya, Enqueue elemen dalam antrian 2 terlebih dahulu dan kemudian salin semua elemen dari antrian 1 ke antrian2. -Untuk POP, cukup dekor elemen dari antrian dari Anda memasukkan elemen terakhir.

Begitu,

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

}}

public int pop(){
int popItem=queue2.dequeue();
return popItem;
}'

Ada satu masalah, saya tidak bisa mencari tahu, bagaimana cara mengganti nama antriannya ???

Vince
sumber
0
#include <bits/stdc++.h>
using namespace std;
queue<int>Q;
stack<int>Stk;
void PRINT(stack<int>ss , queue<int>qq) {
    while( ss.size() ) {
        cout << ss.top() << " " ;
        ss.pop();
    }
    puts("");
    while( qq.size() ) {
        cout << qq.front() << " " ;
        qq.pop();
    }
    puts("\n----------------------------------");
}
void POP() {
    queue<int>Tmp ;
    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);
    }
}
Rezwan4029
sumber
1
Tolong beberapa kata, menjelaskan tentang apa kode ini, dan bagaimana benda ini dapat membantu OP dalam memecahkan masalahnya, akan sangat dihargai, bersama dengan contoh kode :-)
nIcE cOw
0

Kode Python Menggunakan Hanya Satu Antrian

 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
Amol Sinha
sumber
1
Cobalah menghindari hanya membuang kode sebagai jawaban dan mencoba menjelaskan apa yang dilakukannya dan mengapa. Kode Anda mungkin tidak jelas bagi orang yang tidak memiliki pengalaman pengkodean yang relevan.
Frits
0

di sini adalah kode kerja lengkap dalam c #:

Telah diimplementasikan dengan Antrian Tunggal,

Dorong:

1. add new element.
2. Remove elements from Queue (totalsize-1) times and add back to the Queue

pop:

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 > 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++)
                    s.Push(i);
                for (int i = 1; i < 3; i++)
                    s.Pop();
                Console.ReadKey();
            }
        }
    }
Jaydeep Shil
sumber
Peduli mengomentari waktu (yang diharapkan / diamortisasi) yang dibutuhkan oleh implementasi Anda sebagai fungsi dari elemen yang saat ini disimpan / jumlah dorongan & muncul?
greybeard
0

Berikut adalah solusi yang sangat sederhana yang menggunakan satu Antrian dan memberikan fungsionalitas seperti Stack.

public class CustomStack<T>
{
    Queue<T> que = new Queue<T>();

    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++)
            {
                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());
    }


}

Jadi di kelas di atas bernama "CustomStack" yang saya lakukan adalah hanya memeriksa antrian untuk kosong, jika kosong kemudian masukkan satu dan sejak saat itu di bangsal masukkan dan kemudian hapus masukkan. Dengan logika ini pertama akan menjadi yang terakhir. Contoh: Dalam antrian saya memasukkan 1 dan sekarang mencoba memasukkan 2. Kedua kalinya hapus 1 dan masukkan lagi sehingga menjadi urutan terbalik.

Terima kasih.

Prityalok Raman
sumber
0

Di bawah ini adalah solusi Java yang sangat sederhana yang mendukung operasi push secara efisien.

Algoritma -

  1. Nyatakan dua Antrian q1 dan q2.

  2. Operasi push - Elemen enqueue untuk mengantri q1.

  3. Operasi sembulan - Pastikan antrian q2 tidak kosong. Jika kosong, maka dequeue semua elemen dari q1 kecuali elemen terakhir dan enqueue ke q2 satu per satu. Dequeue elemen terakhir dari q1 dan simpan sebagai elemen yang muncul. Tukar antrian q1 dan q2. Kembalikan elemen muncul yang tersimpan.

  4. Mengintip operasi - Pastikan antrian q2 tidak kosong. Jika kosong, maka dequeue semua elemen dari q1 kecuali elemen terakhir dan enqueue ke q2 satu per satu. Dequeue elemen terakhir dari q1 dan simpan sebagai elemen yang diintip. Enqueue kembali ke antrian q2 dan menukar antrian q1 dan q2. Kembalikan elemen mengintip yang tersimpan.

Di bawah ini adalah kode untuk algoritma di atas -

class MyStack {

    java.util.Queue<Integer> q1;
    java.util.Queue<Integer> q2;
    int SIZE = 0;

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

    }

    /** 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() && q2.isEmpty();

    }

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

    /** Swap queues q1 and q2 */
    public void swapQueues() {
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
}
Hetal Rachh
sumber
-1

Inilah solusi saya ..

Concept_Behind :: push(struct Stack* S,int data):: Fungsi ini memberikan elemen pertama pada Q1 dan sisanya pada Q2 pop(struct Stack* S):: jika Q2 tidak mengosongkan transfer semua elem ke Q1 dan mengembalikan elem terakhir di Q2 yang lain (yang berarti Q2 kosong) mentransfer semua elem ke Q2 dan mengembalikan elem terakhir di Q1

Efficiency_Behind :: push(struct Stack*S,int data):: O (1) // sejak enqueue tunggal per data pop(struct Stack* S):: O (n) // karena transfer data n-1 terburuk per pop.

#include<stdio.h>
#include<stdlib.h>
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+1) % Q->size ==Q->front);
    }
void enqueue(struct Queue *Q,int data)
{
    if(isFullQueue(Q))
        {
            printf("Queue overflow\n");
            return;}
    Q->rear=Q->rear+1 % 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+1 % 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++){
            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++){
            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("%d",&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));
    }
Dota2
sumber
-1
import java.util.LinkedList;
import java.util.Queue;


public class StackQueue {

    static Queue<Integer> Q1 = new LinkedList<Integer>();
    static Queue<Integer> Q2 = new LinkedList<Integer>();
    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() > 1) {
            Q2.add(Q1.remove());
        }
        int element = Q1.remove();
        Queue<Integer> temp = new LinkedList<Integer>();
        temp = Q1;
        Q1 = Q2;
        Q2 = temp;
        return element;
        }
    }
}
Rajnish Kumar Jha
sumber
Daftar tertaut Java berfungsi sebagai deque. Jawaban ini tidak masuk akal.
dfeuer
-1
#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++;
    }
    return item;
}
void queuePush(Queue *q, int val) {
    if (queueIsFull(q)) {
        printf("\nQUEUE is FULL\n");
        return;
    }
    if (queueIsEmpty(q)) {
        q->front++;
        q->rear++;
    } else {
        q->rear++;
    }
    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%d", stackTop((Stack*)&s));
  stackDestroy((Stack*)&s);
  return 0;
}
seth
sumber
Dinding kode tanpa komentar atau penjelasan adalah jawaban yang buruk.
Richard