Рубрики

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

Проблема противоположна этому посту. Нам дана структура данных стека с операциями push и pop, задача состоит в том, чтобы реализовать очередь, используя экземпляры структуры данных стека и операций с ними.

Очередь может быть реализована с использованием двух стеков. Пусть реализуемая очередь будет q, а стеки, используемые для реализации q, будут stack1 и stack2. q может быть реализовано двумя способами:

Метод 1 (делая операцию enQueue дорогостоящей) Этот метод гарантирует, что самый старый введенный элемент всегда находится на вершине стека 1, так что операция deQueue просто появляется из stack1. Чтобы поместить элемент в верхнюю часть stack1, используется stack2.

enQueue(q, x):

  • While stack1 is not empty, push everything from stack1 to stack2.
  • Push x to stack1 (assuming size of stacks is unlimited).
  • Push everything back to stack1.

Here time complexity will be O(n)

deQueue(q):

  • If stack1 is empty then error
  • Pop an item from stack1 and return it

Here time complexity will be O(1)

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

C ++

// Программа CPP для реализации очереди
// два стека с дорогостоящим enQueue ()
#include <bits/stdc++.h>

using namespace std;

  

struct Queue {

    stack<int> s1, s2;

  

    void enQueue(int x)

    {

        // Переместить все элементы из s1 в s2

        while (!s1.empty()) {

            s2.push(s1.top());

            s1.pop();

        }

  

        // Вставить элемент в s1

        s1.push(x);

  

        // Отодвинуть все обратно на s1

        while (!s2.empty()) {

            s1.push(s2.top());

            s2.pop();

        }

    }

  

    // Удалить элемент из очереди

    int deQueue()

    {

        // если первый стек пуст

        if (s1.empty()) {

            cout << "Q is Empty";

            exit(0);

        }

  

        // Вернуть вершину s1

        int x = s1.top();

        s1.pop();

        return x;

    }

};

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

int main()

{

    Queue q;

    q.enQueue(1);

    q.enQueue(2);

    q.enQueue(3);

  

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

  

    return 0;

}

Джава

// Java-программа для реализации Queue с использованием
// два стека с дорогостоящим enQueue ()

import java.util.*;

  

class GFG 

static class Queue 

    static Stack<Integer> s1 = new Stack<Integer>(); 

    static Stack<Integer> s2 = new Stack<Integer>(); 

  

    static void enQueue(int x) 

    

        // Переместить все элементы из s1 в s2

        while (!s1.isEmpty())

        

            s2.push(s1.pop()); 

            //s1.pop ();

        

  

        // Вставить элемент в s1

        s1.push(x); 

  

        // Отодвинуть все обратно на s1

        while (!s2.isEmpty()) 

        

            s1.push(s2.pop()); 

            //s2.pop ();

        

    

  

    // Удалить элемент из очереди

    static int deQueue() 

    

        // если первый стек пуст

        if (s1.isEmpty()) 

        

            System.out.println("Q is Empty"); 

            System.exit(0); 

        

  

        // Вернуть вершину s1

        int x = s1.peek(); 

        s1.pop(); 

        return x; 

    

}; 

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

public static void main(String[] args) 

    Queue q = new Queue(); 

    q.enQueue(1); 

    q.enQueue(2); 

    q.enQueue(3); 

  

    System.out.println(q.deQueue()); 

    System.out.println(q.deQueue());

    System.out.println(q.deQueue());


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

python3

# Python3 программа для реализации Queue с использованием
# два стека с дорогостоящим enQueue ()

  

