Рубрики

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

Проблема противоположна этому посту. Нам дана структура данных Queue, которая поддерживает стандартные операции, такие как enqueue () и dequeue (). Нам необходимо реализовать структуру данных стека, используя только экземпляры очереди и операции с очередями, разрешенные для этих экземпляров.

Стек может быть реализован с использованием двух очередей. Пусть для реализации стека будут 's', а для реализации используются очереди 'q1' и 'q2'. Стек 's' может быть реализован двумя способами:

Способ 1 (делая операцию толчка дорогостоящей)
Этот метод гарантирует, что вновь введенный элемент всегда находится перед «q1», так что операция pop просто отключается от «q1». «q2» используется для размещения каждого нового элемента перед «q1».

  1. Шаг операции push (s, x) описан ниже:
    • Поставить в очередь x к q2
    • Один за другим снимаем все с q1 и ставим в очередь q2.
    • Поменяйте местами имена q1 и q2
  2. Функция операции pop (s) описана ниже:
    • Снимите предмет с q1 и верните его.

Ниже приведена реализация вышеуказанного подхода:

C ++

/ * Программа для реализации стека с использованием
две очереди * /
#include <bits/stdc++.h>

  

using namespace std;

  

class Stack {

    // Две встроенные очереди

    queue<int> q1, q2;

  

    // Для поддержания текущего номера

    // элементы

    int curr_size;

  

public:

    Stack()

    {

        curr_size = 0;

    }

  

    void push(int x)

    {

        curr_size++;

  

        // Нажмите x первым в пустом q2

        q2.push(x);

  

        // Подтолкнуть все оставшиеся

        // элементы от q1 до q2.

        while (!q1.empty()) {

            q2.push(q1.front());

            q1.pop();

        }

  

        // поменять местами имена двух очередей

        queue<int> q = q1;

        q1 = q2;

        q2 = q;

    }

  

    void pop()

    {

  

        // если в q1 нет элементов

        if (q1.empty())

            return;

        q1.pop();

        curr_size--;

    }

  

    int top()

    {

        if (q1.empty())

            return -1;

        return q1.front();

    }

  

    int size()

    {

        return curr_size;

    }

};

  
// Код драйвера

int main()

{

    Stack s;

    s.push(1);

    s.push(2);

    s.push(3);

  

    cout << "current size: " << s.size()

         << endl;

    cout << s.top() << endl;

    s.pop();

    cout << s.top() << endl;

    s.pop();

    cout << s.top() << endl;

  

    cout << "current size: " << s.size()

         << endl;

    return 0;

}
// Этот код предоставлен Чхави

Джава

/ * Java-программа для реализации стека с использованием
две очереди * /

import java.util.*;

  

class GfG {

  

    static class Stack {

        // Две встроенные очереди

        static Queue<Integer> q1 = new LinkedList<Integer>();

        static Queue<Integer> q2 = new LinkedList<Integer>();

  

        // Для поддержания текущего номера

        // элементы

        static int curr_size;

  

        Stack()

        {

            curr_size = 0;

        }

  

        static void push(int x)

        {

            curr_size++;

  

            // Нажмите x первым в пустом q2

            q2.add(x);

  

            // Подтолкнуть все оставшиеся

            // элементы от q1 до q2.

            while (!q1.isEmpty()) {

                q2.add(q1.peek());

                q1.remove();

            }

  

            // поменять местами имена двух очередей

            Queue<Integer> q = q1;

            q1 = q2;

            q2 = q;

        }

  

        static void pop()

        {

  

            // если в q1 нет элементов

            if (q1.isEmpty())

                return;

            q1.remove();

            curr_size--;

        }

  

        static int top()

        {

            if (q1.isEmpty())

                return -1;

            return q1.peek();

        }

  

        static int size()

        {

            return curr_size;

        }

    }

  

    // код драйвера

    public static void main(String[] args)

    {

        Stack s = new Stack();

        s.push(1);

        s.push(2);

        s.push(3);

  

        System.out.println("current size: " + s.size());

        System.out.println(s.top());

        s.pop();

        System.out.println(s.top());

        s.pop();

        System.out.println(s.top());

  

        System.out.println("current size: " + s.size());

    }

}
// Этот код предоставлен Prerna

python3

# Программа для реализации стека с использованием
# две очереди

from queue import Queue

  

