C++

Forum

 
Stack vs. Queue Linked Lists

jokerren (15)
Hello,
I'm curious as to whether or not I'm implementing queue structure correctly or not. The commented out block was my stack structure code before I changed it. So my question is, did I actually change anything? My guess is that I'm not going to see a difference unless I also add a pop/remove function. Thanks!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
#include<iostream>
using std::cout;
using std::endl;
using std::string;
using std::cin;
using std::ios;
#include<iomanip>
using std::setw;
#include<cstdlib>
using std::atoi;

struct course{
  string courseName;//e.g. COMSC-165
  string term;//FA2016
  int units;
  char grade;
  course *next;//tail
};

void printList(course*);

int main()
{
course *start=NULL;
course *end=NULL;
course *p=NULL;

printList(start);
char addNewCourse; //for loop control
string buf; //for user input

  do{
    p=new course;//start new node
    cout << "\n\nEnter a course code: (e.g. COMSC-101)" << endl;
    cin >> p->courseName;//get name of course
    cout << "Enter a term: (e.g. FA2015)" << endl;
    cin >> p->term;//get term
    cout << "Enter the amount of units: (e.g. 4)" << endl;
    cin >> buf; p->units=atoi(buf.c_str());//get unit number, 0 if non numeric input
    cout << "Enter the grade you received: ('X' if the course is in progress)" << endl;
    cin >> p->grade;//get grade

    /*queue structure? (FIFO)*/
    end=p;
    p->next=start;
    if (p==NULL)
      p=p->next;
    else
      start=p;

    /*stack structure (LIFO)*/
    //p->next = start;
    //start = p;

    printList(start);//print list

    cout << "\nWould you like to add another course? (Y/N)" << endl;
    cin >> addNewCourse;//Get user response

  }while(toupper(addNewCourse)=='Y');//loop control
  printList(start);
  delete start;//deallocate list memory
  delete end;
}

void printList(course *p){
  cout.setf(ios::left, ios::adjustfield);
  cout << setw(11) << "COURSE" << setw(8) << "TERM" << setw(8) << "UNITS" << setw(8) << "GRADE" << endl;//table header
  cout << setw(11) << "______" << setw(8) << "____" << setw(8) << "_____" << setw(8) << "_____" << endl;//table header

  for (course *temp=p; temp!=NULL; temp=temp->next){//outputs table data
    cout << setw(11) << temp->courseName << setw(8) << temp->term << setw(8) << temp->units << setw(8) << temp->grade << endl;
  }
}
gunnerfunner (2127)
OP: some comments first and then implementation of both queue and stack:
1. there is no reason with mingle the course with the nodes, I'd keep them separate in a struct and pass course objects to the nodes that make up the list, either queue or stack
2. use the course ctor instead of creating course objects 'by hand' so to say within main()
3. use smart pointer instead of raw C-style pointers, in my program I mention why only std::shared_ptr is feasible in this case
4. your printList doesn't actually print the entire list, you need such a method and that should be const qualified
5. can't see what purpose #include <cstdlib> serves and you're using sufficient std members for a using std directive instead of several declarations
6. use string throughout instead of char and get rid of stoi
7. I haven't done any input validation to focus on the list but you should. See here for a recent discussion here about cin integers:

http://www.cplusplus.com/forum/general/204310/

Stack Implementation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
#include <iostream>
#include <iomanip>
#include <string>
#include <memory>

using namespace std;

struct Course{
    string m_courseName;//e.g. COMSC-165
    string m_term;//FA2016
    int m_units;
    string m_grade;

    Course(string courseName, string term, int units, string grade)
    : m_courseName (courseName), m_term (term), m_units (units), m_grade (grade) {}

};
ostream& operator << (ostream& os, const Course& c)
{
    os << setw(11) << c.m_courseName << setw(8) << c.m_term << setw(8) << c.m_units << setw(8) << c.m_grade << '\n';
    return os;
}
struct stack_Node
{
    Course m_itsCourse;
    shared_ptr<stack_Node> m_itsNext;//not unique_ptr because operator = deleted, used below;

    stack_Node (Course itsCourse) : m_itsCourse (itsCourse) {}
};

struct stack_list
{
    shared_ptr<stack_Node> top;
    int m_num_nodes = 0;

    stack_list() : top(nullptr) {} //this precludes weak_ptr as well;
    void stack_push();
    void stack_pop();
    void stack_display ()const;
};

int main()
{
    stack_list s;
    bool fQuit = false;

    while(!fQuit)
    {
        cout<<"\nEnter your choice:";
        cout<<"\n1. PUSH\t2. POP\t3. DISPLAY\t4. EXIT\n";
        int choice;
        cin>>choice;
        switch(choice)
        {
            case 1:
                s.stack_push();
                break;
            case 2:
                s.stack_pop();
                break;
            case 3:
                s.stack_display();
                break;
            case 4:
                cout << "Goodbye \n";
                fQuit = true;
                break;
            default:
                cout<<"Invalid Choice";
                break;
        }
    }
}
void stack_list::stack_push()
{
    cout << "Enter course name: \n";
    string courseName;
    cin >> courseName;
    cout << "Enter a term: \n";
    string term;
    cin >> term;
    cout << "Enter number of units: \n";
    int units;
    cin >> units;
    cout << "Enter the grade you received: ('X' if the course is in progress) \n";
    string grade;
    cin >> grade;
    Course c(courseName, term, units, grade);

    shared_ptr<stack_Node> p (new stack_Node(c));
    p -> m_itsNext = nullptr;
    if(top != nullptr)
    {
        p -> m_itsNext = top;
    }
    top = p;
    m_num_nodes++;
    cout << "New Course inserted \n";
}
void stack_list::stack_pop()
{
    shared_ptr <stack_Node>  temp;
    if (top == nullptr)
    {
        cout << "Empty stack_list \n";
    }
    else
    {
        temp = top;
        top = top -> m_itsNext;
        cout << "Course popped is: " << temp ->m_itsCourse.m_courseName << '\n';
//        delete temp;
    }
    m_num_nodes --;
}
void stack_list::stack_display()const
{
    if(top == nullptr)
    {
        cout << "Empty stack_list \n";
    }
    else
    {
        cout << "Number of stack items: " << m_num_nodes << '\n';
        cout.setf(ios::left, ios::adjustfield);
        cout << setw(11) << "COURSE" << setw(8) << "TERM" << setw(8) << "UNITS" << setw(8) << "GRADE" << '\n';//table header
        cout << setw(11) << "______" << setw(8) << "____" << setw(8) << "_____" << setw(8) << "_____" << '\n';//table header
        shared_ptr <stack_Node>  p = top;
        while (p != nullptr)
        {
            cout << p -> m_itsCourse;
            p = p -> m_itsNext;
        }
    }
}