class Queue: 

    def __init__(self):

        self.s1 = []

        self.s2 = []

  

    def enQueue(self, x):

          

        # Переместить все элементы из s1 в s2

        while len(self.s1) != 0

            self.s2.append(self.s1[-1]) 

            self.s1.pop()

  

        # Вставить элемент в self.s1

        self.s1.append(x) 

  

        # Подтолкнуть все обратно к s1

        while len(self.s2) != 0

            self.s1.append(self.s2[-1]) 

            self.s2.pop()

  

    # Удалить элемент из очереди

    def deQueue(self):

          

            # если первый стек пуст

        if len(self.s1) == 0

            print("Q is Empty")

      

        # Вернуть вершину self.s1

        x = self.s1[-1

        self.s1.pop() 

        return x

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

if __name__ == '__main__':

    q = Queue()

    q.enQueue(1

    q.enQueue(2

    q.enQueue(3

  

    print(q.deQueue())

    print(q.deQueue())

    print(q.deQueue())

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

C #

// C # программа для реализации Queue с использованием
// два стека с дорогостоящим enQueue ()

using System;

using System.Collections;

  

class GFG 

      

public class Queue 

    public Stack s1 = new Stack(); 

    public Stack s2 = new Stack(); 

  

    public void enQueue(int x) 

    

        // Переместить все элементы из s1 в s2

        while (s1.Count > 0) 

        

            s2.Push(s1.Pop()); 

            //s1.Pop ();

        

  

        // Вставить элемент в s1

        s1.Push(x); 

  

        // Отодвинуть все обратно на s1

        while (s2.Count > 0) 

        

            s1.Push(s2.Pop()); 

            //s2.Pop ();

        

    

  

    // Удалить элемент из очереди

    public int deQueue() 

    

        // если первый стек пуст

        if (s1.Count == 0) 

        

            Console.WriteLine("Q is Empty"); 

              

        

  

        // Вернуть вершину s1

        int x = (int)s1.Peek(); 

        s1.Pop(); 

        return x; 

    

}; 

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

public static void Main() 

    Queue q = new Queue(); 

    q.enQueue(1); 

    q.enQueue(2); 

    q.enQueue(3); 

  

    Console.Write(q.deQueue()+" "); 

    Console.Write(q.deQueue()+" "); 

    Console.Write(q.deQueue()); 


  
// Этот код предоставлен
// Субхадип Гупта


Выход:

1
2
3

Метод 2 (Делая операцию deQueue дорогостоящей) В этом методе в операции en-queue новый элемент вводится в верхней части stack1. В операции удаления очереди, если стек2 пуст, тогда все элементы перемещаются в стек2 и, наконец, возвращается вершина стека2.

enQueue(q,  x)
  1) Push x to stack1 (assuming size of stacks is unlimited).
Here time complexity will be O(1)

deQueue(q)
  1) If both stacks are empty then error.
  2) If stack2 is empty
       While stack1 is not empty, push everything from stack1 to stack2.
  3) Pop the element from stack2 and return it.
Here time complexity will be O(n)

Метод 2 определенно лучше, чем метод 1.
Метод 1 перемещает все элементы дважды в операции enQueue, в то время как метод 2 (в операции deQueue) перемещает элементы один раз и перемещает элементы, только если stack2 пуст. Таким образом, амортизируемая сложность операции удаления становится ,
Реализация метода 2:

C ++

// Программа CPP для реализации очереди
// два стека с дорогостоящим deQueue ()
#include <bits/stdc++.h>

using namespace std;

  

struct Queue {

    stack<int> s1, s2;

  

    // помещаем элемент в очередь

    void enQueue(int x)

    {

        // Вставить элемент в первый стек

        s1.push(x);

    }

  

    // Удалить элемент из очереди

    int deQueue()

    {

        // если оба стека пусты

        if (s1.empty() && s2.empty()) {

            cout << "Q is empty";

            exit(0);

        }

  

        // если s2 пусто, переместить

        // элементы из s1

        if (s2.empty()) {

            while (!s1.empty()) {

                s2.push(s1.top());

                s1.pop();

            }

        }

  

        // возвращаем верхний элемент из s2

        int x = s2.top();

        s2.pop();

        return x;

    }

};

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

int main()

{

    Queue q;

    q.enQueue(1);

    q.enQueue(2);

    q.enQueue(3);

  

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

  

    return 0;

}

С

/ * C Программа для реализации очереди с использованием двух стеков * /
#include <stdio.h>
#include <stdlib.h>

  
/ * структура стекового узла * /

