Bus Error(core dumped)

[randysimes]

I am writing a Stack template. The stack is declared as an array.
[
template <typename T, size_t N>; // N is 100
class TStack
{
...
private:
T data_[N];
...
}

I have several functions in this class template, Pop() //removes last item of stack, Push() //pushes an item to the stack, Size() //returns the size of the stack, Capacity()// returns N

I have a cpp program that tests the functionality of my template using a menu interface. When I choose Pop() without pushing anything to the stack, I get a Bus Error(core dumped).

[
template <typename T, size_t N>
... ::Pop()
{
if (size_ == 0) {std::cerr << "Stack is empty'\n'";}
else {return data_[size_-1];} //size_ is initialized to 0 and incremented when item are pushed to the stack and decremented when they are popped
}
]

When I Push() an item to the stack and then choose Pop(), it does what is expected.

What should I do to data_ to ensure that this does not happen. I understand that the Bus Error is a segmentation fault and it happens because I am trying to acces a value that is not allocated memory, but am not sure how to fix it in this situation. In the guidelines I am not allowed to use operator new or delete to insure allocation.

Thanks in advance.

[weaknessforcats]

What's wrong woith the stack<> template in the C++ Standard Template Library?

Is this some sort of school assignment?

[randysimes]

weaknessforcats , yes it is.

[weaknessforcats]

You are using a fixed array for your stack. Not good. You should be using a linked list so you add/remove nodes as items are added or removed from the list.

In this case data_ is a T*.

When data_ is 0, the stack is empty.

A linked list will avoid the seg fault since you won't need all sorts of array management code in the class.

All you need is a linked list where you add to or remove from the end of the list.

The add is your Push(), the Remove()is your Pop().

There should be a Top() to view the top of the stack (last element in the linked list) without removing it.

[randysimes]

I do have a Top() function. The requirements state that I have to use an array that holds 100 elements. T data_[N] // N is passed in as 100. I just don't know why I get the seg fault because I have an if(size_ == 0) throw an error, but it seems like it throws the error AND tries to return the value when I only want it to throw the error OR return the value.

[sridhard2406]

Hi,
Make one member variable for counts of push and pop operation, whenever pop calls, check that count variable, if that variable is 0 or -1, just return the pop funtion with error messsage.
When you declared that variable make it as a private.
When you decalred initially assign -1 for that member veriable.

[randysimes]

That's what the variable size_ takes care of, the counts of the Push() ++size_, and Pop() --size_ The only thing different would be to check for -1 also, I only check for 0. Maybe redo the if and make it:
if(size_ != 0) {return data_[size_ - 1]}
error if else

[sridhard2406]

And also, when you create the size member variable, initalize the value as 0 or -1. You can achive this using constructor .

[randysimes]

I initialize size_ to zero with the class constructor. I am using prefix incrementation, would this make a difference?

[sridhard2406]

I think, it will not, make any difference, better put the logs and check it.

[weaknessforcats]

You haven't got an off-by-one error do you?

Your N is the number of array elements. Like 100. The array elements vary from 0 to 99.

If you use 0 to indicate the stack is empty, then when you have 1 you need to use data_[0] and not data_[1].

data_[100] is outside your array and causes a dump.

[randysimes]

weaknessforcats , I am now working on part 2 of my assignment. In this part, I construct a Queue. I have to use linked lists for this part. Linked lists are new to me.
template <typename T>
class TQueue
{
public:
TQueue();
//~TQueue();
void Push (const T& t); //push t onto queue
T Pop (); //pop queue and return removed element; error if empty
T& Front (); //return front element of stack; error if empty
const T& Front () const; //const version
size_t Size () const; //return number of elements in queue
int Empty () const; //return 1 if queue is empty, 0 if not empty
void Clear (); //make the queue empty
void Display (std::ostream& os, char ofc) const; //outputs contents through os
private:
class Link
{
Link (const T& t) : element_(t), nextLink_(0) {}
T element_;
Link * nextLink_;
friend class TQueue<T>;
};
Link * firstLink_;
Link * lastLink_;
};

How do I access element_ and nextLink_ in my Push function?

When I Push(t), it goes to element_, then I'm not to sure on the rest.

??
firstLink_ = element_;
lastLink_ = nextLink_;
nextLink_ = '\0';
??

[weaknessforcats]

I would use two structs (classes):

1) LinkedList.
This is the linked list. Here is the address of the first element (node) and last element (Node) plus the address of the current position (used in traverses of the list:

struct LinkedList
{
     Node* first;
     Node* last;
     Node* current:
};

2) Node

This is an element in the list. Here is the data, and a pointer to the Node before and after this Node:

struct Node
{
    T Data;
    Node* prev;
    Node* next;
};

You should be able to write a series of functions:
1) Insert the second Node* argument after the first Node* argument.
This function wouldn't even know there is a list. All it does is work with the next/prev pointers to do the insert. It will be called as need by other funcitons.
2) Delete the Node that is the Node* argument.
3) Create a Node and populate with the T data argument

Then these functions that call the Node functions:

1) Append the T data to the end of the list
a) call the create node using the data
b) if the list is empty make the created node both the first and lkiat of the list
otherwise, call the insert node function using the last node as the first argunent and the new node the first argument.


The append function is called by your Queue Push().

etc...

There's a lot of info on linked list available by doing a Google.

[randysimes]

Unfortunately, I am unable to use anything other than what was given in the tqueue.h file provided above.

[APmore]

.. ::Pop()
{
if (size_ == 0) {std::cerr << "Stack is empty'\n'";}
else {return data_[size_-1];} //size_ is initialized to 0 and incremented when item are pushed to the stack and decremented when they are popped
}

so when stack is empty, and you are calling pop..you are returning data[-1].{crossed array bounds} .Hence you are getting seg fault because of invalid memory access.

~kishore