Penumpukan implementasi menggunakan dua antrian

Pertanyaan serupa ditanyakan sebelumnya di sana , tetapi pertanyaannya terbalik, menggunakan dua antrian sebagai tumpukan. Pertanyaannya adalah ...

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

Untuk menyelesaikannya harus ada dua .

  • Versi A : tumpukan harus efektif ketika item ditekan; dan
  • Versi B : Tumpukan harus efektif ketika elemen muncul.

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

124
27 марта '09 в 5:07 2009-03-27 05:07 TechTravelThink bertanya pada 27 Maret 2009 pada 05:07 2009-03-27 05:07
@ 22 jawaban

Versi A (pers efektif):

  • dorong:
    • enqueue in queue1
  • pop:
    • sedangkan antrian size1 lebih besar dari 1, objek kelebihan dari antrian1 ke antrian2
    • hapus dan kembalikan elemen terakhir dari queue1, lalu alihkan nama queue1 dan queue2

Versi B (pop efektif):

  • dorong:
    • enqueue in queue2
    • masukkan semua elemen antrian1 di antrian2, lalu alihkan nama antrian1 dan antrian2
  • pop:
    • deqeue dari queue1
178
27 марта '09 в 5:17 2009-03-27 05:17 jawabannya diberikan Svante 27 Maret 2009 di 5:17 2009-03-27 05:17

Cara termudah (dan mungkin satu-satunya) untuk melakukan ini adalah mendorong item baru ke antrian kosong, dan kemudian menghapus yang lain dan meminta ke antrian yang sebelumnya kosong. Dengan demikian, yang terakhir selalu di depan antrian. Ini akan menjadi versi B, untuk versi A Anda cukup membatalkan proses, membuang item-item secara sekunder, kecuali yang terakhir.

>

 "Stack" +---+---+---+---+---+ | | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

>

 "Stack" +---+---+---+---+---+ | 1 | | | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 1 | | | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 

>

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

>

 "Stack" +---+---+---+---+---+ | 3 | 2 | 1 | | | +---+---+---+---+---+ Queue A Queue B +---+---+---+---+---+ +---+---+---+---+---+ | 3 | 2 | 1 | | | | | | | | | +---+---+---+---+---+ +---+---+---+---+---+ 
61
27 марта '09 в 5:20 2009-03-27 05:20 jawabannya diberikan oleh Samuel pada tanggal 27 Maret 2009 di 5:20 2009-03-27 05:20

Kita dapat melakukannya dengan satu antrian:

tombol:

  • tambahkan item baru.
  • Jika n adalah jumlah elemen dalam antrian, maka hapus dan masukkan elemen n-1 kali.

pop:

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

Contoh implementasi:

 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)); } } 
46
06 сент. jawaban yang diberikan phoxis 06 Sep 2011-09-06 07:19 '11 pada 7:19 2011-09-06 07:19
 import java.util.*;  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()); } } 
9
01 дек. jawabannya diberikan oleh Mahmood Akhtar 01 Desember. 2010-12-01 13:35 '10 pada 13:35 2010-12-01 13:35

Bisakah saya menggunakan antrian tunggal untuk mengimplementasikan stack? Saya dapat menggunakan dua antrian, tetapi pertimbangan 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(); } 
4
12 апр. Jawabannya diberikan Min Zhou 12 Apr 2011-04-12 03:24 '11 pada 3:24 2011-04-12 03:24
 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(); } } 
3
10 янв. Jawabannya diberikan hiddenboy 10 Jan 2011-01-10 00:41 '11 pada 0:41 2011-01-10 00:41

Inilah jawaban saya - di mana "pop" tidak efektif. Tampaknya semua algoritme yang >

Algoritma, di mana daftar diperdagangkan kembali dan yang keempat, mungkin lebih baik, karena perhitungan ukuran tidak diperlukan, meskipun Anda masih perlu mengu>

Anda dapat membuktikan bahwa algoritma ini tidak dapat ditulis lebih cepat dari N, mencatat bahwa informasi pada elemen terakhir dalam antrian hanya tersedia melalui mengetahui ukuran antrian dan bahwa Anda harus menghancurkan data untuk sampai ke elemen ini, maka dari itu antrian kedua.

