Обращение стека с использованием очереди в C - PullRequest
Новая
       14

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

0 голосов
/ 01 ноября 2019

Мне нужно перевернуть стек, используя очередь. Функция reverseStack () использует только push () и pop () при добавлении или удалении целых чисел из стека, и только enqueue () и dequeue () при добавлении или удалении целых чисел из очереди.

Но яполучил ошибку сегментации на push(&s, dequeue(&q));. Кто-нибудь может сказать мне, что это значит? Спасибо.

Вот мой код: 

void reverseStack(Stack *s) 
{
    Queue *q;

    while(!isEmptyStack(s)) //pop items from stack and queue into q
    {
        enqueue(&q, pop(s));
    }
    while(!isEmptyQueue(q)) //dequeue items from queue and push to stack
    {
        push(&s, dequeue(&q));
    }
}

Обновлено: 

typedef struct _listnode{
   int item;
   struct _listnode *next;
} ListNode;

typedef struct _linkedlist{
   int size;
   ListNode *head;
   ListNode *tail;
} LinkedList;

////////////////////////////////// stack    ///////////////////////////////////////////////////////

typedef struct stack{
    LinkedList ll;
} Stack;

//////////////////////////////////// queue ////////////////////////////////////////////////////////

typedef struct _queue{
    LinkedList ll;
} Queue;

Мне дали этот список функций, и мне нужно создать функцию reverseStack ()на основании этого. 

void push(Stack *s, int item){
   insertNode(&(s->ll), 0, item);
}

int pop(Stack *s){
   int item;
   if(!isEmptyStack(s)){
    item = ((s->ll).head)->item;
    removeNode(&(s->ll), 0);
    return item;
   }
    return INT_MIN;
}

int peek(Stack *s){
   return ((s->ll).head)->item;
}

int isEmptyStack(Stack *s){
   if ((s->ll).size == 0)
      return 1;
   return 0;
}

void enqueue(Queue *q, int item){
   insertNode(&(q->ll), q->ll.size, item);
}

int dequeue(Queue *q){
   int item;
   item = ((q->ll).head)->item;
   removeNode(&(q->ll), 0);
   return item;
}

int isEmptyQueue(Queue *q){
   if ((q->ll).size == 0)
      return 1;
   return 0;
}

1 Ответ

0 голосов
/ 02 ноября 2019

Здесь есть несколько проблем.

Ваш reverseStack метод: 

void reverseStack(Stack *s) 
{
    Queue *q;

    while(!isEmptyStack(s)) //pop items from stack and queue into q
    {
        enqueue(&q, pop(s));
    }
    while(!isEmptyQueue(q)) //dequeue items from queue and push to stack
    {
        push(&s, dequeue(&q));
    }
}

Здесь вы объявляете q, но никогда определить это. Первое, что вам нужно сделать, это заставить q указать на что-то, или, возможно, вы хотели написать: 

Queue q;

, который выделил бы место для структуры Queue в стеке процессора.

С написанным кодом я не понимаю, как он работает. Вызовы enqueue должны прекратиться, потому что q никогда не присваивается значение. Хотя я думаю, что это возможно, поскольку C является дружественным языком, так как вы передаете адрес из q, а не значение из q, выпросто повредить стек вызовов.

В любом случае, если вы не исправите это (либо сделаете q не указателем, либо присвойте ему значение, вызвав malloc), у вас будут проблемы,Если он действительно должен быть динамически распределен, то замените &q на q в этой функции.

Ваш push определяется как: 

void push(Stack *s, int item){
   insertNode(&(s->ll), 0, item);
}

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

Но в вашей reverseStack функции s уже является Stack * (указатель на стек). Но вы звоните push с адресом указателя. Вы передаете Stack ** (указатель на указатель на стек).

Правильный вызов будет: 

push(s, dequeue(q)); // or maybe dequeue(&q), depending on how you
                     // you end up defining q.

Ваш компилятор C должен был дать вам ошибки в этих строках,Или ... ну, C, будучи тем, чем он является, возможно, он просто дал вам предупреждения.

Предупреждение компилятора - не более чем скрытая ошибка. Скомпилируйте с максимально возможным уровнем предупреждений, включите опцию «предупреждения как ошибки» и исправьте каждое предупреждение .

...