Implementing Stack in Data Structure: Basic Operations on Stack
Stack Data Structure and Implementation: An Overview
Optimizing productivity & time management is essential in today's fast-paced world. One of the best methods for increasing productivity and managing deadlines is "task stacking," or dividing large work into manageable pieces. This article will provide insights on how the stack in data structure works, Stack data structure and implementation examples, stack operations in data structure and why it's beneficial, as well as tips on how you can apply stacking principles to your own daily routine.
What is stack in data structure?
A stack is a fundamental data structure used in computer science and programming to store and organize data. It follows the Last-In-First-Out (LIFO) principle, which means that the last element inserted into the stack is the first one to be removed. One can visualize a stack as a pile of plates stacked vertically, where the topmost plate is the element at the top of the stack. The act of adding an element to the stack is known as "pushing," while removing an element is called "popping." Stacks are commonly used in various applications, such as in compilers, operating systems, and web browsers, to name a few. They are also an essential concept in understanding algorithm design and data structures. The stack is a straightforward yet powerful data structure that plays a vital role in computing, and understanding its concepts will help anyone become a better programmer.
Working of Stack
The Last-In-First-Out (LIFO) principle, which states that elements are added and withdrawn from the top of the stack, is a linear data structure. Push (to add an element) and Pop (to remove the top element) are the two main supported operations. Managing temporary data storage, parsing expressions, and tracking function calls are frequent tasks that entail the use of stacks.
LIFO principle in the stack
- The LIFO (Last-In-First-Out) principle is a fundamental concept in the implementation of a stack data structure.
- In a stack, the last item that is added to the structure is the first one to be removed.
- This principle is similar to the way that a stack of plates is arranged in a cafeteria or kitchen.
- The last plate that is placed on top of the stack is the first one to be taken off when someone wants to use it.
- In programming, the stack LIFO principle is implemented using a stack data structure.
- When a new element is added to the stack, it is placed on top of the existing elements.
- When an element needs to be removed from the stack, the topmost element is removed first.
- This process continues until the desired element is reached.
- The stack LIFO principle is important because it enables programmers to implement many useful algorithms, such as reversing the order of elements in a list, evaluating expressions in a postfix notation, and implementing backtracking algorithms.
Applications of Stack in data structure
There are some application of stack in data structure, those are
- Function Calls and Recursion: When a function is called, the computer stores information about the function call, including the return address and the values of any parameters, on the stack. When the function is finished, the information is retrieved from the stack and the program continues executing from the point where it left off.
- Expression Evaluation: A stack can be used to evaluate arithmetic expressions in which parentheses are used to group sub-expressions. The operands and operators are pushed onto the stack, and when a closing parenthesis is encountered, the sub-expression is evaluated using the operators and operands on the stack.
- Parsing: A stack in data structure is often used in parsing algorithms to keep track of the nesting of symbols such as parentheses, brackets, and braces.
- Undo/Redo Operations: Many applications, such as text editors and graphic design software, allow users to undo and redo previous operations. A stack can be used to store the state of the application before each operation, allowing the user to undo or redo the operation by popping or pushing elements from the stack.
- Backtracking: When searching for a solution to a problem, it may be necessary to backtrack and try a different path if the current path does not lead to a solution. A stack can be used to store information about the current path, allowing the algorithm to backtrack by popping elements from the stack.
Advantages of Stack
There are some advantages of stack in DSA, those are
- Easy to implement: The implementation of a stack is simple and straightforward, making it easy to use and understand.
- Efficient memory management: A stack uses a fixed amount of memory, which is allocated when the stack is created. This makes it efficient in terms of memory management.
- Quick access to the top element: A stack allows quick access to the top element, which is useful in many applications, such as parsing expressions and reversing a string.
- Recursive algorithms: A stack is often used in recursive algorithms, as it provides an efficient way to store and manage the state of the recursive calls.
- Undo/Redo operations: Stacks are often used in undo/redo operations, as they allow for a history of previous actions to be stored and easily accessed.
- Function call management: A stack is used in programming languages to manage function calls and the associated variables and parameters.
Disadvantages of stack
There are some advantages of stack in DSA, those are
- Limited functionality: Stacks have limited functionality and are only suitable for storing and retrieving elements in a specific order. It is not possible to access or modify elements in the middle of the stack without removing all the elements above it.
- Limited capacity: Stacks have a fixed size, and once the stack is full, it cannot store any additional elements unless some of the existing elements are removed.
- No random access: Unlike other data structures like arrays, stacks do not provide direct access to elements in the middle of the stack. The user has to remove all the elements above it to access it.
- Stack overflow: If a stack is not implemented correctly, it can lead to a stack overflow. This happens when the stack becomes full, and more elements are added, causing the program to crash.
- Implementation complexity: Implementing a stack requires more complex coding than other data structures like arrays and lists. This can make it difficult for inexperienced programmers to work with stacks.
- Memory management: Stacks can lead to memory management issues if elements are not removed properly. Unused elements can take up memory, causing memory leaks and slowing down the program.
Basic Operation of the stack
Insertion: push()
The push() operation is one of the fundamental operations in a stack data structure. When an element is added to a stack, it is added to the top of the stack. This process is called pushing an element onto the stack. The push() operation is used to insert an element onto the top of the stack. This considers as one of the stack operations.
Algorithm
1 − First Check if the stack is full.
2 − Then If the stack is full, produce an error and exit.
3 − If the stack is not full then increments top to point next empty space.
4 − After that add the data element to the stack location, where the top is pointing.
5 − Returns success.
Example
Python
MAXSIZE = 8
stack = [None] * MAXSIZE
top = -1
def isfull():
if top == MAXSIZE - 1:
return True
else:
return False
def push(data):
global top
if not isfull():
top = top + 1
stack[top] = data
else:
print("Could not insert data, Stack is full.")
# Main function
if __name__ == '__main__':
push(44)
push(10)
push(62)
push(123)
push(15)
print("Stack Elements:")
# print stack data
for i in range(0, 8):
print(stack[i], end=' ')
Java
public class StackExample {
static final int MAXSIZE = 8;
static int[] stack = new int[MAXSIZE];
static int top = -1;
public static boolean isFull() {
return top == MAXSIZE - 1;
}
public static void push(int data) {
if (!isFull()) {
top++;
stack[top] = data;
} else {
System.out.println("Could not insert data, Stack is full.");
}
}
public static void main(String[] args) {
push(44);
push(10);
push(62);
push(123);
push(15);
System.out.println("Stack Elements:");
// Print stack data
for (int i = 0; i <= top; i++) {
System.out.print(stack[i] + " ");
}
}
}
C++
#include <iostream>
class StackExample {
public:
static const int MAXSIZE = 8;
static int stack[MAXSIZE];
static int top;
static bool isFull() {
return top == MAXSIZE - 1;
}
static void push(int data) {
if (!isFull()) {
top++;
stack[top] = data;
} else {
std::cout << "Could not insert data, Stack is full." << std::endl;
}
}
};
int StackExample::stack[StackExample::MAXSIZE];
int StackExample::top = -1;
int main() {
StackExample::push(44);
StackExample::push(10);
StackExample::push(62);
StackExample::push(123);
StackExample::push(15);
std::cout << "Stack Elements:" << std::endl;
// Print stack data
for (int i = 0; i <= StackExample::top; i++) {
std::cout << StackExample::stack[i] << " ";
}
return 0;
}
Explanation
The stack data structure defined in this example has a maximum capacity of 8. To add components to the stack, it uses a push operation, and before inserting data, it determines whether the stack is full. Five elements—44, 10, 62, 123, and 15—are pushed into the stack in the main function, and the stack's contents are then printed.
Output
Stack Elements:
44 10 62 123 15
Deletion: pop()
The pop() operation in a stack is used to remove the top element of the stack and return its value. The pop() operation modifies the state of the stack by removing the topmost element, which is also known as the head, top, or front of the stack.
Algorithm
1 − First check if the stack is empty.
2 − Then If the stack is empty, produce an error and exit.
3 − After that If the stack is not empty, access the data element at which the top is pointing.
4 − Then decreases the value of the top by 1.
5 − Lastly returns success.
Example
Python
class Stack:
def __init__(self):
self.stack = []
def __str__(self):
return str(self.stack)
def push(self, data):
if data not in self.stack:
self.stack.append(data)
return True
else:
return False
def remove(self):
if len(self.stack) <= 0:
return ("No element in the Stack")
else:
return self.stack.pop()
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)
print("----Deletion operation in stack----")
p = stk.remove()
print("The popped element is: " + str(p))
print("Updated Stack:")
print(stk)
Java
import java.util.ArrayList;
import java.util.List;
class Stack {
private List<Integer> stack;
public Stack() {
this.stack = new ArrayList<>();
}
@Override
public String toString() {
return stack.toString();
}
public boolean push(int data) {
if (!stack.contains(data)) {
stack.add(data);
return true;
} else {
return false;
}
}
public String remove() {
if (stack.isEmpty()) {
return "No element in the Stack";
} else {
int poppedElement = stack.remove(stack.size() - 1);
return "The popped element is: " + poppedElement;
}
}
}
public class Main {
public static void main(String[] args) {
Stack stk = new Stack();
stk.push(1);
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
System.out.println("Stack Elements:");
System.out.println(stk);
System.out.println("----Deletion operation in stack----");
String p = stk.remove();
System.out.println(p);
System.out.println("Updated Stack:");
System.out.println(stk);
}
}
C++
#include <iostream>
#include <vector>
class Stack {
private:
std::vector<int> stack;
public:
Stack() {
// Constructor
}
bool push(int data) {
if (std::find(stack.begin(), stack.end(), data) == stack.end()) {
stack.push_back(data);
return true;
} else {
return false;
}
}
std::string remove() {
if (stack.empty()) {
return "No element in the Stack";
} else {
int poppedElement = stack.back();
stack.pop_back();
return "The popped element is: " + std::to_string(poppedElement);
}
}
friend std::ostream& operator<<(std::ostream& os, const Stack& obj) {
os << "[";
for (size_t i = 0; i < obj.stack.size(); ++i) {
os << obj.stack[i];
if (i < obj.stack.size() - 1) {
os << ", ";
}
}
os << "]";
return os;
}
};
int main() {
Stack stk;
stk.push(1);
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
std::cout << "Stack Elements:" << std::endl;
std::cout << stk << std::endl;
std::cout << "----Deletion operation in stack----" << std::endl;
std::string p = stk.remove();
std::cout << p << std::endl;
std::cout << "Updated Stack:" << std::endl;
std::cout << stk << std::endl;
return 0;
}
Explanation
The 'Stack' class in this example is a representation of a stack data structure with methods for adding and removing members as well as for showing the contents of the stack. In the main function, an instance of the 'Stack' class is created, five elements (1, 2, 3, 4, and 5) are added to the stack, its contents are displayed, an element is removed from the stack, and the updated stack is then displayed.
Output
Stack Elements:
[1, 2, 3, 4, 5]
----Deletion operation in stack----
The popped element is: 5
Updated Stack:
[1, 2, 3, 4]
peek()
The peek() operation returns the value of the element at the top of the stack, without modifying the stack itself. This can be useful when you need to check the value of the top element before deciding whether to remove it or not. This is considered as one of the stack operations.
Algorithm
1. START
2. Then return the element at the top of the stack
3. END
Example
Python
class Stack:
def __init__(self):
self.stack = []
def __str__(self):
return str(self.stack)
def push(self, data):
if data not in self.stack:
self.stack.append(data)
return True
else:
return False
# Use peek to look at the top of the stack
def peek(self):
return self.stack[-1]
stk = Stack()
stk.push(1)
stk.push(2)
stk.push(3)
stk.push(4)
stk.push(5)
print("Stack Elements:")
print(stk)
print("topmost element: ",stk.peek())
Java
import java.util.ArrayList;
import java.util.List;
class Stack {
private List<Integer> stack;
public Stack() {
this.stack = new ArrayList<>();
}
@Override
public String toString() {
return stack.toString();
}
public boolean push(int data) {
if (!stack.contains(data)) {
stack.add(data);
return true;
} else {
return false;
}
}
public int peek() {
return stack.get(stack.size() - 1);
}
}
public class Main {
public static void main(String[] args) {
Stack stk = new Stack();
stk.push(1);
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
System.out.println("Stack Elements:");
System.out.println(stk);
System.out.println("topmost element: " + stk.peek());
}
}
C++
#include <iostream>
#include <vector>
class Stack {
private:
std::vector<int> stack;
public:
Stack() {
// Constructor to initialize an empty stack
}
// Function to push an element onto the stack
bool push(int data) {
// Check if data is not already in the stack
if (std::find(stack.begin(), stack.end(), data) == stack.end()) {
stack.push_back(data);
return true;
} else {
return false;
}
}
// Function to peek at the top of the stack
int peek() {
if (!stack.empty()) {
return stack.back();
} else {
// Handle the case where the stack is empty
throw std::runtime_error("Stack is empty.");
}
}
// Function to display the elements of the stack
void display() {
for (int element : stack) {
std::cout << element << " ";
}
std::cout << std::endl;
}
};
int main() {
Stack stk;
stk.push(1);
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
std::cout << "Stack Elements:" << std::endl;
stk.display();
try {
std::cout << "Topmost element: " << stk.peek() << std::endl;
} catch (const std::runtime_error& e) {
std::cerr << e.what() << std::endl;
}
return 0;
}
Explanation
The class Stack for a stack data structure is defined in this example. It enables adding components to the stack, showing the contents of the stack, and looking at the top element of the stack. In the main function, a stack is created, five components are pushed onto it, the contents of the stack are displayed, and the top element of the stack is then retrieved and printed using the peek method.
Output
Stack Elements:
[1, 2, 3, 4, 5]
topmost element: 5
isFull()
The isFull() operation in a stack data structure is used to determine if the stack is full or not. A stack is said to be full if it has reached its maximum capacity and there is no more space to add new elements to the stack. This is one of the stack operations.
Algorithm
1. START
2. Then if the size of the stack is equal to the top position of the stack, the stack is full. Return 1.
3. Otherwise, return 0.
4. END
Example
import java.io.*;
public class StackExample {
private int arr[];
private int top;
private int capacity;
StackExample(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
public boolean isEmpty() {
return top == -1;
}
public boolean isFull() {
return top == capacity - 1;
}
public void push(int key) {
if (isFull()) {
System.out.println("Stack is Full\n");
return;
}
arr[++top] = key;
}
public static void main (String[] args) {
StackExample stk = new StackExample(5);
stk.push(1); // inserting 1 in the stack
stk.push(2);
stk.push(3);
stk.push(4);
stk.push(5);
System.out.println("Stack Full? " + stk.isFull());
}
#include <iostream>
int MAXSIZE = 8;
int stack[8];
int top = -1;
/* Check if the stack is full */
int isfull(){
if(top == MAXSIZE)
return 1;
else
return 0;
}
/* Main function */
int main(){
printf("Stack full: %s\n" , isfull()?"true":"false");
return 0;
}
Python
MAXSIZE = 8
stack = [None] * MAXSIZE
top = -1
# Check if the stack is full
def isfull():
if top == MAXSIZE - 1:
return True
else:
return False
# Main function
if __name__ == '__main__':
print("Stack full: {}".format("true" if isfull() else "false"))
Java
public class StackExample {
static int MAXSIZE = 8;
static Object[] stack = new Object[MAXSIZE];
static int top = -1;
// Check if the stack is full
static boolean isFull() {
return top == MAXSIZE - 1;
}
public static void main(String[] args) {
System.out.println("Stack full: " + (isFull() ? "true" : "false"));
}
}
C++
#include <iostream>
class StackExample {
public:
static const int MAXSIZE = 8;
static int top;
static bool isFull() {
return top == MAXSIZE - 1;
}
};
int StackExample::top = -1;
int main() {
std::cout << "Stack full: " << (StackExample::isFull() ? "true" : "false") << std::endl;
return 0;
}
Explanation
In this example, a stack with a maximum size of 8 is created, and the function isfull() is defined to determine whether the stack is full. When the stack is full or empty, the main function prints "Stack full: true" if the stack is full and "Stack full: false" if it isn't.
Output
Stack empty? false
Stack full: false
isEmpty()- The isEmpty() operation is a method that is commonly associated with the stack data structure. This operation is used to check if the stack is empty or not. In general, the isEmpty() method returns true if the stack is empty (contains no elements), and false otherwise. This is one of the stack operations.
Algorithm
1. START
2. If the top value is -1, the stack is empty. Return 1.
3. Otherwise, return 0.
4. END
Example
Python
MAXSIZE = 8
stack = [0] * MAXSIZE
top = -1
# Check if the stack is empty
def isempty():
if top == -1:
return True
else:
return False
# Main function
if __name__ == "__main__":
print(f"Stack empty: {isempty()}")
Java
public class StackExample {
static final int MAXSIZE = 8;
static int[] stack = new int[MAXSIZE];
static int top = -1;
// Check if the stack is empty
static boolean isEmpty() {
return top == -1;
}
public static void main(String[] args) {
System.out.println("Stack empty: " + isEmpty());
}
}
C++
#include <iostream>
class StackExample {
public:
static const int MAXSIZE = 8;
static int stack[MAXSIZE];
static int top;
// Check if the stack is empty
static bool isEmpty() {
return top == -1;
}
};
// Initializing the top of the stack
int StackExample::top = -1;
int main() {
std::cout << "Stack empty: " << StackExample::isEmpty() << std::endl;
return 0;
}
Explanation
In this example, a stack with a maximum size of 8 is created, and the method "isempty()" is defined to determine whether the stack is empty. The main function checks to see if the stack is empty or not, printing "Stack empty: True" if it is and "Stack empty: False" if it is not.
Output
Stack empty: True
Stack Time Complexity
In computer science, the time complexity of an algorithm is a measure of the amount of time taken by an algorithm to complete as a function of the input size. The time complexity of an algorithm is often expressed using big O notation, which gives an upper bound on the worst-case time complexity of the algorithm. The time complexity of a stack depends on the specific operation being performed. Here are the time complexities of some common stack operations:
- Push: O(1) - This operation adds an element to the top of the stack and takes constant time.
- Pop: O(1) - This operation removes and returns the top element of the stack and takes constant time.
- Peek: O(1) - This operation returns the top element of the stack without removing it and takes constant time.
- Search: O(n) - This operation searches for an element in the stack from the top and takes linear time, where n is the number of elements in the stack.
- Size: O(1) - This operation returns the number of elements in the stack and takes constant time.
In summary, most stack operations have a time complexity of O(1), except for the search operation, which has a time complexity of O(n).
Implementation of Stack in different languages
- Implementing stacks in different programming languages is a fascinating topic that highlights the unique features of each language.
- Whether it's Python, Java, or C++, each language has its own syntax and approach to building a stack data structure.
- As developers, we are continuously looking for the most efficient and effective way to solve problems, making it essential to understand the nuances of each language when it comes to stack implementation.
- By diving into the differences between these programming languages, we can better understand how to tailor our solution to fit the problem at hand, ultimately leading to more robust and optimized code.
FAQs
1. What is the implementation of a data structure?
A data structure is "implemented" when it is produced and used in a programming language in a certain way, generally through the use of variables, arrays, and algorithms.
2. How to implement stack data structure using an array?
You can create an array to contain the components of a stack data structure and use a variable to track the top of the stack to implement it.
3. What are the 6 applications of stack?
Expression evaluation, function call management (call stack), backtracking algorithms, parsing (for example, in compilers), undo/redo capability, and managing history in web browsers are six typical uses for a stack data structure.
4. What is stack and its types?
Linear data structures that adhere to the Last-In-First-Out (LIFO) concept include stacks. The ordinary stack and the deque (double-ended queue) are the two major forms of stacks.
5. What is the principle of stack?
The Last-In-First-Out (LIFO) principle underlies the stacking system, according to which the last item added to the stack is also the first one to be taken away.
Summary
Summing up this article by stating that, stack is a great tool when it comes to managing projects and organizing data. Stack is easy to use, user-friendly, and secure. With the help of stack, you can keep your work organized and create a truly efficient workflow for your business. More than this, stack offers the ability to customize your workspace so that each project or task has its own special place within the app. This makes it easier than ever to store and track information with ease. With all these amazing benefits of using stack, there’s no reason not to give it a try. Try Stack today and take back control of your projects you won’t regret it!
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
