Рубрики

Дизайн стека с операциями над средним элементом

Как реализовать стек, который будет поддерживать следующие операции в O (1) времени сложности ?
1) push (), который добавляет элемент в начало стека.
2) pop (), который удаляет элемент из верхней части стека.
3) findMiddle (), который вернет средний элемент стека.
4) deleteMiddle (), который удалит средний элемент.
Push и pop — это стандартные операции стека.

Важный вопрос, использовать ли связанный список или массив для реализации стека?

Обратите внимание, что нам нужно найти и удалить средний элемент. Удаление элемента из середины не является O (1) для массива. Также нам может понадобиться переместить средний указатель вверх, когда мы нажимаем на элемент, и переместиться вниз, когда мы выполняем pop (). В односвязном списке перемещение среднего указателя в обоих направлениях невозможно.

Идея состоит в том, чтобы использовать двусвязный список (DLL). Мы можем удалить средний элемент за O (1), сохранив средний указатель. Мы можем перемещать средний указатель в обоих направлениях, используя предыдущий и следующий указатели.

Далее следует реализация операций push (), pop () и findMiddle (). Реализация deleteMiddle () оставлена в качестве упражнения. Если в стеке есть четные элементы, findMiddle () возвращает второй средний элемент. Например, если стек содержит {1, 2, 3, 4}, то findMiddle () вернет 3.

C ++

/ * C ++ Программа для реализации стека
который поддерживает findMiddle () и
deleteMiddle за O (1) раз * /
#include <bits/stdc++.h>

using namespace std;

  
/ * Узел двусвязного списка * /

class DLLNode 

    public:

    DLLNode *prev; 

    int data; 

    DLLNode *next; 

}; 

  
/ * Представление структуры данных стека
который поддерживает findMiddle () в O (1) раз.
Стек реализован с использованием двусвязного списка.
Поддерживает указатель на головной узел, указатель на
средний узел и количество узлов * /

class myStack 

    public:

    DLLNode *head; 

    DLLNode *mid; 

    int count; 

}; 

  
/ * Функция для создания структуры данных стека * /
myStack *createMyStack() 

    myStack *ms = new myStack();

    ms->count = 0; 

    return ms; 

}; 

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

void push(myStack *ms, int new_data) 

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

    DLLNode* new_DLLNode = new DLLNode();

    new_DLLNode->data = new_data; 

  

    / * Так как мы добавляем в начале,

    prev всегда NULL * /

    new_DLLNode->prev = NULL; 

  

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

    new_DLLNode->next = ms->head; 

  

    / * Увеличение количества предметов в стеке * /

    ms->count += 1; 

  

    / * Изменить средний указатель в двух случаях

    1) Связанный список пуст

    2) Количество узлов в связанном списке нечетное * /

    if (ms->count == 1) 

    

        ms->mid = new_DLLNode; 

    

    else

    

        ms->head->prev = new_DLLNode; 

  

        if(!(ms->count & 1)) // Обновление середины, если ms-> count четное

        ms->mid = ms->mid->prev; 

    

  

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

    ms->head = new_DLLNode; 

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

int pop(myStack *ms) 

    / * Переполнение стека * /

    if (ms->count == 0) 

    

        cout<<"Stack is empty\n"

        return -1; 

    

  

    DLLNode *head = ms->head; 

    int item = head->data; 

    ms->head = head->next; 

  

    // Если связанный список не

    // становимся пустыми, обновляем пред

    // новой головы как NULL

    if (ms->head != NULL) 

        ms->head->prev = NULL; 

  

    ms->count -= 1; 

  

    // обновляем средний указатель, когда

    // у нас есть нечетное число

    // элементы в стеке, i, e

    // сдвинуть средний указатель

    if ((ms->count) & 1 ) 

        ms->mid = ms->mid->next; 

  

    free(head); 

  

    return item; 

  
// Функция для нахождения середины стека

int findMiddle(myStack *ms) 

    if (ms->count == 0) 

    

        cout << "Stack is empty now\n"

        return -1; 

    

  

    return ms->mid->data; 

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

int main() 

    / * Давайте создадим стек с помощью операции push () * /

    myStack *ms = createMyStack(); 

    push(ms, 11); 

    push(ms, 22); 

    push(ms, 33); 

    push(ms, 44); 

    push(ms, 55); 

    push(ms, 66); 

    push(ms, 77); 

  

    cout << "Item popped is " << pop(ms) << endl; 

    cout << "Item popped is " << pop(ms) << endl; 

    cout << "Middle Element is " << findMiddle(ms) << endl; 

    return 0; 

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

С

/ * Программа для реализации стека, который поддерживает findMiddle () и deleteMiddle

   за O (1) время * /

#include <stdio.h>
#include <stdlib.h>

  
/ * Узел двусвязного списка * /

