The stack is always a favourite part of the interviewer in any programming interview. Stack has an important place in Linear data structure and used to implement complex solutions. Stack Interview Questions are the best collection of concepts and questions asked in the data structure Interview.
Stacks are important part of data structures and comes under abstract data structures. They allow access to only one data item at a time and that is the last item inserted.
Since internally other data structures are used by stack, they are abstract data type. Stacks use array. Stacks are useful to perform many operations in other data types.
Few examples of Stack implementation:
- Stack is used by Binary trees in traversing of nodes.
- Stack is used by Graphs in searching the vertices of the graph.
- Stacks can be used to process tasks, messages etc.
To crack Stack interview and to give perfect answers to stack interview questions and answers, It is very important to have basic concepts of stack and other data types like array.
Here we have given the basic concept of stack and implementation of stack using C language.
While keeping in mind the practical implementation and complexity we have given plenty of examples of stack implementation and operations using C Programming.
What is a Stack?
A stack is a linear data structure and represented a list of the element in which an element may be inserted or deleted only from one end, called the top of the stack.
Elements in the stack are arranged in a linear fashion. Unlike an array, we can not access an element randomly.
According to the behaviour of Stack, we can have two important operations
- PUSH and
Insertion of an element in the stack from the top is called PUSH and removal of an element from the stack is called POP.
We can only access the last element inserted in a Stack. Hence We can say an Item can either Inserted or Deleted At only one end of the stack and that end is the TOP. This is why We called it a LIFO – Last In First Out.
Main Features of Stack
- The stack is a Linear type data structure
- Allow only the last element to access
- Random access of element is not allowed
- The stack is an ordered list of similar data type
- When a stack is completely full it is called Overflow Stack and If completely empty it is called Underflow Stack.
- A stack is a recursive data structure. Here is a structural definition of a Stack:
- a stack is either empty or
- it consisted of a top and the rest which is a stack;
Application of Stack
- We can use stack reverse a string. You push a given string to stack – character by character – and then POP character from the stack.
- Undo Operations in the text editor is an application of stack PUSH and POP.
Basic Operations on Stack
Stack allowed the following operation with data stored it with:
- Push operation
- Pop operation
- Peek operation
Algorithm for PUSH Operation in Stack
Consider MAX represents the last position of the element to be inserted and TOP is the current position. TOP initially points to 0.
Algorithm POP Operation in Stack
The function will return the popped value from the stack
Implementation of Stack
The stack can be implemented as
- Using Array
- Using a Linked list
Array and linked list both are used to implement a stack. Both have some advantages and disadvantages associated with them. Here are some relative comparisons between these two.
- The array is a collection of similar data types elements while the linked list is a collection of elements of the same type connected to each other by pointers.
- Array consumes memory in a contiguous manner. Also, the size of array is decided at compile time. This kind of memory allocation is called Static memory allocation. But in case of linked list memory allocated at runtime. The size of the list can be increased or decreased at runtime. This kind of memory allocation is called dynamic memory allocation.
- The size of the array is fixed. Memory allocated as soon as the array is declared. In the case of a linked list, size can grow or shrink.
- In array, due to memory allocation in contiguous in manner, insertion and deletion take more time in comparison to linked list.
- Accessing an element in an array is faster. Also, any element of an array can be easily accessed by using indexing. This is not in the case of a linked list. You have to transverse from the starting point to access any element.
Implement Stack using an Array
A working Example of Implementation of Stack using Array
Implement Stack using a Linked list
A working Example of Implementation of Stack using Linked List