Before you keep reading...

Runestone Academy can only continue if we get support from individuals like you. As a student you are well aware of the high cost of textbooks. Our mission is to provide great books to you for free, but we ask that you consider a $10 donation, more if you can or less if $10 is a burden.

Support Runestone Academy Today

Before you keep reading...

Making great stuff takes time and $$. If you appreciate the book you are reading now and want to keep quality materials free for other students please consider a donation to Runestone Academy. We ask that you consider a $10 donation, but if you can give more thats great, if $10 is too much for your budget we would be happy with whatever you can afford as a show of support.

Support Runestone Academy Today

3.5. Using a Stack in C++

Now that we have clearly defined the stack as an abstract data type we will turn our attention to using a stack with the help of the Standard Template Library (STL) in C++. Recall that when we give an abstract data type a physical implementation we refer to the implementation as a data structure.

As we described in Chapter 1, in C++, as in any object-oriented programming language, the implementation of choice for an abstract data type such as a stack is the creation of a new class. The stack operations are implemented as methods. However, the STL already has a well written implementation of the Stack class.

The following stack implementation (ActiveCode 1) assumes that the end of the array will hold the top element of the stack. As the stack grows (as push operations occur), new items will be added on the end of the array. pop operations will manipulate that same end.

//Tests the push, empty, size, pop, and top methods of the stack library. #include <iostream> #include <stack> // Calling Stack from the STL using namespace std; int main() { stack<int> newStack; newStack.push(3); //Adds 3 to the stack newStack.push(8); newStack.push(15); // returns a boolean response depending on if the stack is empty or not cout << "Stack Empty? " << newStack.empty() << endl; // returns the size of the stack itself cout << "Stack Size: " << newStack.size() << endl; // returns the topmost element of the stack cout << "Top Element of the Stack: " << newStack.top() << endl; // removes the topmost element of the stack newStack.pop(); cout << "Top Element of the Stack: " << newStack.top() << endl; cout << "Stack Size: " << newStack.size() << endl; return 0; }

#Tests the push, empty, size, pop, and top methods of the stack library. class Stack: def __init__(self): #initializes new stack instance self.items = [] def isEmpty(self): #returns boolean return self.items == [] def push(self, item): #pushes new item onto stack self.items.append(item) def pop(self): #removes topmost item from stack return self.items.pop() def top(self): #returns the topmost item from the stack return self.items[len(self.items)-1] def size(self): #returns the size of the stack return len(self.items) def main(): newStack = Stack() newStack.push(4) newStack.push(8) newStack.push(15) print("Stack Empty? ", newStack.isEmpty()) print("Stack Size: ", newStack.size()) print("Top Element of the Stack: ", newStack.top()) newStack.pop(); print("Top Element of the Stack: ", newStack.top()) main()

Self Check

Q-3: Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?

stack<int> m;
m.push(5);
m.push(12);
m.pop();
m.push(27);
cout << m.top();

• 5
• Remember that a stack is built from the bottom up.
• 12
• pay attention to the line that says m.pop();.
• 27
• Good job. This is correct because the 12 was poped of from the end and the 27 was pushed.
• The stack is empty
• This would mean everyting is removed from the stack, when does that happen?

Q-4: Given the following sequence of stack operations, what is the top item on the stack when the sequence is complete?

stack<int> m;
m.push(37);
m.push(56);
m.push(4);
while (!m.empty()){
    m.pop();
    m.pop();
}

• 37
• You may want to check out the docs for
• the stack is empty
• There is an odd number of things on the stack but each time through the loop 2 things are popped.
• an error will occur
• Good Job, this is true because the stack can not evenly pop off every item within itself, because there is an odd number of items.
• 4
• You may want to check out the docs for isEmpty

You have attempted of activities on this page