struct DLLNode

{

    struct DLLNode *prev;

    int data;

    struct DLLNode *next;

};

  
/ * Представление структуры данных стека, которая поддерживает findMiddle ()

   в O (1) раз. Стек реализован с использованием двусвязного списка. Это

   поддерживает указатель на головной узел, указатель на средний узел и количество

   узлы * /

struct myStack

{

    struct DLLNode *head;

    struct DLLNode *mid;

    int count;

};

  
/ * Функция для создания структуры данных стека * /

struct myStack *createMyStack()

{

    struct myStack *ms =

               (struct myStack*) malloc(sizeof(struct myStack));

    ms->count = 0;

    return ms;

};

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

void push(struct myStack *ms, int new_data)

{

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

    struct DLLNode* new_DLLNode =

               (struct DLLNode*) malloc(sizeof(struct DLLNode));

    new_DLLNode->data  = new_data;

  

    / * Так как мы добавляем в начале,

      prev всегда NULL * /

    new_DLLNode->prev = NULL;

  

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

    new_DLLNode->next = ms->head;

  

    / * Увеличение количества предметов в стеке * /

    ms->count += 1;

  

    / * Изменить средний указатель в двух случаях

       1) Связанный список пуст

       2) Количество узлов в связанном списке нечетное * /

    if (ms->count == 1)

    {

         ms->mid = new_DLLNode;

    }

    else

    {

        ms->head->prev = new_DLLNode;

  

        if (ms->count & 1) // Обновление середины, если ms-> count нечетно

           ms->mid = ms->mid->prev;

    }

  

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

    ms->head  = new_DLLNode;

}

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

int pop(struct myStack *ms)

{

    / * Переполнение стека * /

    if (ms->count  ==  0)

    {

        printf("Stack is empty\n");

        return -1;

    }

  

    struct DLLNode *head = ms->head;

    int item = head->data;

    ms->head = head->next;

  

    // Если связанный список не становится пустым, обновить пред.

    // новой головы как NULL

    if (ms->head != NULL)

        ms->head->prev = NULL;

  

    ms->count -= 1;

  

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

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

    if (!((ms->count) & 1 ))

        ms->mid = ms->mid->next;

  

    free(head);

  

    return item;

}

  
// Функция для нахождения середины стека

int findMiddle(struct myStack *ms)

{

    if (ms->count  ==  0)

    {

        printf("Stack is empty now\n");

        return -1;

    }

  

    return ms->mid->data;

}

  
// Драйвер программы для тестирования функций myStack

int main()

{

    / * Давайте создадим стек с помощью операции push () * /

    struct myStack *ms = createMyStack();

    push(ms, 11);

    push(ms, 22);

    push(ms, 33);

    push(ms, 44);

    push(ms, 55);

    push(ms, 66);

    push(ms, 77);

  

    printf("Item popped is %d\n", pop(ms));

    printf("Item popped is %d\n", pop(ms));

    printf("Middle Element is %d\n", findMiddle(ms));

    return 0;

}

Джава

/ * Java-программа для реализации стека, который поддерживает findMiddle () и deleteMiddle
за O (1) время * /

  

public class GFG 

{

    / * Узел двусвязного списка * /

    class DLLNode

    {

        DLLNode prev;

        int data;

        DLLNode next;

        DLLNode(int d){data=d;}

    }

      

    / * Представление структуры данных стека, которая поддерживает findMiddle ()

       в O (1) раз. Стек реализован с использованием двусвязного списка. Это

       поддерживает указатель на головной узел, указатель на средний узел и количество

       узлы * /

    class myStack

    {

        DLLNode head;

        DLLNode mid;

        int count;

    }

      

  

    / * Функция для создания структуры данных стека * /

    myStack createMyStack()

    {

        myStack ms = new myStack();

        ms.count = 0;

        return ms;

    }

      

  

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

    void push(myStack ms, int new_data)

    {

  

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

        DLLNode new_DLLNode = new DLLNode(new_data);

          

  

        / * Так как мы добавляем в начале,

          prev всегда NULL * /

        new_DLLNode.prev = null;

          

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

        new_DLLNode.next = ms.head;

          

        / * Увеличение количества предметов в стеке * /

        ms.count += 1;

          

        / * Изменить средний указатель в двух случаях

           1) Связанный список пуст