struct sNode {

    int data;

    struct sNode* next;

};

  
/ * Функция для перемещения элемента в стек * /

void push(struct sNode** top_ref, int new_data);

  
/ * Функция извлечения элемента из стека * /

int pop(struct sNode** top_ref);

  
/ * структура очереди с двумя стеками * /

struct queue {

    struct sNode* stack1;

    struct sNode* stack2;

};

  
/ * Функция для помещения элемента в очередь * /

void enQueue(struct queue* q, int x)

{

    push(&q->stack1, x);

}

  
/ * Функция для удаления элемента из очереди * /

int deQueue(struct queue* q)

{

    int x;

  

    / * Если оба стека пусты, то ошибка * /

    if (q->stack1 == NULL && q->stack2 == NULL) {

        printf("Q is empty");

        getchar();

        exit(0);

    }

  

    / * Переместить элементы из стека 1 в стек 2, только если

       стек2 пуст * /

    if (q->stack2 == NULL) {

        while (q->stack1 != NULL) {

            x = pop(&q->stack1);

            push(&q->stack2, x);

        }

    }

  

    x = pop(&q->stack2);

    return x;

}

  
/ * Функция для перемещения элемента в стек * /

void push(struct sNode** top_ref, int new_data)

{

    / * выделить узел * /

    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));

    if (new_node == NULL) {

        printf("Stack overflow \n");

        getchar();

        exit(0);

    }

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*top_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*top_ref) = new_node;

}

  
/ * Функция извлечения элемента из стека * /

int pop(struct sNode** top_ref)

{

    int res;

    struct sNode* top;

  

    / * Если стек пуст, то ошибка * /

    if (*top_ref == NULL) {

        printf("Stack underflow \n");

        getchar();

        exit(0);

    }

    else {

        top = *top_ref;

        res = top->data;

        *top_ref = top->next;

        free(top);

        return res;

    }

}

  
/ * Функция драйвера для проверки всех функций * /

int main()

{

    / * Создать очередь с элементами 1 2 3 * /

    struct queue* q = (struct queue*)malloc(sizeof(struct queue));

    q->stack1 = NULL;

    q->stack2 = NULL;

    enQueue(q, 1);

    enQueue(q, 2);

    enQueue(q, 3);

  

    / * Элементы из очереди * /

    printf("%d ", deQueue(q));

    printf("%d ", deQueue(q));

    printf("%d ", deQueue(q));

  

    return 0;

}

Джава

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

  

import java.util.Stack;

  

public class GFG {

    / * класс очереди с двумя стеками * /

    static class Queue {

        Stack<Integer> stack1;

        Stack<Integer> stack2;

    }

  

    / * Функция для перемещения элемента в стек * /

    static void push(Stack<Integer> top_ref, int new_data)

    {

        // Поместить данные в стек

        top_ref.push(new_data);

    }

  

    / * Функция извлечения элемента из стека * /

    static int pop(Stack<Integer> top_ref)

    {

        / * Если стек пуст, то ошибка * /

        if (top_ref.isEmpty()) {

            System.out.println("Stack Underflow");

            System.exit(0);

        }

  

        // выталкиваем данные из стека

        return top_ref.pop();

    }

  

    // Функция для постановки элемента в очередь

    static void enQueue(Queue q, int x)

    {

        push(q.stack1, x);

    }

  

    / * Функция для удаления элемента из очереди * /

    static int deQueue(Queue q)

    {

        int x;

  

        / * Если оба стека пусты, то ошибка * /

        if (q.stack1.isEmpty() && q.stack2.isEmpty()) {

            System.out.println("Q is empty");

            System.exit(0);

        }

  

        / * Переместить элементы из стека 1 в стек 2, только если

        стек2 пуст * /

        if (q.stack2.isEmpty()) {

            while (!q.stack1.isEmpty()) {

                x = pop(q.stack1);

                push(q.stack2, x);

            }

        }

        x = pop(q.stack2);

        return x;

    }

  