class Stack:

      

    def __init__(self):

          

        # Две встроенные очереди

        self.q1 = Queue()

        self.q2 = Queue() 

              

        # Чтобы сохранить текущий номер

        количество элементов

        self.curr_size = 0

  

    def push(self, x):

        self.curr_size += 1

  

        # Сначала нажмите x в пустом q2

        self.q2.put(x) 

  

        # Подтолкнуть все оставшиеся

        # элементов от q1 до q2.

        while (not self.q1.empty()):

            self.q2.put(self.q1.queue[0]) 

            self.q1.get()

  

        # поменять местами имена двух очередей

        self.q = self.q1 

        self.q1 = self.q2 

        self.q2 = self.q

  

    def pop(self):

  

        # если в q1 нет элементов

        if (self.q1.empty()): 

            return

        self.q1.get() 

        self.curr_size -= 1

  

    def top(self):

        if (self.q1.empty()):

            return -1

        return self.q1.queue[0]

  

    def size(self):

        return self.curr_size

  
Код водителя

if __name__ == '__main__':

    s = Stack()

    s.push(1

    s.push(2

    s.push(3

  

    print("current size: ", s.size())

    print(s.top()) 

    s.pop() 

    print(s.top()) 

    s.pop() 

    print(s.top()) 

  

    print("current size: ", s.size())

  
# Этот код предоставлен PranchalK

C #

/ * C # Программа для реализации стека с использованием
две очереди * /

using System;

using System.Collections;

  

class GfG {

  

    public class Stack {

        // Две встроенные очереди

        public Queue q1 = new Queue();

        public Queue q2 = new Queue();

  

        // Для поддержания текущего номера

        // элементы

        public int curr_size;

  

        public Stack()

        {

            curr_size = 0;

        }

  

        public void push(int x)

        {

            curr_size++;

  

            // Нажмите x первым в пустом q2

            q2.Enqueue(x);

  

            // Подтолкнуть все оставшиеся

            // элементы от q1 до q2.

            while (q1.Count > 0) {

                q2.Enqueue(q1.Peek());

                q1.Dequeue();

            }

  

            // поменять местами имена двух очередей

            Queue q = q1;

            q1 = q2;

            q2 = q;

        }

  

        public void pop()

        {

  

            // если в q1 нет элементов

            if (q1.Count == 0)

                return;

            q1.Dequeue();

            curr_size--;

        }

  

        public int top()

        {

            if (q1.Count == 0)

                return -1;

            return (int)q1.Peek();

        }

  

        public int size()

        {

            return curr_size;

        }

    };

  

    // Код драйвера

    public static void Main(String[] args)

    {

        Stack s = new Stack();

        s.push(1);

        s.push(2);

        s.push(3);

        Console.WriteLine("current size: " + s.size());

        Console.WriteLine(s.top());

        s.pop();

        Console.WriteLine(s.top());

        s.pop();

        Console.WriteLine(s.top());

        Console.WriteLine("current size: " + s.size());

    }

}

  
// Этот код предоставлен Арнабом Кунду


Выход :

current size: 3
3
2
1
current size: 1

Способ 2 (делая поп-операцию дорогостоящей)
В режиме push новый элемент всегда ставится в очередь на q1. В операции pop (), если q2 пусто, тогда все элементы, кроме последнего, перемещаются в q2. Наконец, последний элемент удаляется из q1 и возвращается.

  1. операция push (s, x) :
    • Поставьте в очередь x к q1 (при условии, что размер q1 не ограничен).
  2. операция pop (s) :
    • Один за другим удалите все, кроме последнего элемента из q1, и поставьте в очередь q2.
    • Снимите с очереди последний элемент q1, исключенный элемент — результат, сохраните его.
    • Поменяйте местами имена q1 и q2
    • Верните элемент, сохраненный в шаге 2.

C ++

/ * Программа для реализации стека
используя две очереди * /
#include <bits/stdc++.h>

using namespace std;

  

class Stack {

    queue<int> q1, q2;

    int curr_size;

  

public:

    Stack()

    {

        curr_size = 0;

    }

  

    void pop()

    {

        if (q1.empty())

            return;

  

        // Оставляем один элемент в q1 и

        // подтолкнуть других в q2.

        while (q1.size() != 1) {

            q2.push(q1.front());

            q1.pop();

        }

  

        // Высовываем единственный левый элемент

        // из q1

        q1.pop();

        curr_size--;

  

        // поменять местами имена двух очередей

        queue<int> q = q1;

        q1 = q2;

        q2 = q;

    }

  

    void push(int x)

    {

        q1.push(x);

        curr_size++;

    }

  

    int top()

    {

        if (q1.empty())

            return -1;

  

        while (q1.size() != 1) {

            q2.push(q1.front());

            q1.pop();

        }

  

        // последний нажатый элемент

        int temp = q1.front();

  

        // очистить вспомогательную очередь после

        // последняя операция

        q1.pop();

  

        // подтолкнуть последний элемент к q2

        q2.push(temp);

  

        // меняем имена двух очередей

        queue<int> q = q1;

        q1 = q2;

        q2 = q;

        return temp;

    }

  

    int size()

    {

        return curr_size;

    }

};

  
// Код драйвера

int main()

{

    Stack s;

    s.push(1);

    s.push(2);

    s.push(3);

    s.push(4);

  

    cout << "current size: " << s.size()

         << endl;

    cout << s.top() << endl;

    s.pop();

    cout << s.top() << endl;

    s.pop();

    cout << s.top() << endl;

    cout << "current size: " << s.size()

         << endl;

    return 0;

}
// Этот код предоставлен Чхави

Джава

/ * Java-программа для реализации стека
используя две очереди * /

import java.util.*;

  

class Stack {

    Queue<Integer> q1 = new LinkedList<>(), q2 = new LinkedList<>();

    int curr_size;

  

    public Stack()

    {

        curr_size = 0;

    }

  

    void remove()

    {

        if (q1.isEmpty())

            return;

  

        // Оставляем один элемент в q1 и

        // подтолкнуть других в q2.

        while (q1.size() != 1) {

            q2.add(q1.peek());

            q1.remove();

        }

  

        // Высовываем единственный левый элемент

        // из q1

        q1.remove();

        curr_size--;

  

        // поменять местами имена двух очередей

        Queue<Integer> q = q1;

        q1 = q2;

        q2 = q;

    }

  

    void add(int x)

    {

        q1.add(x);

        curr_size++;

    }

  

    int top()

    {

        if (q1.isEmpty())

            return -1;

  

        while (q1.size() != 1) {

            q2.add(q1.peek());

            q1.remove();

        }

  

        // последний нажатый элемент

        int temp = q1.peek();

  

        // очистить вспомогательную очередь после

        // последняя операция

        q1.remove();

  

        // подтолкнуть последний элемент к q2

        q2.add(temp);

  

        // меняем имена двух очередей

        Queue<Integer> q = q1;

        q1 = q2;

        q2 = q;

        return temp;

    }

  

    int size()

    {

        return curr_size;

    }

  

    // Код драйвера

    public static void main(String[] args)

    {

        Stack s = new Stack();

        s.add(1);

        s.add(2);

        s.add(3);

        s.add(4);

  

        System.out.println("current size: " + s.size());

        System.out.println(s.top());

        s.remove();

        System.out.println(s.top());

        s.remove();

        System.out.println(s.top());

        System.out.println("current size: " + s.size());

    }

}

  
// Этот код предоставлен Принчи Сингхом

C #

using System; 

using System.Collections; 

class GfG 

    public class Stack 

    

        public Queue q1 = new Queue(); 

        public Queue q2 = new Queue(); 

        // Просто добавляем новый элемент в q1

        public void Push(int x) => q1.Enqueue(x); 

  

        // переместить все элементы с q1 на q2, кроме задней части q1.

        // Сохраняем заднюю часть q1

        // меняем местами q1 и q2

        // вернуть сохраненный результат

        public int Pop() 

        

            if (q1.Count == 0) 

                return -1; 

            while (q1.Count > 1) 

            

                q2.Enqueue(q1.Dequeue()); 

            

            int res = (int)q1.Dequeue(); 

            Queue temp = q1; 

            q1 = q2; 

            q2 = temp; 

            return res; 

        

  

        public int Size() => q1.Count; 

  

        public int Top() 

        

            if (q1.Count == 0) 

                return -1; 

            while (q1.Count > 1) 

            

                q2.Enqueue(q1.Dequeue()); 

            

            int res = (int)q1.Dequeue(); 

            q2.Enqueue(res); 

            Queue temp = q1; 

            q1 = q2; 

            q2 = temp; 

            return res; 

        

    }; 

    public static void Main(String[] args) 

    

        Stack s = new Stack(); 

    s.Push(1); 

    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 

    s.Push(7); 

    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 

    s.Push(9); 

    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 

  

    s.Pop(); 

    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 

    s.Pop(); 

    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 

  

    s.Push(5); 

    Console.WriteLine("Size of Stack: " + s.Size() + "\tTop : " + s.Top()); 

    


// Представлено Шакти Прасадом

  
// Размер стека: 1 Верх: 1
// Размер стека: 2 Верх: 7
// Размер стека: 3 Верх: 9
// Размер стека: 2 Верх: 7
// Размер стека: 1 Верх: 1
// Размер стека: 2 Верх: 5

Выход :

current size: 4
4
3
2
current size: 2

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

Эта статья составлена Sumit Jain и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

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

0.00 (0%) 0 votes