Algorithms C++ Edition (2015)
Part 1: Identifying the Data Types
Chapter 1c: The Stack, as a Linked List
The Data Structure
You’ll need one Linked List node - the Head - as well as an integer to keep track of the Item Count. Luckily, there are no Stack Overflows as a Linked List. Chances are, you may have to design the Linked List Nodes as well.
// A Singly Linked List Node has:
// - the Next Node (Point to the Next Node)
// - the Data Item (choose what data type you want)
CompositeStructure Node {
Node NEXTID
(choose a data type) ITEM
}
// Abstract Data Type: Stack, as a Linked List
// The Stack Has:
// - a Head (Linked List Node)
CompositeStructure LinkedListStack {
Node HEAD
Integer COUNT
}
Now, let’s look at how the Push() and Pop() methods work, in detail:
Linked List Stack: Push() Function
The Push() function from a Linked List Stack adds items into that stack. It does this in the following procedure, in this particular order:
1) Make a new Local Variable. Set it as a Node. This will be the New Linked List head.
2) Set your input item to be the New Head Node’s data
3) Set the previous head’s next node to the New Head.
4) Set the New Head as the Linked List’s Stack Head
5) And Finally, Increment the Item Count
After the push() procedure successfully inserts an item, you should have that item at the head of the linked list and the item count should be increased by 1.
Linked List Stack: Pop() Function
In contrast to the Push() method, the Pop() method from a Linked List 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 if the Head Node isn’t Null (if the Head Node Exists)
2) If so, either return NULL or report a stack underflow error
3) If there’s an item to pop, create a Local Variable. Set it to be your soon-to-be return item (it should be the Head Node!)
4) Get the Node NEXT to the Head. This will NOW be the new LinkedList Head.
5) Decrement the Item Count
6) 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 the Linked List Head. Also, the item count should be decreased by 1.
C++ 01a: The Stack, as an Array
Here, we start playing around with some basic data structures in C++ code. You may also use online IDE’s such as rextester.com, ideone.com, or codepad.org.
Future algorithms start to become more complex, so understand these well!
The Data Structure, in C++
In C++, we’re going to define our ArrayStack as a data class. First, we define our Class and its fields. Later, we’ll include the methods Push() and Pop()
By default, we’ll set the Array Size to 10. There is also the constructor included. In your main code, if you need to create an instance of an array stack, simply call the constructor method.
// 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)
class ArrayStack {
int MAXSIZE = 10;
int COUNT;
<choose a data type> ARRAY[10];
public:
// INPUT: -nothing
// OUTPUT: - nothing
// EFFECT: Constructor: Array Stack, with its max size as Initial Value
ArrayStack() {
this->COUNT = 0;
};
// INSERT PUSH() FUNCTION HERE
//________________
// INSERT POP() FUNCTION HERE
//________________
};
Note: the data type can be whatever you wish. It depends on the data you wish to process.
Array Stack: Push() Function, in C++
Remember the procedure behind the push() function. First note the steps it takes to enter the data into the stack, then check that the steps actually process the way you intend it to be.
In this version, we simply get our system to print “Stack Overflow” and end the function if we try to enter too many items in the array
We’ve also included a few print lines that show you that the function actually pushed the value into the array
// INPUT: - an item (some Data Type)
// OUTPUT: - nothing
// EFFECT: inserts an item (some Data Type) onto our Array Stack
void push(<chosen data type> item) {
// 1) Check if there’s room in the array for the extra item
if (this->MAXSIZE <= this->COUNT) {
// 2) If there’s no room in the array,
// print a Stack Overflow and end the function
std::cout << "Stack Overflow!\n";
return;
}
// 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
this->ARRAY[COUNT] = item;
// PROOF that it inserted:
std::cout << "New Item is " << this->ARRAY[COUNT] << " At Index "<< COUNT << "\n";
// 4) And Finally, Increment the Item Count
this->COUNT += 1;
// PROOF of incremented Item Count:
std::cout << "Count is " << this->COUNT << "\n";
};
OPTIONAL: Array Size Increaser (phase 1.2)
If you choose to go with a variable-size array, include this method along with the others. This version will double the array size where needed. Take note of the procedure steps. Array sizes, by definition, are fixed. However, this will simply replace the old array with a larger one - entering each item one by one in its original order.
Array Stack: Pop() Function, in C++
Just like the Push() function, take note of the procedural steps in how a Pop function is performed. Here, we implement it in C++.
If pop() is called when there is no items in the stack, we’ll just print out a message and end the function.
// INPUT: - nothing
// OUTPUT:- an item (some Data Type)
// EFFECT: removes and retrieves an item (some Data Type) from our Array Stack
<chosen data type> pop() {
// 1) Check the Array Count if there are any items to pop.
if (this->COUNT <= 0) {
// 2) If not, print a message and return null
std::cout << "Stack Underflow!\n";
return NULL;
};
// 3) If there’s an item to pop, Decrement the Item Count first.
// We’re going to remove an item!
this->COUNT -= 1;
// 4) Then,create a Local Variable.
// Set it to be your return item
// (it should be the item at the end of the stack!)
<chosen data type> r = this->ARRAY[COUNT];
// PROOF that it loaded the end item:
std::cout << "Loaded is " << this->ARRAY[COUNT] << " at index "<< this->COUNT << "\n";
// Remove the item at the End of the Stack afterwards
this->ARRAY[COUNT] = NULL;
// 5) And Finally, the function returns your item and ends.
return r;
}
};
C++ 01b: The Stack, as a Linked List
The Data Structure, in C++
In C++, we use pointers to link the nodes together. This way, each node has the memory address of the next node. Instead of duplicating nodes and taking up data space in the computer memory, we just “point” out to what the next node is.
We have class definitions for both a node and the linked list. We also have constructors for both a Node and the Linked List Stack. You need both of them together, as the Stack requires nodes to be made
// A Singly Linked List Node has:
// - the Next Node (Point to the Next Node)
// - the Data Item (choose what data type you want)
class Node {
public:
Node* NEXT;
<chosen data type> ITEM;
// INPUT: - a data item
// OUTPUT: - nothing
// EFFECT: Constructor: Linked List Node, with the Data Item as its input
Node(<chosen data type> item) {
this->ITEM = item;
};
};
// Abstract Data Type: Stack, as a Linked List
// The Stack Has:
// - a Default Head (Linked List Node)
// - an item count (integer)
class LinkedListStack {
Node* HEAD;
int COUNT;
public:
// INPUT: - nothing
// OUTPUT: - nothing
// EFFECT: Constructor: Linked List Stack,
LinkedListStack() {
this->HEAD = new Node(<data with chosen data type>);
this->COUNT = 0;
};
// INSERT PUSH() FUNCTION HERE
//________________
// INSERT POP() FUNCTION HERE
//________________
};
For advanced users, the item count is optional. However, it does come in handy in optimizing your data structures and operations, as well as helping it become more robust.
Linked List Stack: Push() Function, in C++
// INPUT: - an item (some Data Type)
// OUTPUT: - nothing
// EFFECT: inserts an item (some Data Type) onto our Linked List Stack
void push(<chosen data type> INPUT) {
// 1) Make a new Local Variable. Set it as a Node.
// This will be the New Linked List head.
Node* NEWHEAD = new Node(INPUT);
// 2) Set your input item to be the New Head Node’s data
// (The Constructor does this)
// 3) Set the previous head’s next node to the New Head
NEWHEAD->NEXT = this->HEAD;
// 4) Set the New Head as the Linked List’s Stack Head
this->HEAD = NEWHEAD;
// PROOF that it inserted:
std::cout << "Head item is:" << HEAD->ITEM << "\n";
std::cout << "Next Head item is:" << HEAD->NEXT->ITEM << "\n";
// 5) Increment the Item Count
this->COUNT += 1;
};
Linked List Stack: Pop() Function
// INPUT: - nothing
// OUTPUT:- an item (some Data Type)
// EFFECT: removes and retrieves an item (some Data Type) from our Linked List Stack
<chosen data type> pop() {
// 1) Check if the Head Node isn’t Null (if the Head Node Exists)
if (this->HEAD->NEXT == NULL) {
// 2) If so, print a message and return null
std::cout << "Stack Underflow!" << "\n";
return NULL;
}
// 3) If there’s an item to pop, create a Local Variable.
// Set it to be your soon-to-be return item
// (it should be the Head Node!)
<chosen data type> r = HEAD->ITEM;
// PROOF that it loaded:
std::cout << "loaded item is:" << r << "\n";
// 4) Get the Node NEXT to the Head.
// This will NOW be the new LinkedList Head.
this->HEAD = this->HEAD->NEXT;
// PROOF that head has been moved:
std::cout << "Head item is now: " << HEAD->ITEM << "\n";
// 5) Decrement the Item Count
this->COUNT -= 1;
// 7) And Finally, the function returns your item and ends.
return r;
}
C++ Workshop #1
Stacks At Work
Now we’re going to see the Stack in action.
Part 1:
1) Set up an IDE of your choice (online IDE’s such as rextester.com, ideone.com, or codepad.org will do as well)
2) In the above portion of your code, make sure you have these lines included:
#include <iostream>
using namespace std;
These allow your C++ code to use strings and other basic data types.
3) Copy-paste either the ArrayStack or the LinkedListStack class from the previous chapters, along with their respective push() and pop() methods. You may remove the Print PROOF statements if you wish.
4) In all places of your code that require you to choose your data type, set them as a string:
<chosen data type> ====> string
5a) If you chose ArrayStack, to avoid errors, change the following lines from the pop() method below:
this->ARRAY[COUNT] = NULL;
to
this->ARRAY[COUNT].clear();
5b) If you chose LinkedListStack, to avoid errors, change the following lines from the constructor method below:
this->HEAD = new Node(<data with chosen data type>);
to
this->HEAD = new Node(“BOTTOM NODE”);
6) Afterwards, copy these lines as your main() method:
// ——————————-
int main()
{
// Fill Blank as ArrayStack* or LinkedListStack*
// DO NOT forget the star! *
___ m;
// Fill blank as ArrayStack() or LinkedListStack()
// depending on whatever you chose previously
// It's a Constructor: DO NOT forget the parentheses! ()
m = new ___;
string s;
m->push("A");
m->push("B");
m->push("C");
m->push("D");
string d = m->pop();
d = m->pop();
std::cout << "local var d is C? " << d << "\n";
string c = m->pop();
std::cout << "local var c is B? " << c << "\n";
m->push("Y");
m->push("D");
m->push("D");
m->push("U");
m->push("B");
m->push("T");
m->push("S");
m->push("E");
m->push("B");
m->push("X");
for(int i = 0; i < 9; i++) {
std::cout << "Popped: " << m->pop() << "\n";
};
d = m->pop();
d = m->pop();
std::cout << "Trigger Stack Underflow: " << m->pop() << "\n";
};
// ——————————-
What happened?
There should be two lines printed that say
“ local var d is C? C
local var c is B? B ”
Then, we attempted to spell BESTBUDDY.
If you used an ArrayStack, we managed to get all 9 letters in, but not the “X”. Why? Because a stack overflow has just happened. We tried to get the extra item “X” in, but we couldn’t. The stack was full.
If you used a LinkedListStack, we managed to input the “X”. However, the “Y” in BESTBUDDY wasn’t popped. Because a Linked List has no limits, the “X” was popped as part of the 9 pops - spelling XBESTBUDD.
Afterwards, we tried to pop a few more items.
But eventually, the stack was empty. So what happened? A stack underflow occurred.
Part 2: Switching List Types
If you switch to the other list type (array or linked list), you should have the same results. Try it out, and note the differences between the two data structures.