CODEWITHSUNDEEP
c++pointersqueueoutput
Kevin Groen
Kevin Groen

Reputation: 918

C++: First character in queue is wrong

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!

Upvotes: 0

Views: 285

Answers (4)

egur
egur

Reputation: 7960

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;
}

Upvotes: 0

andre
andre

Reputation: 7249

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";
}

Upvotes: 0

timrau
timrau

Reputation: 23058

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_++); }

Upvotes: 1

stellarossa
stellarossa

Reputation: 1800

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

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

Upvotes: 0

Related Questions