    / * Функция драйвера для проверки вышеуказанных функций * /

    public static void main(String args[])

    {

        / * Создать очередь с элементами 1 2 3 * /

        Queue q = new Queue();

        q.stack1 = new Stack<>();

        q.stack2 = new Stack<>();

        enQueue(q, 1);

        enQueue(q, 2);

        enQueue(q, 3);

  

        / * Элементы из очереди * /

        System.out.print(deQueue(q) + " ");

        System.out.print(deQueue(q) + " ");

        System.out.println(deQueue(q) + " ");

    }

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

C #

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

using System;

using System.Collections.Generic; 

  

class GFG 

{

    / * класс очереди с двумя стеками * /

    public class Queue

    {

        public Stack<int> stack1;

        public Stack<int> stack2;

    }

  

    / * Функция для перемещения элемента в стек * /

    static void push(Stack<int> top_ref, int new_data)

    {

        // Поместить данные в стек

        top_ref.Push(new_data);

    }

  

    / * Функция извлечения элемента из стека * /

    static int pop(Stack<int> top_ref)

    {

        / * Если стек пуст, то ошибка * /

        if (top_ref.Count == 0) 

        {

            Console.WriteLine("Stack Underflow");

            Environment.Exit(0);

        }

  

        // выталкиваем данные из стека

        return top_ref.Pop();

    }

  

    // Функция для постановки элемента в очередь

    static void enQueue(Queue q, int x)

    {

        push(q.stack1, x);

    }

  

    / * Функция для удаления элемента из очереди * /

    static int deQueue(Queue q)

    {

        int x;

  

        / * Если оба стека пусты, то ошибка * /

        if (q.stack1.Count == 0 && q.stack2.Count == 0)

        {

            Console.WriteLine("Q is empty");

            Environment.Exit(0);

        }

  

        / * Переместить элементы из стека 1 в стек 2, только если

        стек2 пуст * /

        if (q.stack2.Count == 0) 

        {

            while (q.stack1.Count != 0) 

            {

                x = pop(q.stack1);

                push(q.stack2, x);

            }

        }

        x = pop(q.stack2);

        return x;

    }

  

    / * Код водителя * /

    public static void Main(String []args)

    {

        / * Создать очередь с элементами 1 2 3 * /

        Queue q = new Queue();

        q.stack1 = new Stack<int>();

        q.stack2 = new Stack<int>();

        enQueue(q, 1);

        enQueue(q, 2);

        enQueue(q, 3);

  

        / * Элементы из очереди * /

        Console.Write(deQueue(q) + " ");

        Console.Write(deQueue(q) + " ");

        Console.WriteLine(deQueue(q) + " ");

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

1 2 3 

Очередь также может быть реализована с использованием одного пользовательского стека и одного стека вызовов функций. Ниже приведен модифицированный метод 2, в котором рекурсия (или стек вызовов функций) используется для реализации очереди с использованием только одного определенного пользователем стека.

enQueue(x)
  1) Push x to stack1.

deQueue:
  1) If stack1 is empty then error.
  2) If stack1 has only one element then return it.
  3) Recursively pop everything from the stack1, store the popped item 
    in a variable res,  push the res back to stack1 and return res

Шаг 3 гарантирует, что последний извлеченный элемент всегда возвращается, и поскольку рекурсия останавливается, когда в stack1 есть только один элемент (шаг 2), мы получаем последний элемент stack1 в deQueue (), а все остальные элементы возвращаются обратно. шаг

3. Реализация метода 2 с использованием стека вызовов функций:

C ++

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

using namespace std;

  

struct Queue {

    stack<int> s;

  

    // помещаем элемент в очередь

    void enQueue(int x)

    {

        s.push(x);

    }

  

    // Удалить элемент из очереди

    int deQueue()

