STACK
STACK
================================================================================
- Stack is a linear data structure that follows a particular order in which the operations are performed.
- The order may be LIFO(Last In First Out) or FILO(First In Last Out).
- Basic Operation on Stack:
- push() : To insert an element into the stack
- pop() : To remove an element from the stack
- top() : Returns the top element of the stack.
- isEmpty() : Returns true if stack is empty else false.
- isFull() : Returns true if stack is full else false.
- push():
- Adds an item to the stack.
- If stack is full, then it said to be an "Overflow Condition".
- Time Complexity: 0(1)
- Only a new node is created and the pointer of the last node is updated. This includes only memory allocation operations. Hence it can be said that insertion is done in constant time.
- Algorithm:
- begin
- if stack is full
- return
- endif
- else
- increment top
- stack[top] = assign value
- end else
- end
- Flow Chart:
- pop():
- Removes an item from stack.
- The items are removed in reversed order in which they have pushed.
- If the stack is empty, then it said be an "Underflow Condition".
- Time Complexity: 0(1)
- Only the first node is deleted and the top pointer is updated. This is a constant time operation.
- Algorithm:
- begin
- if stack is empty
- return
- endif
- else
- store value of stack[top]
- decrement top
- return value
- end else
- end
- Flow chart:
- Removes an item from stack.
- The items are removed in reversed order in which they have pushed.
- If the stack is empty, then it said be an "Underflow Condition".
- Time Complexity: 0(1)
- Only the first node is deleted and the top pointer is updated. This is a constant time operation.
- Algorithm:
- begin
- if stack is empty
- return
- endif
- else
- store value of stack[top]
- decrement top
- return value
- end else
- end
- begin
- if stack is empty
- return
- endif
- else
- store value of stack[top]
- decrement top
- return value
- end else
- end
- Flow chart:
- top():
- Returns top element of the stack.
- Time Complexity: 0(1)
- In linked list implementation also a single memory address is accessed. It takes constant time.
- Algorithm:
- begin
- return stack[top]
- end
- Flow Chart:
- Returns top element of the stack.
- Time Complexity: 0(1)
- In linked list implementation also a single memory address is accessed. It takes constant time.
- Algorithm:
- begin
- return stack[top]
- end
- begin
- return stack[top]
- end
- Flow Chart:
- isEmpty():
- Returns true if the stack is empty, else false
- Time Complexity: 0(1)
- It only performs an arithmetic operation to check if the stack is empty or not.
- Algorithm:
- begin
- if top == -1
- return true
- else
- return false
- end
- Flow Chart:
- isEmpty():
- Returns true if the stack is empty, else false
- Time Complexity: 0(1)
- It only performs an arithmetic operation to check if the stack is empty or not.
- Algorithm:
- begin
- if top == -1
- return true
- else
- return false
- end
- Flow Chart:
- Returns true if the stack is empty, else false
- Time Complexity: 0(1)
- It only performs an arithmetic operation to check if the stack is empty or not.
- Algorithm:
- begin
- if top == -1
- return true
- else
- return false
- end
- begin
- if top == -1
- return true
- else
- return false
- end
- Flow Chart:
- isFull():
- Returns true if the stack is full, else false
- Returns true if the stack is full, else false
- Algorithm:
- begin
- if top == sizeof(stack) -1
- return true
- else
- return false
- end
- begin
- if top == sizeof(stack) -1
- return true
- else
- return false
- end
- Flow Chart:
- Write a menu driven code to demonstrate all the stack operations .
- Please find git repository link for the solution. Link
Comments
Post a Comment