Stacks using doubly linked lists

[comwizz]

hi ,
I just was trying to implement a stack using doubly linked list . Well , i cannot exactly find out the error. Any hint would be of great help.
Heres the code

#include<iostream.h>
#include<conio.h>
class abc
{
 public:
 int num;
 abc* next;
 abc* previous;
 friend void push(abc*,int);
 void pop(abc*);
 friend void display();
};
abc* head;
void display()
{
 while(1)
 {
  cout<<head->num;
  if(head->next==NULL)
  break;
  head=head->next;
 }
}

void push(abc* top,int no)
{
 static int ctr=0;
 if(ctr==0)
 {
  top=new abc;
  if(top==NULL)
  {
   cout<<"Overflow"<<endl;return;
  }
  head=top;
  top->num=no;
  top->next=NULL;
  top->previous=top;
  ctr++;
 }
 else
 {
  top->next=new abc;
  if(top->next==NULL)
  {
   cout<<"Overflow"<<endl;return;
  }
  top->previous=top;
  top=top->next;
  top->num=no;
  top->next=NULL;
 }
}

int main()
{
 abc* top=NULL;
 int n;
 do
 {
  cout<<"Enter 1 for push , 2 for peep , 3 for pop , 4 for change and -1 to exit "<<endl;
  cin>>n;
  int x;
   switch(n)
   {
    case 1:
	 cout<<"Enter number you want to push"<<endl;
	 cin>>x;
	 push(top,x);
	 display();
	 break;
   }
  }while(n!=-1);
}

[azimuth0]

I notice a few things...

There's no need to declare push() and display() as being friends of abc , since abc has no protected members.

The designation of head and top is kind of confusing. Why not head and tail , or top and bottom ?

The top variable isn't being updated, in any case. It looks as if you think that push() is updating the top pointer declared in main() , but it's really updating its own copy of the pointer.

The head variable should be initialized to NULL.

The static ctr variable has no use at all. You are only using it to check to see if the stack is empty, but you can just as easily do that by checking head (which should be NULL).

Hope this helps.

[Lerner]

Your stack is a doubly linked list with restricted access to the links in the list. The links themselves need to do nothing (they could display their value if you want but other than display themselves they do nothing) so remove everything from abc but the member variables (and write a display method if you wish). The stack in this program is really called head, and head is really a pointer to the first link in the list, just like you have declared it. To use the list you have to have knowledge of at least one node in the list. Usually you would keep track of the first link in the list, but you could keep track of something else if you want.

When you display the list you don't want to change anything in the list, you just want to display the values stored in it. If you change the value of head as you display the list you will have to have some mechanism to remember what head really is pointing to before you do another function call. This adds another level of complexity to the program but would be doable if you insist. On the other hand, you wouldn't have to keep track of this new location if you have a policy saying head always points to the first link in the list so I will leave it alone when I display the list; instead I will use another abc pointer to run the list in the body of the function.

Stacks differ from doubly linked lists in that you are resticted by ensuring that the last link added is the first link removed. The easiest way to do this is to always add to the front of the list or to always add to the back of the list. If you always add/remove from the front of the list, then the address stored in head will have to change each time one of these operations is performed. If you always add/remove from the end of the list, then value in head may or may not change, depending on whether there is more than one link in the list or not. However, you will have to either keep track of the end of the list or run the list to find the end of the list every time you want to do one of these tasks. So pick your poison, state it clearly, and deal with it.

You also have some other decisions to make.

First you can use free standing functions to manipulate the stack as you do in the post, or you could create another class to encapsulate a stack. Each stack has variables, such as the first node in a linked list and the number of nodes in the list, and a number of methods that can manipulate the stack itself, such as add/remove a link, display link(s), etc. I think it makes sense to create a second class, but it's up to you.

Second, you can either declare your stack and the variables associated with your stack, like ctr, with global scope so it is accessable to all the functions that will use them---using global variables is frowned upon, OR you could declare them within main() and pass then back and forth among the various functions--which would be the prefered way. If you are passing them back and forth between freestanding functions, then you will want to pass the variables by reference to any function that could change the value of the variable, so any changes to the value in the variable is maintained after the function stops.

[Laiq Ahmed]

The stack is a lifo(last in first out) based sequential structure. I think you don't need a double link list to implment it, you can implement lifo based list directly.

