26 Stack using linked lists struct Node f double datai class stack ublic Stack(i // constructor Stack(const stack& stack) / copy constructor -Stack() // destru empty ( op() // ke void push(const double x)i double pop() // change the stac bool full(i unnecessary for linked list void display ()const
26 struct Node{ public: double data; Node* next; }; class Stack { public: Stack(); // constructor Stack(const Stack& stack); // copy constructor ~Stack(); // destructor bool empty() const; double top() const; // keep the stack unchanged void push(const double x); double pop(); // change the stack bool full(); // unnecessary for linked lists void display() const; private: Node* top; }; Stack using linked lists
27 Push(addHead), Pop(deleteHead void List:: addHead(int newdata)i Nodeptr newptr new Nodei newptr->dat ewdata newPtr->next head; From 'addHead to push head newPtri void Stack:: push(double x)i Node* newptr new Node lewptr->data newPtr->next =top; top ewer
27 void List::addHead(int newdata){ Nodeptr newPtr = new Node; newPtr->data = newdata; newPtr->next = head; head = newPtr; } void Stack::push(double x){ Node* newPtr = new Node; newPtr->data = x; newPtr->next = top; top = newPtr; } From ‘addHead’ to ‘push’ Push (addHead), Pop (deleteHead)
28 Stack using arrays lass stack i public: Stack(int size = 10)i Stack(const Stack& stack aStack() delete[ values; bool empty()i return (top 1) double top ()i void push (const double x)i double pop()i bool full() return ( top = size)i K void display ()i private: int size // max stack size size -1 int topi // current top of stack oublex va⊥ues; / element array
28 Stack using arrays class Stack { public: Stack(int size = 10); Stack(const Stack& stack); ~Stack() { delete[] values; } bool empty() { return (top == -1); } double top(); void push(const double x); double pop(); bool full() { return (top == size); } void display(); private: int size; // max stack size = size - 1 int top; // current top of stack double* values; // element array };
29 Attributes of stack size: the max size of stack top: the index of the top element of stack values: point to an array which stores elements of stack Operations of stack empty: return true if stack is empty, return false otherwise full: return true if stack is full return false otherwise top: return the element at the top of stack push: add an element to the top of stack pop: delete the element at the top of stack display: print all the data in the stack
29 Attributes of Stack size: the max size of stack top: the index of the top element of stack values: point to an array which stores elements of stack Operations of Stack empty: return true if stack is empty, return false otherwise full: return true if stack is full, return false otherwise top: return the element at the top of stack push: add an element to the top of stack pop: delete the element at the top of stack display: print all the data in the stack
30 Stack constructor Allocate a stack array of s ize. by default size =10 Initially top is set to -1. It means the stack is empty When the stack is full, top will have its maximum value, i.e SIZe Stack: Stack(int size /*=10*/) Va⊥ues new double [size]i top maxTop Although the constructor dynamically allocates the stack array, the stack is still static, The size is fixed after the initialization
30 Allocate a stack array of size. By default, size = 10. Initially top is set to -1. It means the stack is empty. When the stack is full, top will have its maximum value, i.e. size – 1. Stack::Stack(int size /*= 10*/) { values = new double[size]; top = -1; maxTop = size - 1; } Although the constructor dynamically allocates the stack array, the stack is still static. The size is fixed after the initialization. Stack constructor