在 C 中使用队列反转堆栈 [英] Reversing a stack using queue in C

问题描述

我需要使用队列来反转堆栈.reverseStack() 函数只在向堆栈中添加或移除整数时使用 push() 和 pop()，而在向队列中添加或移除整数时仅使用 enqueue() 和 dequeue().

I need to reverse a stack using queue. The reverseStack() function only uses push()and pop()when adding or removing integers from the stack, and only uses enqueue() and dequeue() when adding or removing integers from the queue.

但是我在 push(&s, dequeue(&q)); 处遇到了分段错误.谁能告诉我这是什么意思?谢谢.

But I got a segmentation fault at push(&s, dequeue(&q));. Could anyone tell me what does this mean? Thanks.

这是我的代码:

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() 函数.

I was given these list of functions and I need to create the reverseStack() function based on these.

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;
}

推荐答案

这里有几个问题.

你的 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 指向某些东西，或者您可能打算编写:

Here, you declare q, but you never define it. The first thing you need to do is make q point to something, or perhaps you meant to write:

Queue q;

这将为处理器堆栈上的 Queue 结构分配空间.

Which would allocate space for a Queue structure on the processor stack.

写的代码，我不明白它是如何工作的.对 enqueue 的调用应该终止，因为 q 从未被赋值.虽然我想这是可能的，C 是一种友好的语言，因为你传递的是 q 的 address 而不是 valueq，你只是破坏了调用堆栈.

With the code as written, I don't understand how it works. The calls to enqueue should die because q is never assigned a value. Although I guess it's possible, C being the friendly language it is, that since you're passing the address of q rather than the value of q, you're just corrupting the call stack.

在任何情况下，除非你解决这个问题(要么使 q 成为非指针，要么通过调用 malloc 为其赋值)，你将有问题.如果确实应该动态分配，则在该函数中将 &q 替换为 q.

In any event, unless you fix that (either make q a non-pointer, or assign it a value by calling malloc), you're going to have problems. If it really is supposed to be dynamically allocated, then replace &q with q in that function.

您的 push 定义为:

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

也就是说你需要传递一个 Stack *(指向堆栈的指针)作为第一个参数.

That says you need to pass a Stack * (pointer to a stack) as the first parameter.

但是在您的 reverseStack 函数中，s 已经是一个 Stack *(指向堆栈的指针).但是您正在使用指针的地址调用 push .您正在传递一个 Stack **(指向堆栈的指针).

But in your reverseStack function, s is already a Stack * (pointer to a stack). But you're calling push with the address of the pointer. You're passing a Stack ** (pointer-to-pointer to stack).

正确的调用是:

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

您的 C 编译器应该在这些行上给您错误.或者......好吧，C 就是它，也许它只是给了你警告.

Your C compiler should have given you errors on those lines. Or ... well, C being what it is, perhaps it just gave you warnings.

编译器警告只不过是变相的错误.以尽可能高的警告级别进行编译，启用警告为错误"选项，并修复每个警告.

A compiler warning is nothing more than an error in disguise. Compile with the highest possible warning level, enable the "warnings as errors" option, and fix every warning.

这篇关于在 C 中使用队列反转堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！