Question

For my assignment, I'm not sure how to start making a stack implemented via linked list of arrays. I'm stuck on how to approach the very first steps (Stack class members and constructor.) I'm familiar with allocating memory, arrays, and linked lists, but putting them together has me lost. How should I create a Stack with a dynamic linked list of arrays?

Stack name (number of elements); Creates a stack of strings with name “name.” Internally, each unit of memory allocation is “number of elements” elements. Users should be smart enough to choose a number of elements that matches their expected usage patterns.

void push(string) Adds an element containing string to the top of the stack.

bool top(string &)   Retrieves the string in the top element. If the stack it empty, returns false.

bool pop(string &) Retrieves and removes the top element. If the stack is empty, returns false.

destroy() Releases any memory used by the stack.

Implementation details:

Stack class members :

- int array size (specified by user when instantiating)

-linked list definition // ex.( list < string* > something; )

- int topElement (element number of the current top element of the stack)

The element number is logically a “pointer” to the top element. It always points to the place in the current array where the next element would go. Again, assume that the array size is 10. If the element number is 5, then a new element goes into array [5]. When the list is empty, the element number is zero. When the element number is 10, the array is full.

constructor:

allocate an array of the specified size

create a linked list entry containing a pointer to the array

  set topElement to 0, indicating that the top of the stack is element 0 of the current array

push:

if the current array is full (topElement = array size)

{

  create a new array

  add a pointer node for this array to the linked list

  move the data to element 0 of the new array

  set topElement to 1

}

else

{

  add data to the array at position {topElement]

  topElement ++

}

pop:

if the current array is empty (topElement = 0)

{

  if there is only one array allocated

{

  return false

}

else

{

delete current array

remove linked list entry for array

set topElement = array size - 1

  retrieve data from current array [topElement]

return true

}

}

else

{

  topElement - -

  retrieve data from current array [topElement]

return true

}

destroy:

delete array

remove linked list node for array

set topElement = array size

Use a header file for your Stack class, a .cpp for its member functions, and a second .cpp for the main routine.

The main is included and KEEP MAIN AS IS

int main() {
   Stack s(5);
   string st;
   bool b;
   s.push("aaaaa");
   s.push("bbbbb");
   s.push("ccccc");
   s.push("ddddd");
   s.push("eeeee");

   cout << "main: start of part 1" << endl;
   b = s.top(st);
   cout << "main: top of stack " << st << endl;
   b = s.pop(st);
   cout << "main: just popped this ->" << st << endl;
   b = s.top(st);
   cout << "main: new top of stack after pop " << st << endl;
   b = s.pop(st);
   cout << "main: just popped this ->" << st << endl;
   b = s.pop(st);
   cout << "main: just popped this ->" << st << endl;
   b = s.pop(st);
   cout << "main: just popped this ->" << st << endl;
   b = s.pop(st);
   cout << "main: just popped this ->" << st << " stack should now be empty" << endl;
   b = s.top(st);
   if (b)
   {
       cout << "main: stack non-empty when it should be empty" << endl;
       return 4;
   }
   else
   {
       cout << "main: stack empty when it's empty" << endl;
   }

   cout << endl << "main: start of part 2" << endl;
   s.push("aaaaa");   // 1st element 1st array
   s.push("bbbbb");
   s.push("ccccc");
   s.push("ddddd");
   s.push("eeeee");
   s.push("fffff");   // 1st element 2nd array
   s.push("ggggg");
   s.push("hhhhh");
   s.push("iiiii");
   s.push("jjjjj");
   s.push("kkkkk");   // 1st element 3rd array

   b = s.top(st);
   cout << "main: top of stack " << st << endl;
   cout << "main: before while loop " << st << endl;
   b = s.pop(st);
   while (b)
   {
       cout << "main: element of stack " << st << endl;
       b=s.pop(st);
   }

   cout <<"main: before destroy"<< endl;
   s.destroy();
   cout <<"main: after destroy"<< endl;
   s.push("zzzzz");
   b=s.top(st);
   cout << "main: new top of stack " << st << endl;
   s.destroy();

   return 0;
}

