Stack: deep dive

Stack

• A stack is an ordered list in which insertion and deletion are done at one end, called top.
• The last element inserted is the first one to be deleted.
• Hence, it is called the Last in First out(LIFO) or First in Last out (FILO) list.

Stack ADT

Main stack operations

• Push (int data): Inserts data onto stack.
• int Pop(): Removes and returns the last inserted element from the stack.

Auxiliary stack operations

• int Top(): Returns the last inserted element without removing it.
• int Size(): Returns the number of elements stored in the stack.
• int IsEmptyStack(): Indicates whether any elements are stored in the stack or not.
• int IsFullStack(): Indicates whether the stack is full or not.

Implementing Stack using Array

#include<bits/stdc++.h>
using namespace std;

class Stack {
    int size = 5;
    int *items = new int[size];
    int top = 0;

    public:
    void push(int item) {
        if(top == size) cout << "StackOverFlowError" << endl;
        else items[top++] = item;
    }

    int pop() {
        if(top == 0) {
            cout << "StackUnderFlowError" << endl;
            return 0;
            cout <<"HI" << endl;
        }
            cout <<"2HI" << endl;
        return items[--top];
    }

    int length() {
        return top;
    }

    void print() {
        for(int i = 0; i < top; i++)
            cout << *(items + i) << " ";
    }

    int top() {
        return items[top-1];
    }

    bool isEmpty() {
        return top == 0;
    }

    bool isFull() {
        return top == size;
    }

};


int main(int argc, char const *argv[]) {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << "Size : " << s.length() << endl;
    return 0;
}

Performance

Let n be the number of elements in the stack. The complexities of stack operations with this representation can be given as:

Space Complexity (for n push operations): O(n)
Time Complexity of Push() : O(1)
Time Complexity of Pop() : O(1)
Time Complexity of Size() : O(1)
Time Complexity of IsEmpty(): O(1)
Time Complexity of IsFull : O(1)

Limitations

The maximum size of the stack must first be defined and it cannot be changed. Trying to push a new element into a full stack causes an implementation-specific exception.

Stacks: Problems

1. Discuss how stacks can be used for checking balancing of symbols.
2. Discuss infix to postfix conversion algorithm using stack.
3. Discuss postfix evaluation using stacks?
4. Can we evaluate the infix expression with stacks in one pass?
5. How to design a stack such that GetMinimum() should be O(1)?
6. For Problem-5 is it possible to improve the space complexity?