Hello Ninjas! Stack is a fundamental Data Structure in computer science that allows storing and retrieving data in a Last-In-First-Out (LIFO) manner. It is a simple way to manage data in many programming languages, operating systems, and other computer applications. We will discuss stack operations in data structure such as arrays and linked lists and compare the pros and cons of each approach. Understanding stack operations is important for any programmer, as it is fundamental in many algorithms and data structures.

By the end, you will better understand how stacks work and how to use them in your programming projects.

Let's start with understanding a stack first.

What is Stack?

A stack is a particular Data structure that holds a group of elements sequentially or in linear order. It follows the Last-In-First-Out (LIFO) principle, meaning that the last element or item added to the stack is the first to be removed.

For example: Think of a stack of plates in a cafeteria. The plates are added to the top of the stack, and when someone wants to take a plate, they take the top one off the stack. This is precisely how a stack data structure works.

Stacks are used in many programming applications, including algorithms for parsing expressions, reversing a string, and implementing recursive functions. They can also be implemented using an array or linked list data structure.

Representation of the Stack

Here we will see the stack representation as an array.

Basic Operations on Stack

The following are the stack operations that are used in stack implementation:

push()

pop()

topElement() / peek()

isEmpty()

isFull()

size()

1. push()

It adds a new element to the top of the stack. It takes the element as its input and adds it to the top of the stack. This operation increases the size of the stack by one. push is a type of function that is basically used to insert an element in the stack, and this is the only method that can insert the element in the stack, which shows how important it is to learn while learning operations on the stack.

Here's the algorithm which will show us how the push() method works:

Checks If the stack has space to insert the element

If the stack is full, no element can be inserted, so it will return an error

Else if the stack has the capacity, the top will be increment by one and will be pointing to the next empty space in the data structure

Assign the given element to where the top is pointing in the data structure

Inserting is done and shows a success message

2. pop()

It removes the top element from the stack. It takes no input and removes the top element from the stack. This operation decreases the size of the stack by one. Pop is also a type of method/function that is basically used to remove/delete an element from the stack, and this is the only method that is used for the removal of an element from the stack.

Here's the algorithm which will show us how the pop() method works:

Checks the size of the stack, If the stack is empty. It will return false, as there are no elements to remove

If the stack is not empty, the element pointing by the top can be stored in a variable

Now 0 can be assigned to the element where the top is pointing

The popped value can be returned using the variable

3. topElement() / peek()

It returns the top element without removing it. This operation does not change the stack size and is useful when inspecting the top element without modifying the stack.

Here's an algorithm of peek() operation for a better understanding:

Checks the size of the element, If the stack is empty. An error will be returned as there are no elements to return

If the stack is not empty, the element pointing by the top will be stored to a variable

Return the variable having the top element

4. isEmpty()

The isEmpty Operation is used to check whether the stack is empty. isempty() returns a boolean value (true or false) depending on whether the stack is empty or not.

Here's an algorithm of the isEmpty() operation for a better understanding:

Checks the top variable, If the top is pointing to -1. Return true, as the top is not pointing to any element

Else if the top is greater than -1, return false as the top is pointing to some element

5. isFull()

The isFull operation is commonly utilized in implementations of a stack using a fixed-size array. This operation determines if the stack is at maximum capacity and cannot hold additional elements. isfull() returns a Boolean value (true or false) depending on whether the stack is full or not.

Here's an algorithm of the isFull() operation for a better understanding:

Checks the top variable, If the top is equal to the given size. Return true as the capacity of the data structure is full

Else if the top is lesser than the given size, return false

6. size()

The size() is used to calculate the size of the stack, which returns the size of the stack. The size is the capacity of the stack or the number of elements a stack can have at a single time. The size() method is used only when the implementation of stacks is done using arrays because there is a limited space while using arrays.

The variable ‘top' will be used to calculate the size of the stack. For example, If the top is pointing to 3 means there are 4 elements in the stack, so we can return top + 1, resulting in the size of 4 here.

Note: If you're using C++, then there is a size() method provided by Stack C++ STL. The stack.size() can be used without any implementation. Otherwise, you can implement it manually.

Here's an algorithm of the size() operation to implement it manually:

Create a variable ‘n’ with the value 0

If the ‘top’ is -1, then return ‘n’ with the value 0, as there are no elements in the stack

If the ‘top’ is greater than -1, assign ‘n’ with top + 1 and return n

Now let's see the stack implementation in an array and linked list using these stack operations.

Stack Implementation Using Arrays

In this approach, we declare an array of a fixed size and use two pointers: one to point to the top of the stack and the other to point to the bottom. Push and pop operations can be performed by adding or removing elements at the top of the stack. The isEmpty and isFull operations can be implemented by checking the size of the stack against the fixed array size.

Pros:

Arrays are a simple and straightforward data structure to implement

Arrays allow direct access to elements, which can be useful for certain operations

Array-based stacks have constant time complexity for accessing elements, pushing, and popping as long as the size of the array is known

Cons:

Array-based stacks have a fixed size, which can lead to overflow if the stack exceeds its capacity

Resizing an array-based stack can be expensive, requiring copying all elements to a new array

Removing an element from the middle of an array-based stack can be inefficient, requiring shifting all subsequent elements to fill the gap

Implementation:

C++

C++

#include <iostream> using namespace std;

class Stack { private: int top; int* arr;

public: Stack(int size) { top = -1; arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = 0; } }

void push(int val, int size) { if (isFull(size)) { cout << "Error: Stack is full." << endl; } else { top++; arr[top] = val; cout << val << " has been added to the stack." << endl; } }

