Stack implementation using Array (ways to improve code)

Question

Need to implement stack using array only, methods: push, pop, print. The task itself: Implement stack using only array. The only time compiler should allocate memory is through set_size function. The current code version works good enough, but I'm looking for ways to improve it's exec-time / complexity / readability etc. Any ideas? Thank you in advance.

#include <vector>
#include <string>

template <class T>
class Stack
{
 int size = 0;
 T* Array;
 int top = 0;

public:
 Stack(size_t Size);
 ~Stack()
 {
     delete[] Array;
 }
 void push(T element);
 void pop();
 void print();
};
template <class T>
Stack<T>::Stack(size_t Size)
{
 size = Size;
 top = -1;
 Array = new T[size];
}
template <class T>
void Stack<T>::push(T element)
{
 if (top >= (size - 1))
 {
     std::cout << "overflow" << std::endl;
 }
 else
 {
     Array[++top] = element;
 }
}
template <class T>
void Stack<T>::pop()
{
 if (top < 0)
 {
     std::cout << "underflow" << std::endl;
 }
 else
 {
     std::cout << Array[top--] << std::endl;
 }

}
template <class T>
void Stack<T>::print()
{
 if (top == -1)
 {
     std::cout << "empty" << std::endl;
 }
 int i = top;
 while (i > -1)
 {
     std::cout << Array[i--] << " ";
 }
 std::cout << std::endl;
}
template <class T>
Stack<T> set_size(int Size)
{
 return Stack<T>(Size);
}

int main()
{
 auto stack = set_size<std::string>(5);
 stack.push("hello");
 stack.push("hi");
 stack.push("hey");
 stack.push("greetings");
 stack.push("welcome");
 stack.print();
 stack.pop();
 stack.pop();
 stack.print();
 return 0;
}```

I'm voting to close this question as off-topic because it belongs to CodeReview, not StackOverflow. — Fureeish
– Fureeish, Commented Sep 22, 2019 at 15:53

ArnaudLR · Accepted Answer · 2019-09-22 12:41:10Z

1

Your main problem comes from the type conversion between your stack pointer top to your stack size size.

top is an int, which is a signed type. size_t is an unsigned integral type.

When testing (top >= (size - 1)), top is converted to an unsigned int and then considered as UINT_MAX instead of -1, which is always >= to any other unsigned int.

You can either use a size_t as your stack pointer, which means that you cannot use negative value, or convert (size - 1) to a signed value before comparing to top (but this last solution means that you must ensure that the size you specify as a size_t is not too big to be converted to a signed int).

Your print function has also two issues:

in your first test, you assign -1 to top instead of comparing the values
you change your top stack pointer, so that you stack is in an inconsistant state after a call to print()

answered Sep 22, 2019 at 12:41

ArnaudLR

261 bronze badge

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

2 Comments

asymmetriq Over a year ago

Thank you very much! Any other thoughts on how to improve it?

ArnaudLR Over a year ago

Your pop() function does not return any value. I suppose it is not what you need in this exercice. When unstacking a value, you are supposed to know the unstacked value. The stack would be quite useless otherwise.

SomeWittyUsername · Accepted Answer · 2019-09-22 17:43:42Z

0

Your branch predictions are possibly not optimal. You should inspect the resulting assembly to see if the prediction bets on the if rather than on else in your if...else constructs (it will probably predict the if and in this case you should put the common case in the if).
You should pass the arguments by reference and not by value. It doesn't matter in case of simple integers but if your T becomes something more complex, it will result in redundant copy upon push.

answered Sep 22, 2019 at 17:43

SomeWittyUsername

18.4k3 gold badges46 silver badges87 bronze badges

Collectives™ on Stack Overflow

Stack implementation using Array (ways to improve code)

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related