    {

        if (s.empty()) {

            cout << "Q is empty";

            exit(0);

        }

  

        // выталкиваем элемент из стека

        int x = s.top();

        s.pop();

  

        // если стек становится пустым, возвращаем

        // всплывающий элемент

        if (s.empty())

            return x;

  

        // рекурсивный вызов

        int item = deQueue();

  

        // вставляем вытолкнутый элемент обратно в стек

        s.push(x);

  

        // возвращаем результат вызова deQueue ()

        return item;

    }

};

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

int main()

{

    Queue q;

    q.enQueue(1);

    q.enQueue(2);

    q.enQueue(3);

  

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

    cout << q.deQueue() << '\n';

  

    return 0;

}

С

/ * Программа для реализации очереди с использованием одного определенного пользователем стека
и один стек вызовов функций * /
#include <stdio.h>
#include <stdlib.h>

  
/ * структура стекового узла * /

struct sNode {

    int data;

    struct sNode* next;

};

  
/ * структура очереди с двумя стеками * /

struct queue {

    struct sNode* stack1;

};

  
/ * Функция для перемещения элемента в стек * /

void push(struct sNode** top_ref, int new_data);

  
/ * Функция извлечения элемента из стека * /

int pop(struct sNode** top_ref);

  
/ * Функция для помещения элемента в очередь * /

void enQueue(struct queue* q, int x)

{

    push(&q->stack1, x);

}

  
/ * Функция для удаления элемента из очереди * /

int deQueue(struct queue* q)

{

    int x, res;

  

    / * Если оба стека пусты, то ошибка * /

    if (q->stack1 == NULL) {

        printf("Q is empty");

        getchar();

        exit(0);

    }

    else if (q->stack1->next == NULL) {

        return pop(&q->stack1);

    }

    else {

        / * вытолкнуть предмет из стека1 * /

        x = pop(&q->stack1);

  

        / * сохранить последний оставленный товар * /

        res = deQueue(q);

  

        / * вернуть все обратно в стек1 * /

        push(&q->stack1, x);

        return res;

    }

}

  
/ * Функция для перемещения элемента в стек * /

void push(struct sNode** top_ref, int new_data)

{

    / * выделить узел * /

    struct sNode* new_node = (struct sNode*)malloc(sizeof(struct sNode));

  

    if (new_node == NULL) {

        printf("Stack overflow \n");

        getchar();

        exit(0);

    }

  

    / * вставить данные * /

    new_node->data = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*top_ref);

  

    / * переместить голову, чтобы указать на новый узел * /

    (*top_ref) = new_node;

}

  
/ * Функция извлечения элемента из стека * /

int pop(struct sNode** top_ref)

{

    int res;

    struct sNode* top;

  

    / * Если стек пуст, то ошибка * /

    if (*top_ref == NULL) {

        printf("Stack underflow \n");

        getchar();

        exit(0);

    }

    else {

        top = *top_ref;

        res = top->data;

        *top_ref = top->next;

        free(top);

        return res;

    }

}

  
/ * Функция драйвера для проверки вышеуказанных функций * /

int main()

{

    / * Создать очередь с элементами 1 2 3 * /

    struct queue* q = (struct queue*)malloc(sizeof(struct queue));

    q->stack1 = NULL;

  

    enQueue(q, 1);

    enQueue(q, 2);

    enQueue(q, 3);

  

    / * Элементы из очереди * /

    printf("%d ", deQueue(q));

    printf("%d ", deQueue(q));

    printf("%d ", deQueue(q));

  

    return 0;

}

Джава

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

  

import java.util.Stack;

  

public class QOneStack {

    // класс очереди с двумя стеками

    static class Queue {

        Stack<Integer> stack1;

    }

  

    / * Функция для перемещения элемента в стек * /

    static void push(Stack<Integer> top_ref, int new_data)

    {

        / * вставить данные * /

        top_ref.push(new_data);

    }

  

    / * Функция извлечения элемента из стека * /

    static int pop(Stack<Integer> top_ref)

    {

        / * Если стек пуст, то ошибка * /

        if (top_ref == null) {

            System.out.println("Stack Underflow");

            System.exit(0);

        }

        // вернуть элемент из стека

        return top_ref.pop();

    }

  

