使用C ++的双向链表的LIFO堆栈 [英] A LIFO stack using doubly linked list by C++

问题描述

亲爱的：



当我调用函数 LIFO 堆栈>推它工作正常（我在 push 函数中插入了 printf 语句），但 pop 函数依次调用 isQueueEmpty 函数，最后一个，返回堆栈为空，顶部指针指向 NULL 。



任何人都可以帮助我吗？

提前感谢...

Dear all:

I write this programe to simulate a LIFO stack using doubly linked list, when i call the function push it is work correctly (i had inserted a printf statement in push function), but the pop function in turn calls isQueueEmpty function which, the last, return that the stack is empty and the top pointer points to NULL.

can anyone help me??
thank in advance...

class c
{	public:
	node *top;
	node *ptr;
	.
	.
	.
        bool isQueueEmpty();
	void push(c*);
	c* pop();
};

bool c::isQueueEmpty()
{
	if(this->top == NULL) return true;
	else return false;
}

void c::push(c* ss)
{
	if(this->isQueueEmpty()){ this->top = ss->ptr; this->top->next = this->top->prev = NULL;}
	else { ss->ptr->prev = this->top; this->top->next = ss->ptr; this->top = ss->ptr; ss->ptr->next = NULL;}
}

c* c::pop()
{
	if(this->isQueueEmpty()){ printf("You are trying to get data from empty queue ... \n\n"); return NULL;}
	c* evictedN = new c();
	evictedN->ptr = this->top;
	top = top->prev;
	top->next = NULL;
	return evictedN;
}

主要：

in the main:

c* s = new c(istate); // istate is a 2D array
    s->push(c1);
    s->push(c2);
    s->push(c3);
    .
    .
    .
c* queuedState = s->pop();

当最后一行被调​​用时， pop（）函数依次有调用 isQueueEmpty（）函数，返回顶部指针指向 NULL ，堆栈为空， pop（）依次打印< b> 您正试图从空队列中获取数据......

when the last line was called, the pop() function in turn it had called the isQueueEmpty() function, which returns that top pointer points to NULL and the stack is empty, and pop() in turn prints "You are trying to get data from empty queue ..."

推荐答案

存在一个概念错误代码：您使用相同的类c作为堆栈以及使用该堆栈管理的元素。这不是很聪明，因为每个元素都包含用于堆栈管理的附加数据成员。



其次，您的代码格式不正确且冗余使用这个 - >让它难以阅读。



那么代码

There is a concptional error in you code: You are using the same class c for your stack and for the elements that you manage with that stack. That's not very clever, as each of the elements contains the additional data members that are used for the stack management.

Secondly, your code is not formatted well and the redundant use of this-> makes it hard to read.

Then the code

c* evictedN = new c();
    evictedN->ptr = this->top;
top = top->prev;
top->next = NULL;

包含内存泄漏;为什么要创建一个新的c对象，而不是只返回顶部元素？



其余的：只需在调试器中运行程序，你会看到它是否做了它应该做的事情。

contains a memory leak; why do you create a new c object, instead of just returning the top element?

For the rest: Just run your program in a debugger and you will see whether it does what its supposed to do.

正如nv3在解决方案1中指出的那样，对堆栈使用相同的类以及你管理的项目会导致混乱。

如果你的目标是只是来实现一个堆栈（LIFO队列），那么一个双向链表比你想要的更复杂。

可以使用单链表实现堆栈。



调试算法（不是代码，算法;如果这不正确，代码将永远不会正确）我会拿一支铅笔和纸，然后完成将3个项目推入堆栈的步骤：绘制框到表示堆栈节点和箭头来表示指针。在指针改变时擦除并重绘指针。堆栈状态是否正确？如果是这样，现在弹出所有3个项目，一次一个，然后再移动箭头（指针）并验证一切正常，特别是在弹出最后一个项目的情况下（因为那是你目前所在的位置）麻烦）。



如果一切正常，那就处理代码。

我建议堆栈的不同类，节点引用/保存数据和数据（项目）本身。

单链接堆栈的伪代码：

As nv3 pointed out in Solution 1, using the same class for the stack and for the items you are managing is leading to confusion.
If your objective is just to implement a stack (LIFO queue), then a doubly-linked list is more complexity than you want.
A stack can be implemented with a singly linked list.

To debug your algorithm (not the code, the algorithm; if this isn't correct, the code will never be correct) I'd take a pencil and paper and walk through the steps of pushing 3 items onto the stack: draw boxes to represent the stack nodes and arrows to represent the pointers. Erase and redraw the pointers as they change. Is the stack state correct? If so, now pop off all of the 3 items, one at a time, and again move the arrows (pointers) and verify that everything behaves correctly, especially in the case of popping off the last item (because that's where you currently are having trouble).

If that all works, then work on the code.
I'd suggest different classes for the stack, the nodes referencing/holding the data and the data (items) themselves.
Pseudo-code for singly-linked stack:

node has {item* head; node* tail;}  // both initialize to null (for historical relevance these would have been named car and cdr!)
stack has {node* top}
stack theStack;  // empty stack
void stack::push (item*):
  node* cons = new node()    // name chosen for historical relevance
  cons->head = item
  cons->tail = this.top
  this.top = cons

item* stack::pop()
  if this.top == null then report pop from empty stack and return null
  node* tos = this.top
  item* result = tos->head
  this.top = tos->tail
  delete tos
  return result

这篇关于使用C ++的双向链表的LIFO堆栈的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！