C++: First character in queue is wrong

Question

I'm currently working on an assignment for school that says I should create a Queue. It seems to be working. The only problem is that there is an unexpected char at the beginning of my Queue. I use class CQueue to push and pop values from the queue. It is essential that I use this class instead of something like std::queue or deque.

class CQueue
{
private:
char *bottom_;
char *top_;
int size_;
public:
CQueue(int n = 20){
    bottom_ = new char[n];
    top_ = bottom_;
    size_ = n;
}

void push(char c){
    *top_ = c;
    top_++;
}

int num_items() {
    return (top_ - bottom_ );
}

char pop(){
    bottom_++;
    return *bottom_;
}

void print(){
    cout << "Queue currently holds " << num_items() << " items: " ;
    for (char *element=top_; element > bottom_; element--) {
        cout << " " << *element;
    }
    cout << "\n";
}

This is my main method:

int main(){


CQueue q(10);

q.push('s');q.push('t');q.push('a');q.push('c');q.push('k');
q.print();
cout << "Popped value is: " << q.pop() << "\n";
q.print();
q.push('!');
q.push('?');
cout << "Popped value is: " << q.pop() << "\n";
q.print();

while (!q.empty()) q.pop();
if (q.num_items() != 0) {
    cout << "Error: Stack is corrupt!\n";
}
q.print();
cout << "End of program reached\n"<< endl;
return 0;

When I run this code the queue gets filled but *bottom_ is replaced with a '=' symbol. This is my output:

Queue currently holds 5 items:  ═ k c a t
Popped value is: t
Queue currently holds 4 items:  ═ k c a
Popped value is: a
Queue currently holds 5 items:  ═ ? ! k c
Queue currently holds 0 items:
End of program reached

I've been banging my head over this one for a while now so I hope that maybe you can shed some light on this problem!

timrau · Accepted Answer · 2013-11-18 14:35:54Z

1

As your push() is defined, *top_ is NOT in queue. It is one element after the end of queue. Therefore, you should define your print() to iterate from top_ - 1.

Also as @stellarossa mentioned, you should return the character pointed by bottom_ before increment. That is,

char pop() { return *(bottom_++); }

answered Nov 18, 2013 at 14:35

timrau

23.1k4 gold badges55 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

stellarossa · Accepted Answer · 2013-11-18 14:35:48Z

0

char pop(){
    bottom_++;
    return *bottom_;
}

you're incrementing your pointer and then returning the value. it should be the other way around.

answered Nov 18, 2013 at 14:35

stellarossa

1,8101 gold badge19 silver badges30 bronze badges

Comments

andre · Accepted Answer · 2013-11-18 14:38:14Z

0

Are you using an array or linked list?

Keep it simple and use an array with a count variable.

#include <iostream>
using namespace std;
class CQueue
{
private:
char * q;
int size_;
int count;
public:
CQueue(int n = 20){
    q = new char[n];
    size_ = n;
    count = 0;
}

void push(char c){
    assert(count != size);
    q[count] = c;
    count++;
}

int num_items() {
    return count;
}

char pop() {
    assert(count != 0);
    char ret = q[count-1];
    count--;
    return ret; 
}

void print(){
    cout << "Queue currently holds " << num_items() << " items: " ;
    for (int i = 0; i < count; i++) {
        cout << " " << q[i];
    }
    cout << "\n";
}

answered Nov 18, 2013 at 14:38

andre

7,2856 gold badges50 silver badges80 bronze badges

Comments

egur · Accepted Answer · 2013-11-18 14:48:22Z

0

At least two bugs my friend.

1) The print() method starts printing *top which is 1 past the last member. Should be:

for (char *element=top_-1; element >= bottom_; element--) {
    cout << " " << *element;
}

2) The pop() method is wrong: should be:

char pop(){
    return (top_ > bottom_) ? *top_-- : 0;
}

answered Nov 18, 2013 at 14:48

egur

8,0102 gold badges30 silver badges47 bronze badges

1 Comment

Kevin Groen Over a year ago

You are absolutely right about the first one! Thank you so much. But i've decided to use @stellarossa's solution for the pop method.

Collectives™ on Stack Overflow

C++: First character in queue is wrong

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related