Implementation of Stack in C++ (Introduction)
Introduction to Stack
A stack is another type of Data Structure,generally implemented using arrays. Generally, the implementation is LIFO i.e. Last in First out .They are used to convert prefix expression into postfix expression , balanced parenthesis problem, finding preorder of a tree.
Push Time Complexity | O(1) |
Pop Time Complexity | O(1) |
Display Time Complexity | O(n) |
Space Complexity | O(n) |
More about Stacks
- Stack can be defined as a Data Structure that serves as saving the data in a particular fashion.
- In linear data structures like an array and linked list a user is allowed to insert or delete any element to and from any location respectively.
- However, in a Stack, both, insertion and deletion, is permitted at one end only.
- It works on the LIFO (Last In – First Out) basis, i.e, the first element that is inserted in the stack would be the last to be deleted; or the last element to be inserted in the stack would be the first to be deleted.
Stack Operations
- Push: Adding a new item to the Stack Data Structure, in other words pushing new item to Stack DS. It is said to be in an overflow condition if the stack is full.
- Pop: Removing an item from the stack, i.e. popping an item out. If a stack is empty then it is said to be in an underflow condition
- Display: This basically display the whole stack.
Push Operation
Algorithm:
- Check whether stack is full or not.
- If the stack is full, it is not possible to add another element.
- Otherwise, create new node, store the data and change the pointer of top to the newly created node.
Pop Operation
Algorithm:
- In case of pop, note whether the stack is empty or not.
- It is not possible to remove element if the stack is empty.
- Else, store the top variable in temp and make top point to the next variable and delete temp.
C++ Program for Implementation of stack (array) using structure
Run
// C++ Program for Implmentation of stack (array) using structure #include <limits.h> #include <bits/stdc++.h> using namespace std; // A structure to represent a stack struct Stack { int top; int maxSize; int* array; }; struct Stack* create(int max) { struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack)); stack->maxSize = max; stack->top = -1; stack->array = (int*)malloc(stack->maxSize * sizeof(int)); //here above memory for array is being created // size would be 10*4 = 40 return stack; } // Checking with this function is stack is full or not // Will return true is stack is full else false //Stack is full when top is equal to the last index int isFull(struct Stack* stack) { if(stack->top == stack->maxSize - 1){ cout<<"Will not be able to push maxSize reached\n"; } // Since array starts from 0, and maxSize starts from 1 return stack->top == stack->maxSize - 1; } // By definition the Stack is empty when top is equal to -1 // Will return true if top is -1 int isEmpty(struct Stack* stack) { return stack->top == -1; } // Push function here, inserts value in stack and increments stack top by 1 void push(struct Stack* stack, int item) { if (isFull(stack)) return; stack->array[++stack->top] = item; cout<<"We have pushed "<<item <<" to stack\n"; } // Function to remove an item from stack. It decreases top by 1 int pop(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack->array[stack->top--]; } // Function to return the top from stack without removing it int peek(struct Stack* stack) { if (isEmpty(stack)) return INT_MIN; return stack->array[stack->top]; } int main() { struct Stack* stack = create(10); push(stack, 5); push(stack, 10); push(stack, 15); int flag=1; while(flag) { if(!isEmpty(stack)) cout<<"We have popped"<< pop(stack)<<" from stack\n"; else cout<<"Can't Pop stack must be empty\n"; flag=0; } return 0; }
We have pushed 5 to stack We have pushed 10 to stack We have pushed 15 to stack We have popped 15 from the stack
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Stacks
- Introduction to Stack in Data Structure
Click Here - Operations on a Stack
Click Here - Stack: Infix, Prefix and Postfix conversions
Click Here - Stack Representation in –
C | C++ | Java - Representation of a Stack as an Array. –
C | C++ | Java - Representation of a Stack as a Linked List. –
C | C++ | Java - Infix to Postfix Conversion –
C | C++ | Java - Infix to prefix conversion in –
C | C++ | Java - Postfix to Prefix Conversion in –
C | C++ | Java
Queues
- Queues in Data Structures (Introduction)
Click Here - Queues Program in C and implementation
Click Here - Implementation of Queues using Arrays | C Program
Click Here - Types of Queues in Data Structure
Click Here - Application of Queue Data Structure
Click Here - Insertion in Queues Program (Enqueuing) –
C | C++ | Java - Deletion (Removal) in Queues Program(Dequeuing) –
C | C++ | Java - Reverse a Queue –
C | C++ | Java - Queues using Linked Lists –
C | C++ | Java - Implement Queue using Stack –
C | C++ | Java - Implement Queue using two Stacks –
C | C++ | Java
Circular Queues
- Circular queue in Data Structure
Click Here - Applications of Circular Queues
Click Here - Circular queue in –
C | C++ | Java - Circular queue using Array –
C | C++ | Java - Circular Queue using Linked Lists –
C | C++ | Java
Priority Queue
Stacks
- Introduction to Stack in Data Structure
- Operations on a Stack
- Stack: Infix, Prefix and Postfix conversions
- Stack Representation in – C | C++ | Java
- Representation of a Stack as an Array. – C | C++ | Java
- Representation of a Stack as a Linked List. – C | C++ | Java
- Infix to Postfix Conversion – C | C++ | Java
- Infix to prefix conversion in – C | C++ | Java
- Postfix to Prefix Conversion in – C | C++ | Java
Queues
- Queues in Data Structures (Introduction)
- Queues Program in C and implementation
- Implementation of Queues using Arrays | C Program
- Types of Queues in Data Structure
- Application of Queue Data Structure
- Insertion in Queues Program (Enqueuing) – C | C++ | Java
- Deletion (Removal) in Queues Program(Dequeuing) – C | C++ | Java
- Reverse a Queue – C | C++ | Java
- Queues using Linked Lists – C | C++ | Java
- Implement Queue using Stack – C | C++ | Java
- Implement Queue using two Stacks – C | C++ | Java
Circular Queues
- Circular queue in Data Structure
- Applications of Circular Queues
- Circular queue in – C | C++ | Java
- Circular queue using Array – C | C++ | Java
- Circular Queue using Linked Lists – C | C++ | Java
Login/Signup to comment