Zaimplementuj stos przy użyciu dwóch kolejek

143

Podobne pytanie zostało tam zadane wcześniej , ale tutaj jest odwrotnie, używając dwóch kolejek jako stosu. Pytanie...

Biorąc pod uwagę dwie kolejki z ich standardowych operacji ( enqueue, dequeue, isempty, size), zaimplementować stos z jego standardowych operacji ( pop, push, isempty, size).

Powinny istnieć dwie wersje rozwiązania.

  • Wersja A : Stos powinien być wydajny podczas wypychania elementu; i
  • Wersja B : Stos powinien być wydajny podczas wyskakiwania elementu.

Interesuje mnie algorytm bardziej niż jakiekolwiek konkretne implementacje językowe. Z zadowoleniem przyjmuję jednak rozwiązania wyrażone w językach, które znam (,,,,,).

TechTravelThink
źródło
6
Jasne, że tak! CLRS - 10.1-6 ( tinyurl.com/clrs-ex-10-1-6 )
rampion
1
Jeden stos, dwie kolejki to eleganckie rozwiązanie, które Popdziała w $ O (1) $ i Pushdziała w $ O (\ sqrt {n}) $ amortyzowanym czasie.
hengxin
1
@rampion Teraz jego CLRS - 10.1-7. :)
nsane
Powiązany post. Jest to jeden inny ciekawy problem zaimplementować stos używając tylko jedną kolejkę tutaj .
RBT

Odpowiedzi:

194

Wersja A (wydajne wypychanie):

  • Pchać:
    • enqueue in queue1
  • Muzyka pop:
    • podczas gdy rozmiar queue1 jest większy niż 1, potokiem elementy usunięte z kolejki z queue1 do queue2
    • Usuń z kolejki i zwróć ostatnią pozycję queue1, a następnie zamień nazwy queue1 i queue2

Wersja B (wydajny pop):

  • Pchać:
    • enqueue in queue2
    • umieść w kolejce wszystkie elementy queue1 w queue2, a następnie zamień nazwy queue1 i queue2
  • Muzyka pop:
    • deqeue z queue1
Svante
źródło
4
Wydaje się, że wersja B ma problem: czy masz na myśli zakolejkowanie wszystkich elementów queue2 do queue1 z wyjątkiem ostatniego elementu (następnie zmień nazwy q1 i q2)?
Icerman
Komentarz Icermana ma dla mnie sens. Wersja B odpowiedzi wymaga edycji. Nie mam uprawnień do edycji. Czy ktoś mógłby edytować tę odpowiedź?
eeerahul
2
@eeerahul: Sprawdziłem to ponownie i odpowiedź jest prawidłowa. W chwili, gdy wydaje się, że Icerman chce umieścić wszystkie pozycje queue2 w kolejce queue1, queue2 składa się tylko z nowej pozycji, więc komentarz nie ma sensu.
Svante
Czy wersja A jest prawidłowa? wciśnij 1, wciśnij 2, wciśnij 3, wciśnij 4. wciśnij 4. wciśnij 5, wciśnij 6, wciśnij 7, wciśnij 8. pop 8. pop 7. Wygląda na to, Ŝe ten algorytm będzie wyświetlał 3 zamiast 7. Twój algorytm wydaje się być włączony na pierwszy rzut oka, ponieważ prawdopodobnie możemy rozumować jako: w zasadzie zawsze będziesz wstawiał ostatni umieszczony w kolejce element w kolejce 1. Ale to jest ostatni wypchnięty element tylko wtedy, gdy byłeś w kolejce wcześniej. Jeśli pojawiłeś się kilka razy z rzędu, nie musi to być prawda.
user127.0.0.1
1
@ user127.0.0.1: Wygląda na to, że zapomniałeś zmienić kolejki na końcu każdego popu. Istnieje niezmiennik, że po każdym wypchnięciu i każdym popu wszystkie elementy znajdują się w queue1, podczas gdy queue2 jest pusta.
Svante
68

Najłatwiejszym (i być może jedynym) sposobem na zrobienie tego jest wpychanie nowych elementów do pustej kolejki, a następnie dekolejowanie pozostałych i wpisywanie do poprzednio pustej kolejki. W ten sposób najnowszy jest zawsze na początku kolejki. Byłaby to wersja B, w przypadku wersji A wystarczy odwrócić proces, usuwając elementy z kolejki do drugiej kolejki, z wyjątkiem ostatniej.

Krok 0:

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

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

Krok 1:

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

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

Krok 2:

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

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