struct Node {
  int m_iVal;
  Node* m_pNext;
  Node(int const& iVal,m_pNext=0)
}

if you've used the stack it provides three basic as well as standard functionality
push() to push the element on the top of stack
pop() to pop the element from the top
top() returns the top element;
there is no need for display function in the standard stack.
if you need that function
you should have written like that

void display() 
{
//it uses 
while(HEAD) 
{ 
   while(HEAD) 
    {
        cout<<HEAD->top()<<endl;
        HEAD->pop();
     }
}

Your push function takes the pointer as an argument there is no need for that, and remove the friend from there.......
push should be member function.~! i.e. void push(int value) remember this pointer is always passed quitely to member function so no need to pass explicity and declare it as a friend and you are violating the OOP concept encapsulation by doing this.why you've used static counter.............if you declare push as a member function there is no need for that. also why don't you utilize HEAD variable for this.
your push function should be like this.

void push(int value)
{
HEAD= new Node(value,HEAD);
//or its also fine
/* if(HEAD==0)
HEAD= new Node(value);
else {
Node* temp = new Node(value)
temp->m_pNext=HEAD;
HEAD=temp;
}*/
 
}

you didn't include the another important function of stack i.e. pop() it simply releases the top element. it doesn't return the data.

void pop() 
{
if(HEAD)
   {
      Node* temp = HEAD;
      HEAD=HEAD->m_pNext;
      delete HEAD;
    }
}

the last is top()

void top() const {
return HEAD->m_iVal;
}

Now i m giving you the sample code not complete for Stack using Doubly Link list, implement it completely........ Hope you got the idea.........

#include "stdafx.h"
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
struct Node{
  int m_iVal;
  Node* m_pNext;
  Node* m_pPrev;
   Node(int const& val,Node* pNext=0,Node* pPrev=0):m_iVal(val),m_pNext  (pNext),m_pPrevpPrev){}
};
class DList {
public:
  DList():m_HEAD(0),m_TAIL(0){}
  virtual ~DList()
 {
  while(m_HEAD)
    pop_back();
 
//don't forget to add 
//while(m_TAIL)
//pop_front()
  } 
 
//interface provided by double link List;
void push_back(int const& value);
void pop_back();
int back()const 
{
  return m_HEAD->m_iVal;
} 
//implement yourself 
void push_front(int const& value);
void pop_front();
int front();
 
private:
Node* m_HEAD; 
Node* m_TAIL; 
};
void DList::push_back(intconst& value)
{
   if(!m_HEAD) {
      m_TAIL = m_HEAD = new Node(value);
   }
   else {
           Node* temp=new Node(value);
           temp->m_pPrev=m_HEAD;
           m_HEAD->m_pNext=temp;
           m_HEAD=temp;
   }
}
void DList::pop_back()
{
      if(m_HEAD){
      Node* temp= m_HEAD;
      m_HEAD = m_HEAD->m_pPrev;
      delete temp;
}
else {
       cout<<"Nothing to Delete"<<endl;
}
}
class MyStack: public DList {
     //implement stack using the DList; just change the names of interfaces and call base class version :)
};
int main(int argc, char* argv[])
{
DList* dlist = new DList();
dlist->push_back(4);
dlist->push_back(2);
cout<<dlist->back()<<endl;
dlist->pop_back();
cout<<dlist->back()<<endl;
dlist->pop_back();
delete dlist;
return 0;
}

Wish you good luck (y)

[comwizz]

Thanks Lerner , Azimuth0 and Laiq Ahmed for your help. I will be updating my program according to your inputs and would post if I have a problem .
Thanks

[comwizz]

hi,
i tried implementing the stack with pop front , pop back ,push front and push back functions . well , i tried them separately and they worked , but i want a single stack performing all the functions , and here tow separate stacks are being created . so , i cant figure out how to make them into a single one by giving a link to the last element of stack using head and first element of stack using end.
Any suggestion or hint would be of great help. Also , any suggestion to optimize the code would be great.
heres the code

