Here's my custom template stack class
#ifndef INC_20F_FLT_PLN_DSSTACK_H
#define INC_20F_FLT_PLN_DSSTACK_H
#include <iostream>
template <typename T>
class DSStack
{
T* data;
int top;
int capacity;
public:
DSStack()=default;
DSStack(int size);
DSStack(const DSStack<T>& copy);
DSStack& operator= (DSStack<T>);
void push(const T& data);
T pop();
T peek();
bool isempty();
bool isfull();
int getsize();
~DSStack(){while ( !isempty() ) {
pop();
}
isempty();};
};
template<typename T>
DSStack<T>::DSStack(int size) {
this->capacity=size;
this->data = new T[capacity];
top=-1;
}
template<typename T>
void DSStack<T>::push(const T& data) {
if(!isfull())
{
this->data[top+1]=data;
top++;
}
}
template<typename T>
T DSStack<T>::pop() {
if(!isempty())
{
top--;
return data[top+1];
}
}
template<typename T>
T DSStack<T>::peek() {
if(!isempty())
{
return data[top];
}
}
template<typename T>
int DSStack<T>::getsize() {
return top+1;
}
template<typename T>
bool DSStack<T>::isempty() {
if(top==-1)
{
return true;
}
else
return false;
}
template<typename T>
bool DSStack<T>::isfull() {
if(top==capacity-1)
{
return true;
}
else
return false;
}
template<typename T>
DSStack<T>::DSStack(const DSStack<T> ©) {
this->data = new T[copy.capacity];
this->capacity = copy.capacity;
for(int i =0;i<capacity;i++)
{
this->data[i]= copy[i];
this->top+=1;
}
}
template<typename T>
DSStack<T> &DSStack<T>::operator=(DSStack<T> copy) {
this->data = new T[copy.capacity];
this->capacity = copy.capacity;
for(int i =0;i<capacity;i++)
{
this->data[i]= copy[i];
this->top+=1;
}
return *this;
}
#endif //INC_20F_FLT_PLN_DSSTACK_H
And my template linked list class
#ifndef INC_20F_AUTO_IDX_DSLINKEDLIST_H
#define INC_20F_AUTO_IDX_DSLINKEDLIST_H
#include <cstddef>
#include <utility>
template <typename T>
class DSList
{
struct DSNode
{
T value;
DSNode* prev;
DSNode* next;
DSNode(T value, DSNode *prev = nullptr, DSNode *next = nullptr)
: value{std::move(value)}, prev{prev}, next{next}
{}
DSNode(const DSNode&) = delete;
void operator=(const DSNode&) = delete;
friend void swap(DSNode& a, DSNode& b) {
using std::swap;
swap(a.value, b.value);
swap(a.prev, b.prev);
swap(a.next, b.next);
}
};
public:
DSList() = default;
DSList(const DSList<T>&);
DSList& operator=(DSList<T>);
~DSList();
T const& get(std::size_t pos) const;
T& get(std::size_t pos);
void insert(T value, std::size_t pos);
int getsize();
template<typename U>
friend void swap(DSList<U>&, DSList<U>&);
private:
std::size_t n_elements = 0;
DSNode head = { T{}, nullptr, &tail };
DSNode tail = { T{}, &head, nullptr };
};
template<typename T>
DSList<T>::DSList(const DSList<T>& list)
{
for (auto i = list.n_elements; i > 0; --i) {
insert(list.get(i-1), 0);
}
}
template<typename T>
DSList<T>& DSList<T>::operator=(DSList<T> list)
{
swap(*this, list);
return *this;
}
template<typename T>
DSList<T>::~DSList()
{
for (auto p = head.next; p != &tail; ) {
auto next = p->next;
delete p;
p = next;
}
}
template<typename T>
void swap(DSList<T>& a, DSList<T>& b)
{
using std::swap;
swap(a.head, b.head);
swap(a.tail, b.tail);
swap(a.n_elements, b.n_elements);
}
template<typename T>
const T& DSList<T>::get(std::size_t pos) const
{
auto p = head.next;
while (pos--)
p = p->next;
return p->value;
}
template<typename T>
T& DSList<T>::get(std::size_t pos)
{
auto p = head.next;
while (pos--)
p = p->next;
return p->value;
}
template<typename T>
void DSList<T>::insert(T value, std::size_t pos)
{
auto p = &head;
while (pos--)
p = p->next;
auto next = p->next;
next->prev = p->next = new DSNode(std::move(value), p, next);
++n_elements;
}
template<typename T>
int DSList<T>::getsize() {
return n_elements;
}
#endif //INC_20F_FLT_PLN_DSLINKEDLIST.H
When I am trying to create a stack of type int:
DSStack<int>test (2);
, it will allow me to push, pop, peek with the data and it would return correct results.
But when I tried to create stack of type linked list:
DSStack<DSList<int>>test2(2);
, I would also create a linked list of integers, DSList<int>numList;
I can put some numbers in to the linked list and it would give no error. But when I try to push the linkedlist that I created into the stack, it would give error of: Process finished with exit code -1073740940 (0xC0000374). Running with a debegger gives me the error of cannot access memory at a random location. The line points to the destructor of the linked list class, but I believe that the destructor of the linked list class does function properly. I wonder if this has to do with how I set up my stack class. I would really like some help on how to fix this issue. Thank you!
Ok, you got a bunch of weirdness going on in your list impl. I was able to get the following singly-linked list working
#ifndef INC_20F_AUTO_IDX_DSLINKEDLIST_H
#define INC_20F_AUTO_IDX_DSLINKEDLIST_H
#include <cstddef>
#include <utility>
template <typename T>
class DSList
{
struct DSNode
{
T value;
DSNode* next;
DSNode(T value, DSNode *next = nullptr)
: value{std::move(value)}, next{next}
{}
DSNode(const DSNode&) = delete;
void operator=(const DSNode&) = delete;
friend void swap(DSNode& a, DSNode& b) {
using std::swap;
swap(a.value, b.value);
swap(a.prev, b.prev);
swap(a.next, b.next);
}
};
public:
DSList() = default;
DSList(const DSList<T>&);
DSList& operator=(DSList<T>);
~DSList();
T const& get(std::size_t pos) const;
T& get(std::size_t pos);
void insert(T value);
int getsize();
template<typename U>
friend void swap(DSList<U>&, DSList<U>&);
private:
DSNode* head = nullptr;
};
template<typename T>
DSList<T>::~DSList()
{
if (head == nullptr) return;
auto current = head;
while(current->next != nullptr){
auto next = current->next;
delete current;
current = next;
}
}
template<typename T>
void DSList<T>::insert(T value)
{
auto new_node = new DSNode(std::move(value));
if (head == nullptr){
head = new_node;
return;
}
auto p = head;
while (p->next != nullptr)
p = p->next;
auto node = new DSNode(std::move(value));
p->next = node;
}
#endif //INC_20F_FLT_PLN_DSLINKEDLIST.H
int main(){
DSList<int> here;
here.insert(1);
std::cout << "Here";
}
Before you make a DLL, make a SLL, and make sure that it works properly. When I inserted, and when the list destructed there was something weird going on with your accesses. I trimmed out everything that wasn't needed for this specific solution. You'll be on your own to add the counting behavior and bulking insertion.
User contributions licensed under CC BY-SA 3.0