-> Stack is a collection of elements which follow discipline LIFO (Last -in First -Out) for ex:- # if car is parked in a lane # Balls in a cane
ADT (Abstarct Data Type) of STACK -> It contain data representation and operations in the stack ADT stack Data:-
1. Space for storing elements 2. Top pointer
operations:- 1. Push(); 2. Pop(); 3. Peek(index); 4. StackTop(); 5. isEmpty(); 6. isFull();
-> We can use Array and Linked List for implementation of stack; -> Insertion is always from end , so time complexity of insertion is 0(1) ----Stack using Array----
Structure of Stack :- Struct Stack{ int size; int Top; int *s; }
or class Stack{ public: int size; int Top; int *s; }
In Main:- int main() { Stack st; st.data = 5; st.s = new int(st.data); st.top = -1; return 0; }
Empty Conditions:- If(Top == -1); Full Conditions:- If(Top == Size-1);
operations:-
PUSH();
void push(Stack *st, int n) { if (st->top == st->size-1){ cout<<"Stack is Full"; } else{ st->top++; st->s[st->top] = n; } }
Pop
void pop(Stack *st) { int x; if (st->top == -1) { cout<<"Stack is Empty"; } else{ st->top--; } }
Peek
void peek(Stack st, int pos) { if (st.top — pos + 1 <0 ) cout << "Position Invalid"; else cout<<st.s[st.top — pos + 1]; }