What Is Stack Implementation in Data Structure?

//

Larry Thompson

What Is Stack Implementation in Data Structure?

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. It means that the last element added to the stack will be the first one to be removed. Stack implementation in data structure involves using various operations to manipulate and manage the elements in a stack.

Operations on a Stack

A stack typically supports three main operations:

  • Push: This operation adds an element to the top of the stack.
  • Pop: This operation removes and returns the element from the top of the stack.
  • Peek: This operation returns the element at the top of the stack without removing it.

In addition to these core operations, some other useful operations on a stack include:

  • isEmpty: This operation checks if the stack is empty or not.
  • isFull: This operation checks if the stack is full or not (applicable for fixed-size stacks).

Stack Implementation Using Arrays

The simplest way to implement a stack is by using an array. Here’s an example of how it can be done in C++:

#include <iostream>
using namespace std;

const int MAX_SIZE = 100;
int stack[MAX_SIZE];
int top = -1;

void push(int item) {
    if (top == MAX_SIZE - 1) {
        cout << "Stack Overflow!" << endl;
        return;
    }

    stack[++top] = item;
}

void pop() {
    if (top == -1) {
        cout << "Stack Underflow!" << endl;
        return;
    }

    int item = stack[top--];
    cout << "Popped element: " << item << endl;
}

int peek() {
    if (top == -1) {
        cout << "Stack is empty!" << endl;
        return -1;
    }

    return stack[top];
}

bool isEmpty() {
    return top == -1;
}

bool isFull() {
    return top == MAX_SIZE - 1;
}

int main() {
    push(10);
    push(20);
    push(30);

    cout << "Top element: " << peek() << endl;

    pop();
    
    cout << "Is stack empty? " << (isEmpty() ? "Yes" : "No") << endl;

    return 0;
}

In this implementation, we use the array 'stack' to store the elements and the variable 'top' to keep track of the index of the top element. The push operation increases 'top' by 1 and adds the element at that position. The pop operation decreases 'top' by 1 and returns the element at the previous top position.

Stack Implementation Using Linked List

Another way to implement a stack is by using a linked list. In this approach, each element in the stack is represented by a node in the linked list. Here's an example of how it can be done in Java:

public class Stack<T> {
    
    private Node<T> top;

    private static class Node<T> {
        T data;
        Node<T> next;

        public Node(T data) {
            this.data = data;
            next = null;
        }
    }

    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        if (top == null) {
            top = newNode;
        } else {
            newNode.next = top;
            top = newNode;
        }
    }

    public T pop() {
        if (top == null) {
            System.out.println("Stack Underflow!");
            return null;
        }

        T item = top.data;
        top = top.next;
        return item;
    }

    public T peek() {
        if (top == null) {
            System.println("Stack is empty!");
            return null;
        }

        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }
  
  public static void main(String[] args) {
      Stack<Integer> stack = new Stack<>();
      
      stack.push(10);
      stack.push(20);
      stack.push(30);

      System.println("Top element: " + stack.peek());

      stack.pop();
      
      System.println("Is stack empty? " + (stack.isEmpty() ? "Yes" : "No"));
  }
}

In this implementation, we define a generic class 'Stack' with a nested class 'Node' representing each element in the linked list. The push operation creates a new node and makes it the new 'top' by updating the 'next' reference. The pop operation removes the current 'top' node and updates the 'top' reference to its next node.

Conclusion

A stack is a fundamental data structure in computer science that provides an efficient way to manage and manipulate data. Understanding how to implement and utilize stacks using arrays or linked lists is crucial for developing efficient algorithms and solving various problems.

Discord Server - Web Server - Private Server - DNS Server - Object-Oriented Programming - Scripting - Data Types - Data Structures

Privacy Policy