           2) Количество узлов в связанном списке нечетное * /

        if(ms.count == 1)

        {

            ms.mid=new_DLLNode;

        }

        else

        {

            ms.head.prev = new_DLLNode;

              

            if((ms.count % 2) != 0) // Обновление середины, если ms-> count нечетно

                ms.mid=ms.mid.prev;

        }

          

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

        ms.head = new_DLLNode;

          

    }

      

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

    int pop(myStack ms)

    {

        / * Переполнение стека * /

        if(ms.count == 0)

        {

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

            return -1;

        }

          

        DLLNode head = ms.head;

        int item = head.data;

        ms.head = head.next;

          

        // Если связанный список не становится пустым, обновить пред.

        // новой головы как NULL

        if(ms.head != null)

            ms.head.prev = null;

          

        ms.count -= 1;

          

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

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

        if(ms.count % 2 == 0)

            ms.mid=ms.mid.next;

          

        return item;

    }

      

    // Функция для нахождения середины стека

    int findMiddle(myStack ms)

    {

        if(ms.count == 0)

        {

            System.out.println("Stack is empty now");

            return -1;

        }

        return ms.mid.data;

    }

      

    // Драйвер программы для тестирования функций myStack

    public static void main(String args[])

    {

        GFG ob = new GFG();

        myStack ms = ob.createMyStack();

        ob.push(ms, 11);

        ob.push(ms, 22);

        ob.push(ms, 33);

        ob.push(ms, 44);

        ob.push(ms, 55);

        ob.push(ms, 66);

        ob.push(ms, 77);

          

        System.out.println("Item popped is " + ob.pop(ms));

        System.out.println("Item popped is " + ob.pop(ms));

        System.out.println("Middle Element is " + ob.findMiddle(ms));

    }

}

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

C #

/ * C # Программа для реализации стека
который поддерживает findMiddle ()
и deleteMiddle за O (1) раз * /

using System;

  

class GFG 

{

    / * Узел двусвязного списка * /

    public class DLLNode

    {

        public DLLNode prev;

        public int data;

        public DLLNode next;

        public DLLNode(int d)

        {

            data=d;

        }

    }

      

    / * Представление стека

    структура данных, которая поддерживает

    findMiddle () за O (1) раз.

    Стек реализован с использованием

    Вдвойне связанный список. Поддерживает

    указатель на головной узел, указатель

    в средний узел и количество

    узлы * /

    public class myStack

    {

        public DLLNode head;

        public DLLNode mid;

        public int count;

    }

      

  

    / * Функция для создания структуры данных стека * /

    myStack createMyStack()

    {

        myStack ms = new myStack();

        ms.count = 0;

        return ms;

    }

      

  

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

    void push(myStack ms, int new_data)

    {

  

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

        DLLNode new_DLLNode = new DLLNode(new_data);

          

  

        / * Так как мы добавляем в начале,

        prev всегда NULL * /

        new_DLLNode.prev = null;

          

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

        new_DLLNode.next = ms.head;

          

        / * Увеличение количества предметов в стеке * /

        ms.count += 1;

          

        / * Изменить средний указатель в двух случаях

        1) Связанный список пуст

        2) Количество узлов в связанном списке нечетное * /

        if(ms.count == 1)

        {

            ms.mid=new_DLLNode;

        }

        else

        {

            ms.head.prev = new_DLLNode;

              

            // Обновление середины, если ms-> count нечетно

            if((ms.count % 2) != 0) 

                ms.mid=ms.mid.prev;

        }

          

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

        ms.head = new_DLLNode;

          

    }

      

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

    int pop(myStack ms)

    {

        / * Переполнение стека * /

        if(ms.count == 0)

        {

            Console.WriteLine("Stack is empty");

            return -1;

        }

          

        DLLNode head = ms.head;

        int item = head.data;

        ms.head = head.next;

          

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

        // обновляем prev новой головы как NULL

        if(ms.head != null)

            ms.head.prev = null;

          

        ms.count -= 1;

          

        // обновляем средний указатель, когда

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

        // в стеке, я двигаюсь вниз

        // средний указатель.

        if(ms.count % 2 == 0)

            ms.mid=ms.mid.next;

          

        return item;

    }

      

    // Функция для нахождения середины стека

    int findMiddle(myStack ms)

    {

        if(ms.count == 0)

        {

            Console.WriteLine("Stack is empty now");

            return -1;

        }

        return ms.mid.data;

    }

      

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

    public static void Main(String []args)

    {

        GFG ob = new GFG();

        myStack ms = ob.createMyStack();

        ob.push(ms, 11);

        ob.push(ms, 22);

        ob.push(ms, 33);

        ob.push(ms, 44);

        ob.push(ms, 55);

        ob.push(ms, 66);

        ob.push(ms, 77);

          

        Console.WriteLine("Item popped is "

                            ob.pop(ms));

        Console.WriteLine("Item popped is "

                            ob.pop(ms));

        Console.WriteLine("Middle Element is " +

                            ob.findMiddle(ms));

    }

}

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


Выход:

Item popped is 77
Item popped is 66
Middle Element is 33

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

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

Дизайн стека с операциями над средним элементом

0.00 (0%) 0 votes