Krok 3:

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

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+
Samuel
źródło
1
Logika tego nie ma sensu. Przejdź z kroku 2 do kroku 3. Kiedy „push” 3, w jaki sposób mogę usunąć z kolejki elementy w kolejce B w taki sposób, aby uzyskać 3 2 1 w kolejce A? Jeśli usunę z kolejki B, aby umieścić w kolejce A, mogę uzyskać tylko elementy w kolejności 2, 1. Jeśli następnie dodam 3, otrzymam zamówienie 3, 1, 2. Jeśli najpierw umieściłem push, a następnie umieściłem w kolejce / przeniesiono do kolejki, otrzymam 1, 2, 3
tsurantino
dlaczego nie uczynić operacji umieszczania w kolejce kosztowną niż operację kolejkowania kosztowną?
Divij Sehgal
49

Możemy to zrobić jedną kolejką:

Pchać:

  1. dodaj do kolejki nowy element.
  2. Jeśli njest liczbą elementów w kolejce, usuń i wstaw n-1razy elementy .

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

Przykładowa realizacja:

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
źródło
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
źródło
Czy ktoś mógłby wyjaśnić logowanie za metodą push w powyższym kodzie? O ile zrozumiałem, pierwszą pętlą for jest usunięcie wszystkich elementów do q2, aż q1 pozostanie jeden element. Proszę, popraw mnie jeśli się mylę.
John
4

Czy możemy użyć jednej kolejki do zaimplementowania stosu? Mogę używać dwóch kolejek, ale rozważenie pojedynczej kolejki byłoby bardziej wydajne. Oto kod:

    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
źródło
Wydaje mi się, że w metodzie pop warunek pętli for powinien być i <queLower.Count - 2, ponieważ inicjalizujesz zmienną i z 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
źródło
2

Oto moja odpowiedź - gdzie „pop” jest nieefektywny. Wydaje się, że wszystkie algorytmy, które przychodzą do głowy od razu, mają złożoność N, gdzie N jest rozmiarem listy: niezależnie od tego, czy zdecydujesz się pracować na „pop”, czy na „push”

Algorytm, w którym listy są wymieniane z powrotem i czwarte, może być lepszy, ponieważ obliczanie rozmiaru nie jest potrzebne, chociaż nadal musisz zapętlić i porównać z pustymi.

możesz udowodnić, że ten algorytm nie może być zapisany szybciej niż N, zauważając, że informacja o ostatnim elemencie w kolejce jest dostępna tylko poprzez znajomość rozmiaru kolejki i że musisz zniszczyć dane, aby dostać się do tego elementu, stąd druga kolejka .

Jedynym sposobem, aby to przyspieszyć, jest przede wszystkim nie używanie kolejek.

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
źródło
2

Oto moje rozwiązanie, które działa w przeciętnym przypadku dla O (1). Istnieją dwie kolejki: ini out. Zobacz pseudokod poniżej:

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
źródło
2
Tam używasz 2 kolejek i 1 stosu do symulacji 1 stosu!
BeniBela
Czy masz na myśli ukryty stos rekurencji?
Vladimir Kostyukov
1

Jak już wspomniano, czy pojedyncza kolejka nie załatwi sprawy? Prawdopodobnie jest mniej praktyczny, ale jest nieco bardziej przejrzysty.

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

pop(x):
dequeue()
dhackner
źródło
1

Oto prosty pseudokod, push to O (n), pop / peek to 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
źródło
1

Niech S1 i S2 będą dwoma stosami używanymi w implementacji kolejek.

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

Dbamy o to, aby jedna kolejka była zawsze pusta.

Operacja wypychania: niezależnie od tego, która kolejka nie jest pusta, wstaw do niej element.

  • Sprawdź, czy kolejka Q1 jest pusta, czy nie. Jeśli Q1 jest puste, umieść w kolejce element w nim.
  • W przeciwnym razie umieść element w kolejce do Q1.

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

Złożoność czasowa: O (1)

Operacja pop: Przenieś n-1 elementów do innej kolejki i usuń ostatni z kolejki w celu wykonania operacji pop.

  • Jeśli kolejka Q1 nie jest pusta, przenieś n-1 elementów z Q1 do Q2, a następnie ustaw w kolejkę ostatni element z Q1 i zwróć go.
  • Jeśli kolejka Q2 nie jest pusta, przenieś n-1 elementów z Q2 do Q1, a następnie Ustaw w kolejkę ostatni element z Q2 i zwróć go.

