AlgoDocs

Stack Implementation Using Linked List

Implementing stack operations using a linked list

Implementation

Push Operation

  • Create a new node with the given data.
  • Set the next pointer of the new node to the current top.
  • Update top to point to the new node.
    • Increment len by 1.

Pop Operation

  • Check if top is NULL (stack is empty).
  • If true, print "Stack is empty" and exit.

Otherwise:

  • Store the current top node in a temporary variable (del).

  • Update top to point to top->next (the next node).

  • Free the memory of the node stored in del.

  • Decrement len by 1.

Peek Operation

  • Check if the stack is empty (top == NULL).

  • If true, print "Stack is empty" and return -1.

  • Otherwise, return the data value of the top node.

IsEmpty Operation

  • Check if top == NULL.

  • Return true if the stack is empty, otherwise false.

Size Operation

  • Return the value of len.

Coding Implementation

#include <iostream>
using namespace std;

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

class Stack {
private:
    Node* top;
    int len;
public:
    Stack() {
        top = NULL;
        len = 0;
    }

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

    void pop() {
        if (isEmpty()) {
            cout << "Stack is empty" << endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete temp;
        len--;
    }

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

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

    int size() {
        return len;
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    cout << s.peek() << endl;
    cout << s.size() << endl;
    s.pop();
    cout << s.peek() << endl;
    cout << s.size() << endl;
    return 0;
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.top = None
        self.length = 0

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        self.length += 1

    def pop(self):
        if self.is_empty():
            print("Stack is empty")
            return
        self.top = self.top.next
        self.length -= 1

    def peek(self):
        if self.is_empty():
            print("Stack is empty")
            return -1
        return self.top.data

    def is_empty(self):
        return self.top is None

    def size(self):
        return self.length

# Example Usage
s = Stack()
s.push(5)
s.push(10)
s.push(15)
print(s.peek())
print(s.size())
s.pop()
print(s.peek())
print(s.size())
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class Stack {
  constructor() {
    this.top = null;
    this.length = 0;
  }

  push(data) {
    const newNode = new Node(data);
    newNode.next = this.top;
    this.top = newNode;
    this.length++;
  }

  pop() {
    if (this.isEmpty()) {
      console.log("Stack is empty");
      return;
    }
    this.top = this.top.next;
    this.length--;
  }

  peek() {
    if (this.isEmpty()) {
      console.log("Stack is empty");
      return -1;
    }
    return this.top.data;
  }

  isEmpty() {
    return this.top === null;
  }

  size() {
    return this.length;
  }
}

// Example Usage
const stack = new Stack();
stack.push(100);
stack.push(200);
stack.push(300);
console.log(stack.peek());
console.log(stack.size());
stack.pop();
console.log(stack.peek());
console.log(stack.size());

Comparison of Stack Implementation Using Array and Linked List

FeatureArrayLinked List
Memory AllocationRequires a contiguous block of memory.Uses non-contiguous memory; nodes allocated dynamically.
SizeFixed size (needs resizing for dynamic growth).Dynamic size; no resizing needed.
Memory EfficiencyCan waste space if resized or over-allocated.Allocates memory exactly as needed.
Push Operation (Insert) O(1), unless resizing is needed. O(1), always efficient.
Pop Operation (Delete) O(1), straightforward. O(1), straightforward.

How is this guide?