21 Stack a stack is a list in which insertion and deletion take place at the same end This end is called top The other end is called bottom Stacks are known as LIFO (Last In, First Out)lists The last element inserted will be the first to be retrieved
21 Stack A stack is a list in which insertion and deletion take place at the same end This end is called top The other end is called bottom Stacks are known as LIFO (Last In, First Out) lists. The last element inserted will be the first to be retrieved
Push and pop Primary operations: Push and Pop Push Add an element to the top of the stack Pop Remove the element at the top of the stack empty stack push an element push another pop B top top A . op
22 Push and Pop Primary operations: Push and Pop Push Add an element to the top of the stack Pop Remove the element at the top of the stack top empty stack A top push an element top push another A B top pop A
Implementation of stacks Any list implementation could be used to implement a stack Arrays(static: the size of stack is given initially) Linked lists(dynamic: never become full) We will explore implementations based on arrays and linked list
23 Implementation of Stacks Any list implementation could be used to implement a stack Arrays (static: the size of stack is given initially) Linked lists (dynamic: never become full) We will explore implementations based on arrays and linked list
24 Stack ADt class Stack public: Stacks Stack(const Stack& stack / copy constructor constructor/destructor stack oi // destructor empty ( head element double top() consti //keep the stack unchangednspection addhead void push(const double x)i access delete head double pop ()i / change the stac update logical constructor/destructor. composition/decompositi / optional void display()const bool full( consti p rivate Compare with List, see that it,'s operations that define the type! stack'is the same as our unsorted list operating at the head o
24 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 … // optional void display() const; bool full() const; private: … }; Stack ADT update, ‘logical’ constructor/destructor, composition/decomposition ‘physical’ constructor/destructor Compare with List, see that it’s ‘operations’ that define the type! ‘stack’ is the same as our ‘unsorted’ list operating at the head ☺ inspection, access headElement addHead deleteHead
Using stack int main( stack stack stack push(5.0)i stack push(6.5)i stack push(-30)i stack push(-8.0) stack display ( cout < Top: < stack top()<< endl tack. pop() esult cout uTop stack top()<< endli while (! stack. empty()) stack pop()i stack display ( 8 return 0 6.5 5 Top: -8 Op top
25 Using Stack int main() { Stack stack; stack.push(5.0); stack.push(6.5); stack.push(-3.0); stack.push(-8.0); stack.display(); cout << "Top: " << stack.top() << endl; stack.pop(); cout << "Top: " << stack.top() << endl; while (!stack.empty()) stack.pop(); stack.display(); return 0; } result