Satu-satunya cara untuk melakukannya lebih cepat adalah tidak menggunakan antrian terlebih dahulu.

 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 
2
27 марта '09 в 5:44 2009-03-27 05:44 jawabannya diberikan FlipMcF 27 Maret 2009 di 5:44 2009-03-27 05:44

Ini solusi saya yang rata-rata berfungsi untuk O (1). Ada dua antrian: in dan out . Lihat di bawah untuk kodesemu:

 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) 
2
21 февр. Jawabannya diberikan Vladimir Kostyukov 21 Feb. 2013-02-21 21:03 '13 pada 21:03 2013-02-21 21:03

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

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

Kami yakin satu antrian selalu kosong.

Operasi push: Tidak peduli antrian mana yang tidak kosong, masukkan item ke dalamnya.

  • Periksa apakah antrian Q1 kosong atau tidak. Jika Q1 kosong, maka elemen Enqueue ada di dalamnya.
  • Jika tidak, elemen EnQueue di 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: Mentransfer n-1 elemen ke antrian lain dan menghapus yang terakhir dari antrian untuk melakukan operasi pop.

  • Jika antrian Q1 tidak kosong, pindahkan elemen n-1 dari Q1 ke Q2, lalu DeQueue elemen terakhir dari Q1 dan kembalikan.
  • Jika antrian Q2 tidak kosong, pindahkan 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: waktu pelaksanaan operasi pop adalah O (n); ketika setiap kali pop dipanggil, kami mentransfer semua elemen dari satu antrian ke yang lain.

1
30 марта '14 в 22:39 2014-03-30 22:39 jawabannya diberikan oleh gandhi_rahul 30 Maret, '14 pukul 10:39 2014-03-30 22:39

Seperti yang telah disebutkan, tidak bisakah satu giliran melakukan trik? Ini mungkin kurang praktis, tetapi sedikit slider.

 push(x): enqueue(x) for(queueSize - 1) enqueue(dequeue()) pop(x): dequeue() 
1
04 янв. jawaban yang diberikan oleh dhackner 04 Jan 2011-01-04 10:17 '11 pada 10:17 2011-01-04 10:17

Berikut adalah beberapa kode pseudo sederhana, tekan - O (n), pop / mengintip - 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() 
1
30 окт. Jawabannya diberikan dansalmo 30 Oktober. 2013-10-30 20:38 '13 pada 20:38 2013-10-30 20:38
 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 
1
19 сент. balasan yang diberikan oleh Ankur Lathiya 19 September 2015-09-19 14:12 '15 pukul 14:12 2015-09-19 14:12
 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(); } } 
1
06 мая '16 в 23:52 2016-05-06 23:52 jawabannya diberikan oleh Swapnil Gangrade pada 06 Mei 16 pukul 23:52 2016-05-06 23:52
 #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); } } 
0
12 июля '14 в 14:56 2014-07-12 14:56 jawabannya diberikan Rezwan4029 12 Juli '14 pukul 14:56 2014-07-12 14:56

Kode python hanya menggunakan 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 
0
18 июля '16 в 14:55 2016-07-18 14:55 jawabannya diberikan Amol Sinha 18 Juli '16 pada 14:55 2016-07-18 14:55

Berikut ini kode kerja lengkap dalam C #:

Diimplementasikan menggunakan antrian tunggal,

tombol:

 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(); } } } 
0
15 нояб. Jawaban diberikan oleh Jaydeep Shil 15 Nov. 2016-11-15 10:33 '16 pada 10:33 2016-11-15 10:33

Ini solusi lain:

untuk PUSH: -Tambahkan item pertama dalam antrian 1. -Ketika menambahkan item kedua, dan seterusnya. Pertama pindahkan item ke antrian 2, dan kemudian salin semua item dari antrian 1 ke antrian2. - untuk POP, cukup hapus item dari antrian Anda dengan memasukkan item terakhir.

Jadi

 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 tahu bagaimana cara mengganti nama antriannya ???

0
13 марта '12 в 15:10 2012-03-13 15:10 jawabannya diberikan kepada Vince pada 13 Maret '12 pukul 15:10

