A stack is a linear data structure that holds a collection of elements. It has two primary operations: Push (adds an element to the collection) and Pop (removes the most recently added element from the collection). By following this order it is a LIFO (last in, first out) collection and can be thought of as a stack of pancakes.
Basic Operations
push() - adds an item to the stack.
pop() - removes an item from the top of the stack.
peek() - returns the value of the top element without removing it.
isEmpty() - check if the stack is empty.
Implementations
A stack implemented using an array
classStack:
def __init__(self, data):
self.stack = []
if data:
self.stack.append(data)
defadd(self, data):
self.stack.append(data)
defpop(self):
return self.stack.pop()
defpeek(self):
if self.isEmpty():
raiseValueError("The stack is empty")
return self.stack[-1]
defisEmpty(self):
return len(self.stack) ==0
intbinarySearch(vector nums, int x) {
int left =0;
int right = nums.size();
while (left <= right) {
int mid = left + (right - left) /2;
if (nums[mid] == x)
return mid;
if (nums[mid] < x)
left = mid +1;
else right = mid -1;
}
return-1;
}
publicclassBinarySearch{publicstaticintsearch(int[] array,int target){int left =0;int right = array.length-1;while(left <= right){int mid =(left + right)/2;if(array[mid]== target){return mid;}elseif(array[mid]> target){ right = mid -1;}else{ left = mid +1;}}return-1;}}
Time Complexity
For the list/array/vector implementation of the stack the average time complexity of the push and pop operations are O(1). However, if the array needs to be resized the complexity will become O(n) where n is the number of elements in the stack.
In the linked list implementation the time complexity of the push and pop operations are O(1) (constant time).
Applications of Stack Data Structure
A stack is a simple but very powerful data structure and has many uses. Some of those uses are:
Arithmetic Expression Evaluation, a stack is very effective in evaluating arithmetic expressions.
They can also be used for Backtracking. Backtracking is an algorithmic technique that is used to search all possible solutions for a problem.
Tracking function calls, whenever a call is made from one function to another the address of the calling function gets stored on the stack.