Queue Implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
#include <iostream>
#include <iomanip>
#include <string>
#include <memory>

using namespace std;

struct Course{
    string m_courseName;//e.g. COMSC-165
    string m_term;//FA2016
    int m_units;
    string m_grade;

    Course(string courseName, string term, int units, string grade)
    : m_courseName (courseName), m_term (term), m_units (units), m_grade (grade) {}

};
ostream& operator << (ostream& os, const Course& c)
{
    os << setw(11) << c.m_courseName << setw(8) << c.m_term << setw(8) << c.m_units << setw(8) << c.m_grade << '\n';
    return os;
}
struct queue_Node
{
    Course m_itsCourse;
    shared_ptr<queue_Node> m_itsNext;//not unique_ptr because operator = deleted, used below;

    queue_Node (Course itsCourse) : m_itsCourse (itsCourse) {}
};

struct queue_list
{
    shared_ptr<queue_Node> rear;
    shared_ptr<queue_Node> front;

    int m_num_nodes = 0;

    queue_list() : rear (nullptr), front (nullptr) {} //this precludes weak_ptr as well;
    void queue_enqueue();
    void queue_dequeue();
    void queue_display ()const;
};

int main()
{
    queue_list q;
    bool fQuit = false;

    while(!fQuit)
    {
        cout<<"\nEnter your choice:";
        cout<<"\n1. ENQUEUE\t2. DEQUEUE\t3. DISPLAY\t4. EXIT\n";
        int choice;
        cin>>choice;
        switch(choice)
        {
            case 1:
                q.queue_enqueue();
                break;
            case 2:
                q.queue_dequeue();
                break;
            case 3:
                q.queue_display();
                break;
            case 4:
                cout << "Goodbye \n";
                fQuit = true;
                break;
            default:
                cout<<"Invalid Choice";
                break;
        }
    }
}
void queue_list::queue_enqueue()
{
    cout << "Enter course name: \n";
    string courseName;
    cin >> courseName;
    cout << "Enter a term: \n";
    string term;
    cin >> term;
    cout << "Enter number of units: \n";
    int units;
    cin >> units;
    cout << "Enter the grade you received: ('X' if the course is in progress) \n";
    string grade;
    cin >> grade;
    Course c(courseName, term, units, grade);

    shared_ptr<queue_Node> p (new queue_Node(c));
    p -> m_itsNext = nullptr;
    if(front == nullptr)
    {
        front = p;
    }
    else
    {
        rear -> m_itsNext = p;
    }
    rear = p;
    m_num_nodes++;
    cout << "New Course inserted \n";
}
void queue_list::queue_dequeue()
{

    if (front == nullptr)
    {
        cout << "Empty queue_list \n";
    }
    else
    {
        shared_ptr <queue_Node>  temp;
        temp = front;
        front = front -> m_itsNext;
        cout << "Course dequed is: " << temp ->m_itsCourse.m_courseName << '\n';
    }
    m_num_nodes --;
}
void queue_list::queue_display() const
{
    if(front == nullptr)
    {
        cout << "Empty queue_list \n";
    }
    else
    {
        cout << "Number of queue items: " << m_num_nodes << '\n';
        cout.setf(ios::left, ios::adjustfield);
        cout << setw(11) << "COURSE" << setw(8) << "TERM" << setw(8) << "UNITS" << setw(8) << "GRADE" << '\n';//table header
        cout << setw(11) << "______" << setw(8) << "____" << setw(8) << "_____" << setw(8) << "_____" << '\n';//table header
        shared_ptr <queue_Node>  p = front;
        while (p != nullptr)
        {
            cout << p -> m_itsCourse;
            p = p -> m_itsNext;
        }
    }
}



jokerren (15)
Thank you very much! I should have specified that a lot of the things you mentioned are things my professor has required like creating the course objects manually and the course structure are what I have to build off of.
Also, I'm not sure what you mean in your 4th statement. Are you saying that the function needs the argument to be a const variable? If so, doesn't that prevent 'p' from traversing the list?
gunnerfunner (2127)
such a method and that should be const qualified

The operative word being 'such'. I'm referring to any method that actually prints the entire list - while the list printing operation is in progress the list is a const object of the corresponding class (either stack or queue) and so there is no restriction on having this method const qualified.
Indeed you should have it const qualified so that the method cannot make any changes to the list while it is printing the list and print out something erroneous. If you notice both stack_display() and queue_display() in my programs are const qualified
Topic archived. No new replies allowed.