Stacks

CS112 | Victor Norman

But first… Abstract Data Types (ADTs)

An ADT consists of…

• A set of operations defined from the users' point of view.
• The algorithms for the operations.
• The values the data structure can hold.

​

Note: it does not define how the data is stored (array, linked list, etc.). That's why it is abstract.

Stack ADT

A Stack is like…

​

what�operations�can we do?

​

Operations on a Stack of plates

put a new plate on top

push(plate)

take a plate off the top

plate = pop()

look at the top plate

plate = peekTop()

is the stack empty?

bool empty = isEmpty()

Questions

If you push a green plate on a stack, and then push a white plate on the stack, and then pop the stack once, what plate do you get?

If you pop again, what plate do you get?

If you push these letters on the stack: 'Z', 'U', 'R', 'I', 'E', 'L' and then pop the stack until it is empty printing each value, what did you see?

​

In what order do you get items compared to the order you put them on?

LIFO = Last In, First Out

Applications of Stacks in CS

Ctrl-Z

URLs in browser

functions calling functions calling functions…

Solving a maze.

Reversing stuff.

Questions

Should there be a limit to how many items can be pushed?

If so, what happens when code tries to push onto a full stack?

What should happen when code tries to pop an empty stack?

(If we have a max size then we should provide an isFull() method.)

​

What data structure should we use internally to store data items in the stack?

Question 1

s is a Stack, and these operations are performed:

s.push(7);

s.push(8);

s.pop();

cout << s.peekTop();

What is the output?

​

1. 7
2. 8
3. 15
4. Error

​

1. 7

Question 2

s is a Stack, and these operations are performed:

s.push(7);

s.push(8);

s.pop();

s.pop();

cout << s.peekTop();

What is the output?

​

• 7
• 8
• 15
• Error

​

• Error

Data Structure to Implement a Stack?

5 choices:

• array
• dynamic array
• linked list
• (internal) List (or STL list)
• (internal) Vec/PyList (or STL vector)

Let's evaluate each choice...

Crucial Idea: Interface vs. Implementation

Interface: what the user interacts with

Implementation: how the interface is implemented.

​

Separate the two and and you can change the implementation without the user changing their code!

.h vs. .cpp

Interface for push()

.h file:

class Stack {

void push(const Item &it); // might throw exception

…

};

Question 3

Where is it better to put the top of the stack, when implementing using an array or dynamic array?

​

• The top is always at location 0 in the array.
• The top is always at location mySize - 1 (where mySize is # of elements in the stack).
• It does not actually matter. Both solutions are equally efficient.

​

​

• 2. The top is always at location mySize - 1 (where mySize is # of elements in the stack).

Implementations for push() using fixed-size array

Best: put top of stack at location mySize - 1, so you don't have to shift values up or down for pushes and pops.

​

Implementation for push() using an array

(in .h: have myArray[] declared.)

​

void Stack::push(const Item &it) {

if (isFull()) {

throw StackFullException();

}

myArray[mySize] = it;

mySize++; // could combine with previous line

}

If using dynamic array, check capacity, possibly double array size, copy values, etc.

​

And, stack is never full.

​

(copy code from PyList::append())

Question 4

Where is it better to put the top of the stack, when implementing using a singly-linked list?

​

• The top is always at myFirst.
• The top is always at myLast.
• It does not actually matter. Both solutions are equally efficient.

​

​

• 1. The top is always at myFirst.

Implementation for push() using linked list

(in .h: have Node *myFirst, Node *myLast declared.)

​

void Stack::push(const Item &it) {

code copied from List's prepend() method

(new call, pointer manipulation, changing size)

}

Using an "internal" List or "internal" dynamic array

What does Prof. Norman mean by this?

class Stack {

private:

List myList; // instead of Node *myFirst, myLast, etc

};

Implementation of push()

void Stack::push(const Item &it) {

myList.prepend(it);

}

​

Done! Handles exceptions and is well-tested.

Each method in Stack is 1 line!