Связанные стеки и очереди - PullRequest
Новая
       31

Связанные стеки и очереди

0 голосов
/ 02 октября 2018

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

#define MAX_STACKS 10 //maximum number of stacks;
typedef struct {
        int key;
        //other fields.
}element;
typedef struct stack *stackpointer;
typedef struct {
        element data;
        stackpointer link;
}stack;
stackpointer top[MAX_STACKS];

void push(int i ,element item) {
     stackpointer temp;
     malloc(temp,sizeof(*temp));
     temp->data = item;
     temp->link = top[i];
     top[i] = temp;
}

Я новичок в структурах данных.Могу ли я получить краткое объяснение вышеуказанной концепции, то есть связанных стеков / очередей.

1 Ответ

0 голосов
/ 03 октября 2018

Итак, я проверил вашу книгу и вроде понял, в чем ваша проблема.

Такое представление оказалось эффективным, если у нас был только один стек или одна очередь.Однако, когда несколько стеков и очередей сосуществуют, не было эффективного способа представлять их последовательно

Таким образом, под последовательным пониманием следует понимать, что это означает использование массивов для представления стеков, а не связанного списка.Теперь просто предположим, что у вас есть матрица, состоящая из 10 массивов для представления каждого размера 100, и вы помещаете некоторые данные в каждый из них.Скажем, вы помещаете только несколько элементов в каждый стек, что в итоге приводит к потере большого количества данных, поскольку в матрице содержится 1000 элементов.Эта проблема возникала при использовании одного массива, но она становится более заметной, когда у вас есть несколько массивов для нескольких стеков.

Теперь, как вы, возможно, поняли, при использовании представления связанного списка стека используется столько памяти, сколько необходимос незначительными накладными расходами на отслеживание следующего элемента, в данном случае ссылка на указатель стека.

stackpointer top[MAX_STACKS]

Итак, мы создали массив типа стека указателя для сохранениятрек верхней позиции каждого отдельного стека.Поэтому теперь, когда пользователь хочет ввести элемент, он должен передать индекс (int i), а также данные (элемент элемента). 

void push(int i ,element item) 
{
     stackpointer temp;
     malloc(temp,sizeof(*temp));
     temp->data = item;
     temp->link = top[i];
     top[i] = temp;
}

Итак, мы создаем временную переменную для хранениянаши данные, которые теперь станут вершиной нашего стека, но перед этим мы должны указать их на предыдущую вершину стека (это делается в строке 5), а в строке 6 мы просто указываем вершине [i] значение temp,Тем не менее, вы можете исправить свой код следующим образом: 

stackpointer temp = (stackpointer)malloc(sizeof(element));

Если у вас есть сомнения по поводу malloc, просто обратитесь к this .Если у вас есть сомнения, дайте мне знать, и я уточню все, что вам нужно.

...