    / * Функция для помещения элемента в очередь * /

    static void enQueue(Queue q, int x)

    {

        push(q.stack1, x);

    }

  

    / * Функция для удаления элемента из очереди * /

    static int deQueue(Queue q)

    {

        int x, res = 0;

        / * Если стеки пустые, то ошибка * /

        if (q.stack1.isEmpty()) {

            System.out.println("Q is Empty");

            System.exit(0);

        }

        // Проверяем, является ли это последним элементом стека

        else if (q.stack1.size() == 1) {

            return pop(q.stack1);

        }

        else {

  

            / * вытолкнуть предмет из стека1 * /

            x = pop(q.stack1);

  

            / * сохранить последний оставленный товар * /

            res = deQueue(q);

  

            / * вернуть все обратно в стек1 * /

            push(q.stack1, x);

            return res;

        }

        return 0;

    }

  

    / * Функция драйвера для проверки вышеуказанных функций * /

    public static void main(String[] args)

    {

        / * Создать очередь с элементами 1 2 3 * /

        Queue q = new Queue();

        q.stack1 = new Stack<>();

  

        enQueue(q, 1);

        enQueue(q, 2);

        enQueue(q, 3);

  

        / * Элементы из очереди * /

        System.out.print(deQueue(q) + " ");

        System.out.print(deQueue(q) + " ");

        System.out.print(deQueue(q) + " ");

    }

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

C #

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

using System;

using System.Collections.Generic; 

  

public class QOneStack

{

    // класс очереди с двумя стеками

    public class Queue 

    {

        public Stack<int> stack1;

    }

  

    / * Функция для перемещения элемента в стек * /

    static void push(Stack<int> top_ref, int new_data)

    {

        / * вставить данные * /

        top_ref.Push(new_data);

    }

  

    / * Функция извлечения элемента из стека * /

    static int pop(Stack<int> top_ref)

    {

        / * Если стек пуст, то ошибка * /

        if (top_ref == null)

        {

            Console.WriteLine("Stack Underflow");

            Environment.Exit(0);

        }

        // вернуть элемент из стека

        return top_ref.Pop();

    }

  

    / * Функция для помещения элемента в очередь * /

    static void enQueue(Queue q, int x)

    {

        push(q.stack1, x);

    }

  

    / * Функция для удаления элемента из очереди * /

    static int deQueue(Queue q)

    {

        int x, res = 0;

          

        / * Если стеки пустые, то ошибка * /

        if (q.stack1.Count == 0)

        {

            Console.WriteLine("Q is Empty");

            Environment.Exit(0);

        }

          

        // Проверяем, является ли это последним элементом стека

        else if (q.stack1.Count == 1) 

        {

            return pop(q.stack1);

        }

        else 

        {

  

            / * вытолкнуть предмет из стека1 * /

            x = pop(q.stack1);

  

            / * сохранить последний оставленный товар * /

            res = deQueue(q);

  

            / * вернуть все обратно в стек1 * /

            push(q.stack1, x);

            return res;

        }

        return 0;

    }

  

    / * Функция драйвера для проверки вышеуказанных функций * /

    public static void Main(String[] args)

    {

        / * Создать очередь с элементами 1 2 3 * /

        Queue q = new Queue();

        q.stack1 = new Stack<int>();

  

        enQueue(q, 1);

        enQueue(q, 2);

        enQueue(q, 3);

  

        / * Элементы из очереди * /

        Console.Write(deQueue(q) + " ");

        Console.Write(deQueue(q) + " ");

        Console.Write(deQueue(q) + " ");

    }

}

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


Выход:

1 2 3 

Спрашивается в: Inmobi , Accolite , Adobe , Amazon , DE Shaw , Flipkart , Goldman Sachs , InfoEdge , MakeMyTrip , Microsoft , Oracle

Пожалуйста, пишите комментарии, если вы обнаружите, что какой-либо из приведенных выше кодов / алгоритмов неверен, или найдете лучшие способы решения той же проблемы

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

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

0.00 (0%) 0 votes