linked list can implement both stack and que code example

Example: stack using linked list

/// Stack using Linked List
/// we are using single Linked List and manage using head pointer not tail
#include <bits/stdc++.h>
using namespace std;

/*****************************/

// Template T is generic class which work for any datatype.
template <typename T>

class Node {
 public:
  T data;
  Node<T> *next;

  Node(T data) : data(data), next(NULL) {}
};

//--------------------------------

template <typename T>

class Stack {
  Node<T> *head;
  int size{0};

 public:
  Stack() {
    head = NULL;
    size = 0;
  }

  //-------------------------------- getSize()   - O(1)

  int getSize() { return size; }

  //---------------------------------- isEmpty() - O(1)
  
  bool isEmpty() {
    if (head == NULL) {
      return true;
    }
    return false;
  }
  //---------------------------------- push() - O(1)

  void push(int data) {
    Node<T> *temp = new Node<T>(data);
    temp->next = head;
    head = temp;
    size++;
  }

  //--------------------------------- pop() - O(1)
  void pop() {
    if (head == NULL) {
      cout << "==============" << endl;
      cout << "STACK EMPTY!!!" << endl;
      cout << "==============" << endl;
      return;
    }

    Node<T> *temp = head;
    head = head->next;

    /// free node - isolation step
    temp->next = NULL;
    delete temp;
    size--;
  }

  //---------------------------------- top_element()  - O(1)

  T top() {
    if (head == NULL) {
      cout << "==============" << endl;
      cout << "STACK EMPTY!!!" << endl;
      cout << "==============" << endl;
      return 0;
    }

    return head->data;
  }
};

/*****************************/

int main() {
  
  Stack<int> s;
  s.push(10);
  s.push(20);
  s.push(30);
  s.push(40);
  s.push(50);


  cout << s.getSize() << endl;
  cout << s.top() << endl;
  s.pop();

}

Tags:

C Example