When it comes to retrieving data, two things we often want to do is push data into a structure and pop it out. Pushing and popping are the major operations of two data structures: stacks and queues. Pushing means adding a new item to a data structure at one end, and popping means pulling an item out of a data structure either at the same end of the structure, seen in stacks, or the opposite end, seen in queues. For this lesson, we will cover stacks.
A stack is essentially a data structure in which we can add items at one end and then remove them from the same end. Stacks exhibit a LIFO (last in, first out) property, which means that if you pop an item from the stack, the item to be popped will be the one that was most recently added.
To make this easier to understand, it helps to think of pushing an item into the stack as adding the item at the TOP, and popping the item from the stack as removing the item from the TOP. The top is the end at which items were most recently added, and the bottom is the end at which they were most recently removed. In queues, the top will be referred to as the back and the bottom will be referred to as the front.
Rules of the stack:
1. An item can only be added to the top.
2. An item can only be removed from the top.
3. An item can only be accessed from the top.
4. Items cannot be accessed or removed if the stack is empty.
Two ways to implement stacks include arrays and linked lists. We will start by looking at arrays.
Array stacks:
Functionally, an array has two ends, which are Position 0, and Position X-1 with X being the number of items currently in the array. Since the number of items currently in the array is the height of the stack, we should keep track of that number with an integer variable height. The array stack class looks like this:
//Note: This version of the array stack does not include a destructor, but you will want one if you use a dynamic array. If you use a dynamic array the destructor's one line is: delete[] stack;
class ArrayStack
{
private:
int stack[100];
int height;
public:
ArrayStack();
void push(int x);
int pop();
int topItem();
int size();
bool isEmpty();
};
Its constructor looks like this:
//Note: No elements of the stack are initialized since the stack starts out empty anyway.
ArrayStack::ArrayStack()
{
height = 0;
}
Now, though, here’s a big question. Which end should be the top, and which one should be the bottom?
Well, if we consider 0 the top and add the items at position 0 each time, we need to shift all the other items one position to the right (down toward the bottom), which gives the push function an okay linear runtime of O(n).
If we consider stack[height-1] to be the top, then we are pushing the items at array[height], therefore always giving us an awesome runtime of O(1).
Here’s the push function with the top end being stack[height - 1].
void ArrayStack::push(int x)
{
stack[height] = x;
height++;
}
That was easy! Now, since popping is just taking off the top item, this is what the pop function would look like.
//Invariant: Pop is not to be used if the stack’s height is zero.
int ArrayStack::pop()
{
height--;
return stack[height];
}
I’m sure some of you might be wondering why I didn’t clear the space at stack[height-1] before I cut the height by one item. This is because since the stack’s FUNCTIONAL size is height. That means that by making height one item smaller, while I am not clearing an array index, I don’t have to since that array index, despite still being in the array, is NOT in the stack.
Now, what if we wanted to look at the top item WITHOUT popping it? I’ve got you covered.
//Invariant: topItem will not be used on empty stacks.
int ArrayStack::topItem()
{
return stack[height - 1];
}
As you can see, it’s pretty much the same as the pop function except now all it does is return the item at the top.
Finally, the last two functions commonly seen in a stack are size, which returns the stack’s height, and isEmpty, which, you guessed it, tells us if the stack is empty. Both are one-liners.
bool ArrayStack::isEmpty()
{
return (height == 0);
}
int ArrayStack::size()
{
return height;
}
The explanation is that size returns the height of the stack, which is how many items are in there, and isEmpty returns whether or not the height of the stack is zero. The only reason we have the size function is to access height since the stack’s height is a private variable.
You can make a stack a dynamic array, although you will have to add a grow function to the stack to make it so the array can increase its capacity when height is too big, and you will need to include the grow function in the push function. You will also need an integer variable array_size to keep track of the array’s maximum capacity. I am not including the dynamic version of the array stack class and its member functions because it really is only COMP 11-level modifications on the regular version since you are just increasing the size of the array without shifting the positions of any elements. If you decide to make a dynamic array stack, you should be able to do everything in it with a runtime of O(n) or faster.
Here’s a picture of the array stack and its member functions. Size is not shown since height is already given.
You also can have a stack in the form of a linked list. This is interesting because almost all your work is already done for you. If you include the linked list class from lesson 1 in your stack class, either in the same file or an external file, then you can write a LinkedStack class that looks like this:
//Note: The linked stack does not include a destructor because deleting the dynamic memory of the stack's list is covered in the linked list class's destructor.
class LinkedStack
{
private:
LinkedList stack;
int height;
public:
LinkedStack();
void push(int x);
int pop();
int topItem();
int size();
bool isEmpty();
};
Ooooooh! You’re now taking advantage of the awesome programming practice of using the work that was already done for you! Some call this laziness. We programmers call it ingenuity!
Now, here’s the constructor:
//The linked list of the linked stack was not initialized because that is covered in the linked list class's constructor.
LinkedStack::LinkedStack()
{
height = 0;
}
Now here’s where it really starts to get cool!
void LinkedStack::push(int x)
{
stack.insert(x);
height++;
}
Awesome! Now all you have to do to push an item in the stack is increment height and use an insert function you had pre-made!
Now here’s pop!
//Invariant: pop will not be used on empty stacks
int LinkedStack::pop()
{
height--;
return stack.remove();
}
Once again, we are working with pre-made functions here, and as always, free stuff is awesome!
The linked stack version of isEmpty is interesting.
bool LinkedStack::isEmpty()
{
return stack.isEmpty();
}
Since the stack is being implemented as a linked list, which also has an isEmpty function, to see if the stack is empty, the stack’s isEmpty function calls the list’s isEmpty function! However, because of scope rules, since the isEmpty functions are for different classes, the computer knows which isEmpty function to call.
The linked stack’s version of size is the same as the array stack’s version of size:
int LinkedStack::size()
{
return height;
}
And finally, here’s the linked stack’s version of topItem:
//Invariant: topItem will not be used on empty stacks.
int LinkedStack::topItem()
{
return stack.head->data;
}
Note once more that since the linked list, the only piece of dynamic memory in the class, has a destructor, the LinkedStack class does not need a destructor.
Overall, every linked stack function has a runtime of O(1), as does every array stack function, however the linked stack is able to expand or shrink the stack’s maximum capacity with a runtime of O(1), whereas to do that in a dynamic array you would need to use functions with a runtime of O(n), so linked stacks are more space-efficient.
Dynamic array stacks would have a faster destructor than linked stacks, O(1) vs. O(n) since the dynamic array stacks would just have to delete the array, whereas the linked stacks would have to delete the list one node at a time. Overall, though, both types of stacks are very fast.
There is one other type of stack you should be familiar with, and that is the recursion stack. Whenever you call a function, its call is basically added to a stack, and all of the function calls in that function call are also in the stack. In a recursive function, the last recursion to be called is the first function to be completed.
Each time a recursive function is called, it is like pushing a function call into the stack. When the function call is finished, that function is essentially popped from the stack. Therefore, the last recursion to be called is the one at the top of the stack. Since this recursion won’t call itself, that function call will terminate and be popped from the stack. The recursion in which that recursion was called is now at the top of the stack, and since its function call to itself is over, that recursion will finish running, terminate itself, and be popped from the stack, all the way until the recursion is ended.
Now you know all about stacks. Next, we will be learning about queues, which are very similar, but have a FIFO (first in first out) property.
No comments :
Post a Comment