DILI #11: Stack and Queue

Stack and queue are two of the most fundamental and literal data structures in computer science. As they work how they sound like.They are both linear data structures, but they differ in the way that elements are added and removed.

1. STACK:
a) Definition:

A stack is a Last In First Out (LIFO) data structure. This means that the last element added to the stack is the first element to be removed. A stack is a stack. Like a stack of book or a stack of unwashed dishes that your mom told you to do but you are too lazy and you ended up get your butt whooped. Anyways, when you add a book to the pile, you put it on top of the other books. When you remove a book from the pile, you take the top book off (if you're a normal person and not a psychopath and just take it from the middle).

b) The Code:

To use stack you can either use STL(Standard Template Library) by doing

#include <stack>

or if you're an overachiever, you can do it the hard way using class.

#include <iostream>
class MyStack {
    private:
        vector<int> data;               // store elements
    public:
        /** Insert an element into the stack. */
        void push(int x) {
            data.push_back(x);
        }
        /** Checks whether the queue is empty or not. */
        bool isEmpty() {
            return data.empty();
        }
        /** Get the top item from the queue. */
        int top() {
            return data.back();
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        bool pop() {
            if (isEmpty()) {
                return false;
            }
            data.pop_back();
            return true;
   }
};

c) The Reverse Polish Notation:

In Rverse Polish Notation, or how I like to call it: The Indonesian Notation, the operands are pushed onto a stack, and the operators are applied to the top two operands on the stack. The result of the operation is then pushed back onto the stack.

For example, the expression 3 + 4 * 5 in RPN would be written as 3 4 5 * +. The operands 3 and 4 are pushed onto the stack, and then the operator * is applied to them. The result, 12, is then pushed back onto the stack. The operator + is then applied to 12 and 5, and the final result, 17, is the output of the expression.

RPN is a very efficient notation for evaluating mathematical expressions. This is because the order of operations is implicit in the notation, so there is no need to use parentheses to group the operands.

CODE:

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int n = tokens.size();
        for(int i = 0; i < n; i++){
            if(tokens.size() > 1 || isdigit(tokens[i]) st.push(stoi(tokens[i]));
            else{
                int x2 = st.top();
                st.pop();
                int x1 = st.top();
                st.pop();
                switch(tokens[i]){
                    case '+': x1 = x1 + x2; break;
                    case '-': x1 = x1 - x2; break;
                    case '*': x1 = x1 * x2; break;
                    case '/': x1 = x1 / x2; break;
                }
                st.push(x1);
            }
        }
        return st.top();
    }
};

2. QUEUE
a) Definition

A queue is a First In First Out (FIFO) data structure. This means that the first element added to the queue is the first element to be removed. A queue can be visualized as a line of people waiting to buy tickets. So, literally a queue, the first person in line is the first person to get a ticket and the person that arrived later will be at the end of the queue. Now you can tell your kids that computers know manners so you should too!

b) The Code:

Not much to say:

• The Lazy way:

#include <queue>

• The Asian way:

class MyQueue {
    private:
        // store elements
        vector<int> data;       
        // a pointer to indicate the start position
        int p_start;            
    public:
        MyQueue() {p_start = 0;}
        /** Insert an element into the queue. Return true if the operation is successful. */
        bool enQueue(int x) {
            data.push_back(x);
            return true;
        }
        /** Delete an element from the queue. Return true if the operation is successful. */
        bool deQueue() {
            if (isEmpty()) {
                return false;
            }
            p_start++;
            return true;
        };
        /** Get the front item from the queue. */
        int Front() {
            return data[p_start];
        };
        /** Checks whether the queue is empty or not. */
        bool isEmpty()  {
            return p_start >= data.size();
        }
};

Though the Asian way looks more impressive, it's inefficient. As, you Dequeue, the space before it is left empty. So, if given a limited space or a fixed-queue, we are screwed.

FYI: To enter a queue is Enqueue and to be off a queue is Dequeue

c) Circular Queue:

Though not as interesting at the Polish up there, this is a neat concept as well, a circular queue. It ultilized the wasted space left by the Asian way of making a queue in a fixed space. For a better visualizations, you can check it out on Leetcodes.

CODE:

class MyCircularQueue {
private:
    vector<int> data;
    int head = 0;
    int tail = 0;
public:
    MyCircularQueue(int k): data(k){}

    bool enQueue(int value) {
        if(isFull()) return false;
        data[(head + tail++) % data.size()] = value;
        return true;
    }

    bool deQueue() {
        if(isEmpty()) return false;
        head = (head + 1) % data.size();
        tail--;
        return true;
    }

    int Front() {
        if(isEmpty()) return -1;
        return data[head];
    }

    int Rear() {
        if(isEmpty()) return -1;
        return data[(head + tail - 1) % data.size()];
    }

    bool isEmpty() {
        return !tail;
    }

    bool isFull() {
        return tail == data.size();
    }
};

REFERENCES:
LeetCode
Stack at GeeksforGeeks
Queue at GeeksforGeeks