Stack Program 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, also used for FILO, i.e. First in Last out
Stacks in C
- 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.
- A Stack 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.
- Pop: Removing an item from the stack, i.e. popping an item out.
- Peek: This basically returns the topmost item in the stack, in other words, peek that what is the topmost item.
- IsEmpty: This returns True If the stack is empty else returns False
Representation of stack.
Stack as a data structure can be represented in two ways.
- Stack as an Array.
- Stack as a struct
- Stack as a Linked List.
Operations on a Stack
There are a number of operations we can perform on a stack as per our need which are as follows:
- Push().
- Pop().
- Top/Peak().
- isEmpty().
1. Push()
- When we require to add an element to the stack we perform Push() operation.
- Push() operation is synonymous of insertion in a data structure.
2. Pop()
- When we require to remove an element to the stack we perform Pop() operation.
- Pop() operation is synonymous of deletion in a data structure.
3. Top()
- This operation returns the top most or peak element of the stack.
- The value of top changes with each push() or pop() operation.
4. isEmpty()
- This operation returns true if the stack is found to be empty.
- Empty stack symbolizes that top = -1.
How stack works?
- Top: An integer variable Top is used, to keep track of topmost element in the stack
- When we initialise the stack, there is no element in a stack so, Top value is initialised to Top = -1
- The value is -1 as if use an array to implement stack if there is 1 element the location would be a[0], thus, for no element we use – 1.
- Push: on pushing new element the Top value increments by 1, top++
- Pop: on popping a new element the top value decrements by 1, top–
- Before pushing we check if the stack is full or not
- Before popping we check if the stack is empty or not
Code for Stack in C Program (using structure)
// C Program for Implmentation of stack (array) using structure #include <limits.h> #include <stdio.h> #include <stdlib.h> // 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) { printf ("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; printf ("We have pushed %d to stack\n", item); } // 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)) printf ("We have popped %d from stack\n", pop (stack)); else printf ("Can't Pop stack must be empty\n"); flag = 0; } return 0; }
Output :
We have pushed 5 to stack We have pushed 10 to stack We have pushed 15 to stack We have popped 15 from stack
Understanding the concept of Stack
Let us understand the concept of Stack. As we have learned about stack above, it stores the data in a particular fashion where the element can only be inserted or deleted at one end only.
Let us consider a stack of books as shown in the image.
- This pile of books would have been formed by placing one book on the other like first the blue book and then on top of it the red book then on top of the red book came the yellow book and so on.
- The functioning of the Stack is similar to this.
- If we look at the stack in the image.
- First the element 42 would have been added to an empty stack.
- Then on the top of it, the second element 18 would be added.
- On the top of 18, the next element 12 would have been added and so on.
- Similarly, if we pick out the books out of the stack we will have to begin from top. For instance if we want to remove the yellow book we will have to first remove the pink book, then the blue book and then the green book and then we will finally be able to remove the yellow book.
- Same happens in the case of the stack. To delete the element 12 , we will have to first remove 22 then 34 and then we can delete the element 12.
- With this example we can be certain that a stack structure works on a LIFO basis, i.e , the last element to be inserted would be deleted first.
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
- 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
Priority Queue
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
Login/Signup to comment