Stacks →
In this post, we introduce Stack - a data structure closely related to Queue. It differs however in the order of operations that we perform on the constituent elements. While queue provided a FIFO (First-In-First-Out) order of processing, stack provides us LIFO (Last-In-First-Out), just as you would pick the last element that you put on the stack before picking out the other elements - just like in the stack of books below, it is very likely you added the blue book on the top very recently (Last-In) and you would pick out this book (on the top of the stack - First-Out) before picking out, say, the green books.
Again, as with queues, we can use an array or a linked list to store our elements. Let use see how to define a Stack class using an array implementation.
#define MAXSIZE 100
class Stack {
int top; // top of the stack
int arr[MAXSIZE]; // array that implements the stack
public:
Stack ();
bool push (int item);
int pop ();
int top_of_stack ();
bool is_empty ();
};
Stack::Stack () {
top = -1;
}We add elements to our stack using the push() method, remove elements from the stack (actually from the top of our stack) using pop() method, and we also keep track of the top of the stack because that’s where interesting actions happen.
We will see the different methods in the following posts. Stay tuned!.