`

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

Złożoność czasowa: czas działania pop Operacja wynosi O (n), ponieważ za każdym razem, gdy wywoływany jest pop, przenosimy wszystkie elementy z jednej kolejki do drugiej.

Rahul Gandhi
źródło
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
źródło
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
źródło
0

Oto jeszcze jedno rozwiązanie:

dla PUSH: -Dodaj pierwszy element do kolejki 1. -Podczas dodawania drugiego elementu i tak dalej, należy najpierw umieścić element w kolejce 2, a następnie skopiować cały element z kolejki 1 do kolejki2. -W przypadku POP po prostu usuń z kolejki element z kolejki od wstawionego ostatniego elementu.

Więc,

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;
}'

Jest jeden problem, nie wiem jak zmienić nazwy kolejek ???

Vince
źródło
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
źródło
1
Proszę o kilka słów wyjaśniających, o co chodzi w tym kodzie i jak ta rzecz jest w stanie pomóc OP w rozwiązaniu jego / jej problemu, będą bardzo mile widziane, wraz z przykładem kodu :-)
NIcE cOw
0

Kod Pythona wykorzystujący tylko jedną kolejkę

 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
źródło
1
Spróbuj uniknąć po prostu zrzucania kodu jako odpowiedzi i spróbuj wyjaśnić, co robi i dlaczego. Twój kod może nie być oczywisty dla osób, które nie mają odpowiedniego doświadczenia w kodowaniu.
Frits
0

oto kompletny działający kod w C #:

Został zaimplementowany z pojedynczą kolejką,

Pchać:

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

Muzyka 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
źródło
Chcesz skomentować (spodziewany / zamortyzowany) czas wymagany przez twoją implementację jako funkcję aktualnie utrzymywanych elementów / sumy wypychania i wyskakiwania?
siwobrody
0

Oto bardzo proste rozwiązanie, które wykorzystuje jedną kolejkę i zapewnia funkcjonalność taką jak 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());
    }


}

Więc w powyższej klasie o nazwie „CustomStack” to, co robię, to po prostu sprawdzanie, czy kolejka jest pusta, jeśli jest pusta, to wstaw jedną i od tej pory wstawiaj i usuwaj wstawki. Zgodnie z tą logiką pierwszy będzie ostatni. Przykład: W kolejce wstawiłem 1 i teraz próbuję wstawić 2. Drugi raz usuń 1 i ponownie włóż, aby stało się w odwrotnej kolejności.

Dziękuję Ci.

Prityalok Raman
źródło
0

Poniżej znajduje się bardzo proste rozwiązanie Java, które obsługuje wydajną operację wypychania.

Algorytm -

  1. Zadeklaruj dwie kolejki q1 i q2.

  2. Operacja wypychania - wstaw element do kolejki q1.

  3. Operacja pop - upewnij się, że kolejka q2 nie jest pusta. Jeśli jest pusty, usuń z kolejki wszystkie elementy z q1 z wyjątkiem ostatniego i umieść go w kolejce do q2 jeden po drugim. Usuń z kolejki ostatni element z q1 i zapisz go jako wyskakujący element. Zamień kolejki q1 i q2. Zwróć przechowywany popped element.

  4. Peek operation - upewnij się, że kolejka q2 nie jest pusta. Jeśli jest pusty, usuń z kolejki wszystkie elementy z q1 z wyjątkiem ostatniego i umieść go w kolejce do q2 jeden po drugim. Usuń z kolejki ostatni element z q1 i zapisz go jako podglądany element. Umieść go z powrotem w kolejce q2 i zamień kolejki q1 i q2. Zwróć przechowywany wgląd w element.

Poniżej znajduje się kod powyższego algorytmu -

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
źródło
-1

Oto moje rozwiązanie…

Concept_Behind :: push(struct Stack* S,int data):: Ta funkcja umieszcza w kolejce pierwszy element w Q1 i odpoczywa w Q2 pop(struct Stack* S) :: jeśli Q2 nie jest puste, przenosi wszystkie elementy do Q1 i zwraca ostatni element w Q2 else (co oznacza, że ​​Q2 jest puste) przenosi wszystkie elementy do Q2 i zwraca ostatni element w Q1

Efficiency_Behind :: push(struct Stack*S,int data):: O (1) // od pojedynczej kolejki na dane pop(struct Stack* S):: O (n) // ponieważ przenosi najgorsze n-1 danych na 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
źródło
-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
źródło
Lista połączona z językiem Java działa dobrze. Ta odpowiedź nie ma sensu.
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
źródło
Ściana kodu bez komentarzy i wyjaśnień to kiepska odpowiedź.
Richard