A LIFO stack using doubly linked list by C++

Question

2.00/5 (1 vote)

See more:

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...

C++

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();

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 ..."

Posted 21-Oct-13 8:14am

3bood.ghzawi

Updated 21-Oct-13 10:01am

v2

Add a Solution

Comments

Sergey Alexandrovich Kryukov 21-Oct-13 14:27pm

"LIFO" is redundant. Stack is LIFO by definition...
—SA

Captain Price 21-Oct-13 14:36pm

You have a declaration of a class named c, and a definition named state. A mistake ?

3bood.ghzawi 21-Oct-13 15:49pm

where is the mistake in my code here? and how to correct it?

Captain Price 21-Oct-13 15:54pm

class c
{
bool isQueueEmpty();
};

And then you've written:-
bool state::isQueueEmpty()
What is class c and what is class state ?

3bood.ghzawi 21-Oct-13 16:03pm

dear Pravinda Ama. i have a mistake in copying my code and i have edit it.
please, i think you don't mind to help me.

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

nv3 · Answer 1 · 2013-10-21T11:15:00

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++

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

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.

Matt T Heffron · Answer 2 · 2013-10-21T12:14:00

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

A LIFO stack using doubly linked list by C++

2 solutions

Solution 1

Solution 2

Add your solution here

Preview 0

Existing Members

...or Join us