Ini kode Java saya untuk mengimplementasikan stack menggunakan antrian.

  import java.util.LinkedList; import java.util.Queue;  public class StackImplementationiUsingQueue { Queue<Integer> q1=new LinkedList<Integer>(); Queue<Integer> q2=new LinkedList<Integer>(); //push operation public void push(int data){ this.q1.add(data); } //pop operation public int pop(){ if(this.q1.isEmpty()){ System.out.println("No Element found !"); } else { int x; while(this.q1.size()>1){ x=this.q1.remove(); this.q2.add(x); } x=q1.remove(); this.q1.addAll(q2); return x; } return -1; } public static void main(String[] args) { StackImplementationiUsingQueue stack=new StackImplementationiUsingQueue(); stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); System.out.println(stack.pop()); } 

}

0
16 июня '17 в 21:13 2017-06-16 21:13 Balas yang diberikan oleh Dungeon Master adalah Kembali 16 Juni 17 di 21:13 2017-06-16 21:13

Berikut ini adalah solusi yang sangat sederhana yang menggunakan antrian tunggal dan menyediakan fungsi 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 disebut "CustomStack", apa yang saya lakukan hanyalah memeriksa antrian untuk kosong jika kosong, lalu tempel, dan kemudian pada tab bangsal, dan kemudian hapus sisipan. Menurut logika ini, yang terakhir akan didahulukan. Contoh: Saya memasukkan 1 dalam antrian dan sekarang saya mencoba memasukkan 2. Hapus 1 untuk yang kedua dan tempel lagi sehingga menjadi dalam urutan terbalik.

Terima kasih

0
07 июля '17 в 11:29 2017-07-07 11:29 jawabannya diberikan oleh Prityalok Raman 07 Juli '17 di 11:29 2017-07-07 11:29
 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; } } } 
-1
23 мая '15 в 11:22 2015-05-23 11:22 jawabannya diberikan oleh Rajnish Kumar Jha 23 Mei '15 pukul 11:22 2015-05-23 11:22
 #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; }  void stackCreate(Stack *stack, int maxSize) { Stack **s = (Stack**) stack; *s = (Stack*)malloc(sizeof(Stack)); (*s)->q1 = queueCreate(maxSize); (*s)->q2 = queueCreate(maxSize); }  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; }  void stackPop(Stack *stack) { Stack **s = (Stack**) stack; queuePop((*s)->q1); }  int stackTop(Stack *stack) { Stack **s = (Stack**) stack; if (!queueIsEmpty((*s)->q1)) { return queueTop((*s)->q1); } return -1; }  bool stackEmpty(Stack *stack) { Stack **s = (Stack**) stack; if (queueIsEmpty((*s)->q1)) { return true; } return false; }  void stackDestroy(Stack *stack) { Stack **s = (Stack**) stack; free((*s)->q1); free((*s)->q2); free((*s)); } int main() { Stack *s = NULL; stackCreate((Stack*) 10); stackPush((Stack*) 44); //stackPop((Stack*) printf("\n%d", stackTop((Stack*) stackDestroy((Stack*) return 0; } 
-1
21 июня '15 в 22:16 2015-06-21 22:16 jawabannya diberikan seth 21 Juni '15 pada 22:16 2015-06-21 22:16

Ini keputusan saya ..

Concept_Behind :: push(struct Stack* S,int data) :: Fungsi ini menempatkan elemen pertama di Q1 dan tetap di pop(struct Stack* S) Q2 pop(struct Stack* S) :: jika Q2 tidak kosong, ia mentransfer semua elem ke Q1 dan mengembalikan elem terakhir di Q2, selain itu (yang berarti Q2 kosong) meneruskan semua elem ke Q2 dan mengembalikan elemen terakhir di Q1

Efficiency_Behind :: push(struct Stack*S,int data) :: O (1) // karena satu data mengikat ke pop(struct Stack* S) :: O (n) // karena menerjemahkan data n-1 terburuk ke dalam setiap 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; } ///////////////////////////////////////////// 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); } } } /////////////////// main() { int size; printf("Enter the number of elements in the Stack(made of 2 queue's)::\n"); scanf("%d", 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)); } 
-1
14 июля '14 в 12:49 2014-07-14 12:49 jawabannya diberikan oleh Dota2 14 Juli '14 pukul 12:49 2014-07-14 12:49

Pertanyaan lain pada label atau Ajukan Pertanyaan