Algorithms C++ Edition (2015)

Part 1: Identifying the Data Types

Chapter 1b: The Stack, as an Array

The Data Structure

You’ll need the actual array, as well as two integers: the max size and the current item count.

// Abstract Data Type: Stack, as an Array

// The Stack Has:

// - the Actual Array (with Size and Data Type)

// - the Max Size of the Stack (Integer)

// - the Current Item Count (Integer)

CompositeStructure ArrayStack {

Integer MAXSIZE

Integer COUNT

(choose a data type) ARRAY[MAXSIZE]

}

Now, let’s look at how the Push() and Pop() methods work, in detail:

Array Stack: Push() Function

The Push() function from an Array Stack adds items into that stack. It does this in the following procedure, in this particular order:

1) Check if there’s room in the array for the extra item

2) If there’s no room in the array, either report a stack overflow error (if fixed-size array) or increase the array size (if variable array)

3) If there’s room in the array, add the item to the stack. Set the new item’s index as the current Item Count (so the item is the very last item in the Stack)

4) And Finally, Increment the Item Count

After the push() procedure successfully inserts an item, you should have that item at the end of the array and the item count should be increased by 1.

Array Stack: Pop() Function

In contrast to the Push() method, the Pop() method from an Array Stack removes an item from that stack. The function returns that item as the Function Output. It does this in the following procedure, in this particular order:

1) Check the Array Count if there are any items to pop.

2) If not, either return NULL or report a stack underflow error

3) If there’s an item to pop, Decrement the Item Count first. We’re going to remove an item!

4) Then,create a Local Variable. Set it to be your return item (it should be the item at the end of the stack!) Remove the item at the End of the Stack afterwards

5) And Finally, the function returns your item and ends.

After the pop() procedure successfully removes and retrieves an item, the item should be the item that was at the end of the array. Also, the item count should be decreased by 1.