int pop() { if (isEmpty()) { cout << "Error: Stack is empty." << endl; return 0; } else { int popValue = arr[top]; arr[top] = 0; top--; cout << popValue << " has been removed from the stack." << endl; return popValue; } }

int peek() { if (isEmpty()) { cout << "Error: Stack is empty." << endl; return 0; } else { int x = arr[top]; cout << " Top element of the stack is " << x << endl; return x; } } };

int main() { int size; cout << "Enter the size of the stack: "; cin >> size; Stack s(size);

int choice, val;

do { cout << "\nStack Menu:\n"; cout << "1. Push an element\n"; cout << "2. Pop an element\n"; cout << "3. Exit\n"; cout << "4. Peek at the top element\n"; cout << "Enter your choice: "; cin >> choice;

switch (choice) { case 1: cout << "Enter the element to push: "; cin >> val; s.push(val, size); break;

case 2: s.pop(); break;

case 3: cout << "Exiting..." << endl; exit(0); break;

Reason: The time complexity of the push, pop, and peek operations in this implementation of a stack is O(1) or constant time, which means the time taken to perform these operations does not depend on the size of the stack.

The overall time complexity of the code is O(N), where N is the size of the array. This is because the array is created using the new keyword, which allocates memory dynamically.

Space complexity: O(N)

Reason: The space complexity of this stack implementation is O(N), where n is the size of the stack. This is because the stack is implemented as an array of size N.

Stack Implementation Using Linked Lists

A stack can also be implemented using a linked list data structure. In this approach, each element in the stack is represented by a node in the linked list. The head of the linked list points to the top of the stack. Push and pop operations can be performed by adding or removing nodes at the head of the linked list, respectively. The isEmpty and isFull operations are unnecessary for this approach since a linked list can grow dynamically.

Note:

The sentence means that when using a linked list data structure, there is no need to check whether it is empty or full because it can dynamically adjust its size to accommodate new elements. This is in contrast to other data structures, such as arrays, where the size is fixed and must be pre-allocated, making it necessary to keep track of whether the structure is empty or full.

Pros:

Linked lists can grow or shrink dynamically, allowing for efficient memory use

Adding or removing elements from a linked list-based stack is generally faster and easier than resizing an array-based stack

Removing an element from the middle of a linked list-based stack is straightforward, as it only requires updating a few pointers

Cons:

Linked lists require additional memory overhead to store the pointers to the next element

Linked list-based stacks do not allow direct access to elements and require traversal of the list to access specific elements

Linked list-based stacks can be slower than array-based stacks for accessing elements, pushing, and popping due to the additional overhead of pointer manipulation

Implementation:

C++

C++

#include <iostream> using namespace std;

class Node { public: int data; Node* next; Node(int value) { data = value; next = NULL; } };

class LinkedListStack { public: Node* head; int size;

LinkedListStack() { head = NULL; size = 0; }

void push(int value) { Node* newNode = new Node(value); newNode->next = head; head = newNode; size++; }

int pop() { if(isEmpty()) { cout << "Stack is empty!" << endl; return -1; } int value = head->data; Node* temp = head; head = head->next; delete temp; size--; return value; }

int peek() { if(isEmpty()) { cout << "Stack is empty!" << endl; return -1; } return head->data; }

bool isEmpty() { return (head == NULL); }

int getSize() { return size; } };

int main() { LinkedListStack stack; int choice, value; while(true) {

cout << "Enter 1 to push \nEnter 2 to pop \nEnter 3 to peek \nEnter 4 to check if empty \nEnter 5 to get size \nEnter 6 to exit " << endl;

cin >> choice;

switch(choice) { case 1: cout << "Enter the value to push: " << endl; cin >> value; stack.push(value); break; case 2: cout << "Popped value: " << stack.pop() << endl; break; case 3: cout << "Top value: " << stack.peek() << endl; break; case 4: cout << "Stack is empty: " << stack.isEmpty() << endl; break; case 5: cout << "Size of stack: " << stack.getSize() << endl; break; case 6: exit(0); default: cout << "Invalid choice!" << endl; } } return 0; }

Output:

Complexity:

Time Complexity: O(1)

Reason: The time complexity of the push, pop, peek, and isEmpty operations in this stack implementation using a linked list is O(1) in the average and worst case. This is because these operations involve only constant-time operations on the head of the linked list.

Space Complexity: O(n)

Reason: Space complexity is O(n), where n is the number of elements in the stack. This is because each element in the stack requires a new Node object to be created and stored in memory. Also read - Data Structure MCQ

Frequently Asked Questions

What operations are possible on the stack?

There are very common operations, such as Accessing an element, Inserting an element, Deleting an element, and Updating an element, around which all other operations can be derived according to which algorithm a programmer is using stack.

What is a basic common operation on the stack?

There are two basic operations that are push and pop, which are used to insert an element in the stack and remove an element from the stack. In push and pop operations, operations such as isFull and isEmpty are also used.

Where is the stack data structure used?

Stack is used where the principle of Last In First Out and There are different use cases of the stack; some of them are checking parenthesis matching, conversion between infix, postfix, or prefix notations, and reversing the data.

Is stack a LIFO or FIFO?

Stack is a data structure that follows the Last-In, First-Out (LIFO) principle. This implies that the final item to be added to the stack is also the first to be taken out. The newest items are placed on top, while the oldest items are placed at the bottom, much like a stack of plates.

Conclusion

Understanding stack operations is crucial for aspiring computer scientists and software engineers. Mastery of stacks provides a strong foundation for learning more complex data structures and algorithms. Their ubiquitous presence in both academic exercises and real-world applications underscores their importance in the field of computer science.

Suppose you want to know more about stack and stack operations. In that case, you can refer to the following articles: