Реализуйте стек с использованием двух очередей

143

Аналогичный вопрос был задан ранее там , но здесь вопрос обратный, используя две очереди в качестве стека. Вопрос...

Учитывая две очереди с их стандартными операциями ( enqueue, dequeue, isempty, size), реализовать стек с его стандартными операциями ( pop, push, isempty, size).

Должно быть две версии решения.

  • Версия A : стек должен быть эффективным при выталкивании элемента; а также
  • Версия B : стек должен быть эффективным при извлечении элемента.

Алгоритм меня интересует больше, чем какие-либо конкретные языковые реализации. Однако я приветствую решения, выраженные на знакомых мне языках (,,,,,).

TechTravelThink
источник
6
Конечно да! CLRS - 10.1-6 ( tinyurl.com/clrs-ex-10-1-6 )
rampion
1
One Stack, Two Queues дает элегантное решение, которое Popработает в $ O (1) $ и Pushработает в амортизированном времени $ O (\ sqrt {n}) $.
hengxin 08
1
@rampion Теперь его CLRS - 10.1-7. :)
nsane
Связанный пост. Это одна другая интересная задача для реализации стека , используя только один очереди здесь .
RBT

Ответы:

194

Версия А (эффективный толчок):

  • От себя:
    • поставить в очередь 1
  • поп:
    • в то время как размер очереди queue1 больше 1, элементы, удаленные из очереди, пересылаются из очереди queue2 в очередь 2
    • dequeue и вернуть последний элемент queue1, затем переключить имена queue1 и queue2

Версия B (эффективный поп):

  • От себя:
    • поставить в очередь 2
    • поставить в очередь все элементы queue1 в queue2, затем поменять имена queue1 и queue2
  • поп:
    • deqeue из очереди 1
Сванте
источник
4
У версии B возникла проблема: вы имеете в виду поставить все элементы очереди queue2 в очередь 1, кроме последнего элемента (затем поменяйте имена q1 и q2)?
Icerman
Комментарий Айцермана мне понятен. Версия B ответа нуждается в редактировании. У меня нет прав на редактирование. Может кто-нибудь отредактировать этот ответ?
eeerahul 07
2
@eeerahul: Я проверил еще раз, и ответ правильный. В то время, когда Айсерман, похоже, хочет поставить все элементы очереди queue2 в очередь queue1, queue2 состоит только из нового элемента, поэтому комментарий не имеет смысла.
Svante
Верна ли версия А? push 1, push 2, push 3, push 4. pop 4. push 5, push 6, push 7, push 8. pop 8. pop 7. Похоже, этот алгоритм будет выдавать 3 вместо 7. Ваш алгоритм кажется правильным. первый взгляд, потому что мы можем рассуждать так: в основном вы всегда будете выталкивать последний элемент в очереди в Queue 1. Но это последний отправленный элемент, только если вы поставили в очередь раньше. Если вы открывали несколько раз подряд, это не должно быть правдой.
user127.0.0.1
1
@ user127.0.0.1: Похоже, вы забыли переключать очереди в конце каждого всплывающего сообщения. Существует инвариант, согласно которому после каждого нажатия и каждого нажатия все элементы находятся в очереди 1, а очередь 2 пуста.
Svante
68

Самый простой (и, возможно, единственный) способ сделать это - поместить новые элементы в пустую очередь, а затем исключить другие и поставить их в ранее пустую очередь. Таким образом, последний всегда находится в начале очереди. Это будет версия B, для версии A вы просто отменяете процесс, удаляя элементы из очереди во вторую очередь, за исключением последней.

Шаг 0:

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

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

Шаг 1:

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

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

Шаг 2:

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

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

Шаг 3:

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

Queue A                Queue B
+---+---+---+---+---+  +---+---+---+---+---+
| 3 | 2 | 1 |   |   |  |   |   |   |   |   |
+---+---+---+---+---+  +---+---+---+---+---+
Самуэль
источник
1
Логика этого не имеет никакого смысла. Сделайте переход от шага 2 к шагу 3. Когда я нажимаю 3, как я могу удалить элементы из очереди B таким образом, чтобы я получил 3 2 1 в очереди A? Если я выведу B из очереди в очередь A, я могу получить элементы только в порядке 2, 1. Если я затем добавлю 3, я получу порядок 3, 1, 2. Если сначала поместить мой push, а затем удалить из очереди / поставить в очередь, я получу 1, 2, 3.
цурантино
почему бы не сделать операцию deque более дорогой, чем операцию постановки в очередь?
Divij Sehgal
49

Мы можем сделать это с помощью одной очереди:

От себя:

  1. поставить новый элемент в очередь.
  2. Если n- количество элементов в очереди, то время удаления и вставки элемента n-1.

поп:

  1. исключать из очереди

.

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

Пример реализации:

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));
  }
}
фоксис
источник
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());
    }
}
Махмуд Ахтар
источник
Может ли кто-нибудь объяснить логин за методом push в приведенном выше коде? Насколько я понял, первый цикл for удаляет все элементы в q2, пока в q1 не останется один элемент. Пожалуйста, поправьте меня, если я ошибаюсь.
Джон
4

Можем ли мы использовать одну очередь для реализации стека? Я могу использовать две очереди, но использование одной очереди было бы более эффективным. Вот код:

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

    }
Мин Чжоу
источник
Я предполагаю, что в методе pop условие цикла for должно быть i <queLower.Count - 2, поскольку вы инициализируете переменную i с помощью 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();
   }
}
скрытый мальчик
источник
2

Вот мой ответ - там, где «поп» неэффективен. Кажется, что все алгоритмы, которые сразу приходят на ум, имеют сложность N, где N - размер списка: выбираете ли вы работать с «всплывающим» или «толкающим».

Алгоритм, при котором списки возвращаются обратно и четвертый, может быть лучше, так как расчет размера не требуется, хотя вам все равно нужно зацикливаться и сравнивать с пустым.

вы можете доказать, что этот алгоритм не может быть записан быстрее, чем N, отметив, что информация о последнем элементе в очереди доступна только через знание размера очереди, и что вы должны уничтожить данные, чтобы добраться до этого элемента, следовательно, вторая очередь .

Единственный способ сделать это быстрее - вообще не использовать очереди.

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
источник
2

Вот мое решение, которое работает для O (1) в среднем случае. Есть две очереди: inи out. См. Псевдокод ниже:

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
Здесь вы используете 2 очереди и 1 стек для имитации 1 стека!
BeniBela
Вы имеете в виду неявный стек рекурсии?
Владимир Костюков
1

Как уже упоминалось, разве не поможет одна очередь? Это, вероятно, менее практично, но немного круче.

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

pop(x):
dequeue()
Дхакнер
источник
1

Вот простой псевдокод, push - O (n), pop / peek - 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

Пусть S1 и S2 - два стека, которые будут использоваться при реализации очередей.

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

Мы следим за тем, чтобы одна очередь всегда была пустой.

Операция push: какая бы очередь не пуста, вставьте в нее элемент.

  • Проверьте, пуста ли очередь Q1. Если Q1 пуст, поместите в него элемент в очередь.
  • В противном случае поместите элемент в Q1.

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

Сложность времени: O (1)

Pop Operation: передать n-1 элементов в другую очередь и удалить последний из очереди для выполнения операции pop.

  • Если очередь Q1 не пуста, перенесите n-1 элементов из Q1 в Q2, а затем DeQueue последнего элемента Q1 и верните его.
  • Если очередь Q2 не пуста, перенесите n-1 элементов из Q2 в Q1, а затем DeQueue последнего элемента Q2 и верните его.

`

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

Сложность времени: время выполнения операции pop - O (n), поскольку каждый раз, когда вызывается pop, мы переносим все элементы из одной очереди в другую.

Рахул Ганди
источник
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
Анкур Латия
источник
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();
    }
}
Свапнил Ганград
источник
0

Вот еще одно решение:

для PUSH: -Добавьте первый элемент в очередь 1. -При добавлении второго элемента и так далее, сначала поставьте элемент в очередь 2, а затем скопируйте все элементы из очереди 1 в очередь2. -для POP просто удалите элемент из очереди, если вы вставили последний элемент.

Так,

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

Есть одна проблема, не могу разобраться, как переименовать очереди ???

Винс
источник
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
источник
1
Пожалуйста, несколько слов, объясняющих, о чем этот код, и как эта штука может помочь OP в решении его / ее проблемы, будет высоко оценена вместе с примером кода :-)
nIcE cOw
0

Код Python с использованием только одной очереди

 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
Амол Синха
источник
1
Постарайтесь не просто сбрасывать код в качестве ответа и постарайтесь объяснить, что он делает и почему. Ваш код может быть не очевиден для людей, не имеющих соответствующего опыта программирования.
Frits
0

вот полный рабочий код на С #:

Это было реализовано с единой очередью,

От себя:

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

поп:

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();
            }
        }
    }
Джайдип Шил
источник
Не хотите ли прокомментировать (ожидаемое / амортизированное) время, требуемое вашей реализацией, в зависимости от хранимых в настоящее время элементов / суммы нажатий и всплывающих окон?
greybeard
0

Вот очень простое решение, которое использует одну очередь и предоставляет такие функции, как стек.

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


}

Итак, в приведенном выше классе с именем "CustomStack" я просто проверяю очередь на пустоту, если она пуста, то вставляю ее, а затем вставляю опеку и затем удаляю вставку. По этой логике первое будет последним. Пример: в очереди я вставил 1 и теперь пытаюсь вставить 2. Второй раз удалите 1 и снова вставьте, чтобы это стало в обратном порядке.

Спасибо.

Притялок Раман
источник
0

Ниже приведено очень простое решение Java, которое эффективно поддерживает операцию push.

Алгоритм -

  1. Объявите две очереди q1 и q2.

  2. Операция push - поставить элемент в очередь q1.

  3. Операция Pop - убедитесь, что очередь q2 не пуста. Если он пуст, то удалите из очереди все элементы из q1, кроме последнего, и поместите их в очередь в q2 один за другим. Удалите из очереди последний элемент из q1 и сохраните его как всплывающий элемент. Поменяйте местами очереди q1 и q2. Вернуть сохраненный всплывающий элемент.

  4. Операция просмотра - убедитесь, что очередь q2 не пуста. Если он пуст, то удалите из очереди все элементы из q1, кроме последнего, и поместите их в очередь в q2 один за другим. Удалите из очереди последний элемент из q1 и сохраните его как выбранный элемент. Поместите его обратно в очередь q2 и поменяйте местами очереди q1 и q2. Вернуть сохраненный просматриваемый элемент.

Ниже приведен код для вышеуказанного алгоритма -

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;
    }
}
Хетал Рах
источник
0

Эффективное решение на C #

public class MyStack {
    private Queue<int> q1 = new Queue<int>();
    private Queue<int> q2 = new Queue<int>();
    private int count = 0;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
    }

    /**
     * Push element x onto stack.
     */
    public void Push(int x) {
        count++;
        q1.Enqueue(x);
        while (q2.Count > 0) {
            q1.Enqueue(q2.Peek());
            q2.Dequeue();
        }
        var temp = q1;
        q1 = q2;
        q2 = temp;
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int Pop() {
        count--;
        return q2.Dequeue();
    }

    /**
     * Get the top element.
     */
    public int Top() {
        return q2.Peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public bool Empty() {
        if (count > 0) return false;
        return true;
    }
}
ДИБЬЕНДУ САХА
источник
-1

Вот мое решение ..

Concept_Behind :: push(struct Stack* S,int data):: Эта функция ставит первый элемент в очередь в Q1 и остается в Q2 pop(struct Stack* S) :: если Q2 не пуст, переносит все элементы в Q1 и возвращает последний элемент в Q2, иначе (что означает, что Q2 пуст) переносит все элементы в Q2 и возвращает последний элемент в Q1

Efficiency_Behind :: push(struct Stack*S,int data):: O (1) // с момента одиночной постановки в очередь на данные pop(struct Stack* S):: O (n) // поскольку переносит худшие данные n-1 на поп.

#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));
    }
Dota 2
источник
-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;
        }
    }
}
Раджниш Кумар Джа
источник
Связанный список Java отлично работает как двухсторонняя очередь. Этот ответ не имеет смысла.
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;
}
Сет
источник
Стена кода без комментариев или объяснений - плохой ответ.
Ричард