C++

Forum

 
Stack data structure as an ADT

yoked88 (140)
So I've been working on implementing a stack data structure as an ADT, the program compiles, but when I try and push elements on top of the stack, for some reason the stack is full. Can anyone help? Thank you in advance.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#ifndef H_stackADT
#define H_stackADT

template <class Type>
class stackADT
{
public:
	virtual void initializeStack() = 0;
	virtual bool isEmptyStack() const = 0;
	virtual bool isFullStack() const = 0;
	virtual void push(const Type&) = 0;
	virtual Type top() const = 0;
	virtual void pop() = 0;
};

#endif 



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
 
#ifndef H_stackType
#define H_stackType

#include <iostream>
#include <cassert>
#include "stackADT.h"

using namespace std;

template <class Type>
class stackType: public stackADT<Type>
{
public:
	const stackType<Type>& operator=(const stackType<Type>&);
	void initializeStack();
	bool isEmptyStack() const;
	bool isFullStack() const;
	void push(const Type&);
	Type top() const;
	void pop();
	stackType(int stackSize = 100);
	stackType(const stackType<Type>&);
	~stackType();
private:
	int maxStackSize;
	int stackTop;
	Type *list;
	void copyStack(const stackType<Type>&);
};

template <class Type>
void stackType<Type>::initializeStack()
{
	stackTop = 0;
}

template <class Type>
bool stackType<Type>::isEmptyStack() const
{
	return (stackTop == 0);
}

template <class Type>
bool stackType<Type>::isFullStack() const
{
	return (stackTop == maxStackSize);
}

template <class Type>
void stackType<Type>::push(const Type& item)
{
	if(!isFullStack())
	{
		list[stackTop] = item;
		stackTop++;
	}
	else
		cout << "The stack is full." << endl;
}

template <class Type>
Type stackType<Type>::top() const
{
	assert(stackTop != 0);
	return list[stackTop - 1];
}

template <class Type>
void stackType<Type>::pop()
{
	if(!isEmptyStack())
		stackTop--;
	else
		cout << "The stack is empty." << endl;
}

template <class Type>
void stackType<Type>::copyStack(const stackType<Type>& other)
{
	delete [] list;
	maxStackSize = other.maxStackSize;
	stackTop = other.stackTop;
	list = new Type[maxStackSize];
	for(int j = 0; j < stackTop; j++)
		list[j] = other.list[j];
}

template <class Type>
stackType<Type>::stackType(int stackSize)
{
	if(stackSize = 0)
	{
		cout << "Size must be positive. Creating default size of 100." << endl;
	}
	else
		maxStackSize = stackSize;
	stackTop = 0;
	list = new Type[maxStackSize];
}

template <class Type>
stackType<Type>::~stackType()
{
	delete [] list;
}

template <class Type>
stackType<Type>::stackType(const stackType<Type>& other)
{
	list = NULL;
	copyStack(other);
}

template <class Type>
const stackType<Type>& stackType<Type>::operator =(const stackType<Type>& other)
{
	if(this != &other)
		copyStack(other);
	return *this;
}

#endif 


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
 
#include <iostream>
#include "stackType.h"

using namespace std;

void test(stackType<int>);

int main()
{
	stackType<int> stack(50), copyStack(50), dummyStack(100);
	stack.initializeStack();
	stack.push(12);
	stack.push(16);
	stack.push(38);
	stack.push(13);
	copyStack = stack;
	cout << "copyStack = ";
	while(!copyStack.isEmptyStack())
	{
		cout << copyStack.top() << " ";
		copyStack.pop();
	}
	cout << endl;
	copyStack = stack;
	test(stack);
	system("PAUSE");
	return 0;
}

void test(stackType<int> other)
{
	if(!other.isEmptyStack())
		cout << "other is not empty." << endl
		     << "top element of other = "
			 << other.top() << endl;
}
Zhuge (4664)
Line 91: You are using assignment (=) in your if statement condition where you wanted comparison (==).
kbw (9488)
You are mixing templates and inheritance polymophism.

An ADT is typically not polymorphic, it's usually a concretet type (like FILE) or a template (like stack<T>).

Thinking is a stack algorithm is exactly the same, irrespective of what type is bing stacked. Inheritance implies that the derived thing is a little different from the base.
Last edited on
yoked88 (140)
@Zhuge, thank you, that fixed it, I was staring at the push function for over an hour.

@kbw The reason I'm making the stack an ADT is because I'm implementing it as an array in the above example, and then going to implement it as a linked list and doubly linked list. It doesn't necessarily have to be abstract, would there be a more efficient way?
kbw (9488)
I was trying to point out that you should either do:
1
2
3
4
5
6
7
8
9
10
11
 
class stackADT
{
public:
	virtual ~stackADT() = 0;
	virtual void initializeStack() = 0;
	virtual bool isEmptyStack() const = 0;
	virtual bool isFullStack() const = 0;
	virtual void push(const Type&) = 0;
	virtual Type top() const = 0;
	virtual void pop() = 0;
};


or
1
2
3
4
5
6
7
8
9
10
11
12
 
template <class Type>
class stackADT
{
public:
	stackADT();
	~stackADT();
	bool isEmptyStack() const;
	bool isFullStack() const;
	void push(const Type&);
	Type top() const;
	void pop();
};


In engineering, everything's a trade off. The polymorphic approach generates a vtable per class and indirection on each call. The template approach generates an entire new class for each time, this used to be called code-bloat, but this is the method most often use.

You are mixing both methods, so it seems a little confused.
Topic archived. No new replies allowed.