#include<iostream.h>
#include<conio.h>
class node
{
 public:
 int val;
 node* next;
 node* previous;
 node(int a):val(a)
 {
  next=NULL;
  previous=NULL;
 }
};
class list
{
 public:
 list():end(NULL),head(NULL){}
 void push_back(int val);
 void push_front(int);
 int pop_back();
 int pop_front();
 void display();
 int peep(int);
 void change(int,int);
 private:
 node* end;
 node* head;
};
int list:: pop_back()
{
 int p=end->val;
 node* temp=end;
 if(end->previous==NULL)
 {
  cout<<"Stack underflow"<<endl;
  return 0;
 }
 end=end->previous;
 end->next=NULL;
 delete temp;
 return p;
}
void list::push_back(int val)
{
 node* temp=new node(val);
 if(end!=NULL)
 {
  temp->previous=end;
  end->next=temp;
  end=temp;
  end->next=NULL;
 }
 else
 {
  temp->previous=NULL;
  end=temp;
  end->next=NULL;
 }
 delete temp;
}
void list::push_front(int x)
{
 if(head==NULL)
 {
  node* temp=new node(x);
  head=temp;
  head->previous=NULL;
  head->next=NULL;
 }
 else
 {
  node* temp=new node(x);
  temp->next=head;
  head->previous=temp;
  head=temp;
  head->previous=NULL;
 }
}
int list::pop_front()
{
 if(head==NULL)
 {
  cout<<"Stack underflow"<<endl;
  return 0;
 }
 int p=head->val;
 node* temp=head;
 head=head->next;
 delete temp;
 return p;
}
int list::peep(int x)
{
 node* ctr=end;
 int i=0;
 while(i<x-1)
 {
   ctr=ctr->previous;
   i++;
 }
 return(ctr->val);
}
void list::change(int x,int new_no)
{
 int i=0;
 node* temp=end;
 while(i<x-1)
 {
   temp=temp->previous;
   i++;
 }
 temp->val=new_no;
}
void main()
{

  clrscr();
  int choice;

  list abc;
  int n;
  do
  {
   cout<<endl<<"Enter your choice";
   cin>>choice;
   int x;
   int ans;
   switch(choice)
   {
    case 1:cout<<"Enter the element you want to push"<<endl;
	   cin>>n;
	   cout<<"Enter 1 for back , 2 for front "<<endl;
	   cin>>ans;
	   if(ans==1)
	   abc.push_back(n);
	   else
	   abc.push_front(n);
	   abc.display();
	   break;
    case 2:cout<<"Do you want to push from the back or the front of the stack"<<endl;
	   cout<<"Enter 1 for back , 2 for front "<<endl;
	   cin>>ans;
	   cout<<"The popped element is"<<endl;
	   if(ans==1)
	   {
	    x=abc.pop_back();
	    if(x!=0)
	    cout<<x;
	   }
	   if(ans==2)
	   {
	    x=abc.pop_front();
	    if(x!=0)
	    cout<<x;
	   }
	   cout<<"The remaining contents are: "<<endl;
	   abc.display();
	   break;
    case 3:cout<<"Enter the number of the element which you want to peep from the top"<<endl;
	   cin>>n;
	   x=abc.peep(n);
	   cout<<"The peeped element is"<<endl;
	   cout<<x<<endl;
	   break;
    case 4:cout<<"Enter the value of the element which you want to change from the top " <<endl;
	   cin>>n;
	   cout<<"Enter the value of the element to be changed"<<endl;
	   cin>>x;
	   abc.change(n,x);
	   cout<<"The new list is:"<<endl;
	   abc.display();
	   break;
   }
  }while(choice!=-1);
}

Thanks,
comwizz

[Lerner]

Lists with push/pop restricted to head/end mimic functionality of double ended queues, aka dequeues (dequeues have some other properties too, but that's the guts of 'em). To me, head would indicate the first node in the list and end would indicate last node in list so there is just one list per "stack" or "dequeue" or whatever you are calling this container. When you pop/push to front it would change head (and end if less than two nodes in list) and when you pop/push to back it would change end (and head if less than two nodes in list). When popping first node onto list or removing second to last node from list, then head is same as end. If pop_back to a single node list, then end is hend->next (aka new node added) and if pop_front to single node list then end becomes head and head becomes head->previous (aka new node added), etc. If head != NULL then end != NULL either. If length == 1, then head == end. Following successful push/pop event head->previous will always be NULL and end->next will always be NULL.