StackLinked List Using C

StackLinked List Using C++

Now that you have an understanding of components, you need to create a stack-linked list. In this section, we ll focus on assembling them into a working C++ application. Some programmers organize components of a stack-linked list into five files: LinkedList.h , LinkedList.cpp , StackLinkedList.h , StackLinkedList.cpp , and StackLinkedListDemo.cpp . All these files are joined together at compile time to create the executable.

The LinkedList.h file is the header file that contains the definition of the Node structure and the definition of the LinkedList class. The LinkedList.cpp is a source code file that contains the implementation of member functions of the LinkedList class, both of which you learned about in Chapter 6.

The StackLinkedList.h file is the header that contains the definition of the StackLinkedList class. The StackLinkedList.cpp is the source code file that contains the implementation of member functions of the StackLinkedList class.

The StackLinkedListDemo.cpp contains the application. It is here where an instance of the StackLinkedList class is declared and member functions are called.

LinkedList Header File and LinkedList Functions

The LinkedList.h file and the LinkedList.cpp file are shown in the following code. These should look familiar to you because they are the same files described in Chapter 6. However, there is one exception. The front and back attributes defined in the LinkedList class in the LinkedList.h file are defined within the protected access specifier section of the class definition. They appeared within the private access specifier in the sample file in Chapter 6. The StackLinkedList class needs access to these variables , so you protect them so they re visible to the subclass.

Refer to Chapter 6 for a complete explanation of these files and member functions.

 //LinkedList.h typedef struct Node {  struct Node(int data)  {  this->data = data;  previous = NULL;  next = NULL;  }  int data;  struct Node* previous;  struct Node* next; } NODE; class LinkedList {  protected:  NODE* front;  NODE* back;  public:  LinkedList();  ~LinkedList();  void appendNode(int);  void displayNodes();  void displayNodesReverse();  void destroyList(); }; //LinkedList.cpp #include "LinkedList.h" LinkedList::LinkedList() {  front = NULL;  back = NULL; } LinkedList::~LinkedList() {  destroyList(); } void LinkedList::appendNode(int data) { NODE* n = new NODE(data);  if(back == NULL)  {  back = n;  front = n;  }  else  {  back->next = n;  n->previous = back;  back = n;  } } void LinkedList::displayNodes() {  cout << "Nodes:";  NODE* temp = front;  while(temp != NULL)  {  cout << " " << temp->data;  temp = temp->next;  } } void LinkedList::displayNodesReverse() {  cout << "Nodes in reverse order:";  NODE* temp = back;  while(temp != NULL)  {  cout << " " << temp->data;  temp = temp->previous;  } } void LinkedList::destroyList() {  NODE* temp = back;  while(temp != NULL)  {  NODE* temp2 = temp;  temp = temp->previous;  delete temp2;  }  back = NULL;  front = NULL; } 

StackLinkedList Header File and StackLinkedList Source File

The StackLinkedList.h file contains the definition of the StackLinkedList class, as shown next. Below the StackLinkedList.h file is the StackLinkedList.cpp file that contains the definitions of member functions.

The class definition and each member function were explained in the The StackLinkedList Class section of this chapter.

 //StackLinkedList.h  class StackLinkedList : public LinkedList {  public:  StackLinkedList();  virtual ~StackLinkedList();  void push(int);  int pop();  bool isEmpty(); }; //StackLinkedList.cpp StackLinkedList.h StackLinkedList::StackLinkedList() { } StackLinkedList::~StackLinkedList() { } void StackLinkedList::push(int x) {  appendNode(x); } int StackLinkedList::pop() {  if(isEmpty())  {  return -1;  }  int retVal = back->data;  NODE* temp = back;  if(back->previous == NULL)  {   back = NULL;  front = NULL;  }  else  {  back = back->previous;  back->next = NULL;  }  delete temp;  return retVal; } bool StackLinkedList::isEmpty() {  if(front == NULL)  {  return true;  }  else  {  return false;  } } 

StackLinkedList Application

The StackLinkedListDemo.cpp file contains the actual stack application, as shown in the following code listing. The application begins by declaring an instance of the StackLinkedList class. Remember that this statement also indirectly calls the constructor of the LinkedList class, which is inherited by the StackLinkedList class.

The application then calls the push() member function to push the values 10, 20, and 30 onto the stack. The displayNodes() member function is then called to display the values on the stack. The displayNodes() member function is a member of the LinkedList class and is described in detailed in Chapter 6.

The pop() member function is then called to remove the last node on the stack, which is then displayed on the screen (see Figure 7-3). The program then calls the delete operator to remove the stack from memory.

Figure 7-3: Before the pop() member function is called, there are three nodes on the stack. Two nodes remain after pop() is called.

Here s the output of this program:

Nodes: 10 20 30 10

 //StackLinkedListDemo.cpp #include <iostream> using namespace std; void main(){  StackLinkedList* stack = new StackLinkedList();  stack->push(10);  stack->push(20);  stack->push(30);  stack->displayNodes();  cout << stack->pop() << endl;  delete stack; }