Answer 1

#include <iostream>

#include <iostream>

using namespace std;

// CLASS NODE INTERFACE

class node {

public:

friend class Stack; // allow methods of class stack to access private members

node(); // give initial values to data members

private:

string data; // data for this node

node * next; // pointer to the next node in the list

};

node::node(){

}

// CLASS NODE IMPLEMENTATION (write the constructor here)

// CLASS STACK INTERFACE

class Stack {

public:

Stack(); // init stack to empty stack

void push(string x); // allocate a new node, copy x into it, put it on the top of the stack

bool pop(string &); // deallocate the top node and return the data that was in it.

// print "Stack empty" and return 0 when the stack is empty.

void print(); // print the data of all nodes, left to right, starting with the top.

Stack(int n);

bool top(string &);

void destroy();

private:

node * ptr; // pointer to top node of the stack, or NULL when stack is empty

};

// CLASS STACK IMPLEMENTATION (write methods here)

bool Stack::pop(string &s){

if (ptr == NULL)

return false;

else {

s = ptr->data;

ptr = ptr->next;

}

return true;

}

bool Stack::top(string &s){

if (ptr == NULL)

return false;

else {

s = ptr->data;

}

return true;

}

Stack::Stack(){

ptr = NULL;

}

Stack::Stack(int n){

ptr = NULL;

}

void Stack::destroy(){

ptr = NULL;

}

void Stack::push(string x){

node* temp = new node();

temp->data = x;

temp->next = ptr;

ptr = temp;

}

void Stack::print(){

node *temp;

temp = ptr;

while(temp!=NULL)

{

cout<<temp->data<<",";

temp=temp->next;

}

cout<<endl;

}

int main() {

Stack s(5);

string st;

bool b;

s.push("aaaaa");

s.push("bbbbb");

s.push("ccccc");

s.push("ddddd");

s.push("eeeee");

cout << "main: start of part 1" << endl;

b = s.top(st);

cout << "main: top of stack " << st << endl;

b = s.pop(st);

cout << "main: just popped this ->" << st << endl;

b = s.top(st);

cout << "main: new top of stack after pop " << st << endl;

b = s.pop(st);

cout << "main: just popped this ->" << st << endl;

b = s.pop(st);

cout << "main: just popped this ->" << st << endl;

b = s.pop(st);

cout << "main: just popped this ->" << st << endl;

b = s.pop(st);

cout << "main: just popped this ->" << st << " stack should now be empty" << endl;

b = s.top(st);

if (b)

{

cout << "main: stack non-empty when it should be empty" << endl;

return 4;

}

else

{

cout << "main: stack empty when it's empty" << endl;

}

cout << endl << "main: start of part 2" << endl;

s.push("aaaaa"); // 1st element 1st array

s.push("bbbbb");

s.push("ccccc");

s.push("ddddd");

s.push("eeeee");

s.push("fffff"); // 1st element 2nd array

s.push("ggggg");

s.push("hhhhh");

s.push("iiiii");

s.push("jjjjj");

s.push("kkkkk"); // 1st element 3rd array

b = s.top(st);

cout << "main: top of stack " << st << endl;

cout << "main: before while loop " << st << endl;

b = s.pop(st);

while (b)

{

cout << "main: element of stack " << st << endl;

b=s.pop(st);

}

cout <<"main: before destroy"<< endl;

s.destroy();

cout <<"main: after destroy"<< endl;

s.push("zzzzz");

b=s.top(st);

cout << "main: new top of stack " << st << endl;

s.destroy();

return 0;

}

===================================================================

SEE OUTPUT

Thanks, PLEASE COMMENT if there is any concern. PLEASE UPVOTE