Реализация связанного списка в стеке

Question

Довольно плохо знаком с реализацией стеков и искал возможную обратную связь. Мой код дает правильный вывод, но я знаю, что это не всегда означает, что он работает так, как предполагается. Я выбрал подход, согласно которому реализация стека с использованием связанного списка, по сути, была такой же, как ваша обычная реализация связанного списка, за исключением того, что все операции выполняются в конце списка. Я не был слишком уверен, что этот подход был верным, но он следовал первому подходу «последним вышел» и имеет ту же сложность для доступа и поиска (O (n)), а также для вставки и удаления O (1). Например, pop () будет просто удалять узел из конца связанного списка, а push () будет просто добавлять узел в конец связанного списка. Я вставил свой код ниже с комментариями внутри них, объясняющими, что я делаю или пытаюсь сделать (если это неверно).

#include <iostream>

struct Node{
    int data;
    Node* next;
};

bool isEmpty(Node** stack){
    if(*stack == NULL){
        return true;
    }
    return false;
}
void push(Node** stack, int data){
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next=NULL;
    // stack similar to "head" 
    if(isEmpty(&(*stack))){
        *stack = new_node;
        return;
    }
    Node* temp = *stack;
    while(temp->next != NULL){
        temp = temp->next;
    }
    temp->next = new_node;
}


void pop(Node** stack){
    // checking if stack is empty
    if(isEmpty(&(*stack))){
        std::cout<<"Stack underflow"<<std::endl;
        return;
    }
    Node* deleteMe = *stack;
    // if at the first element in the stack
    if(deleteMe->next == NULL){
        *stack = (*stack)->next;
        delete deleteMe;
        return;
    }
    while(deleteMe->next != NULL){
        if(deleteMe->next->next==NULL){
            // saving the current location of the node before the node which I want to delete
            Node* temp = deleteMe;
            // updating the deleteMe pointer to the node which I want to delete
            deleteMe = deleteMe->next;
            // setting the current node before the deleteMe node to point to NULL instead of the node which I want to delete
            temp->next = NULL;
            delete deleteMe;
            return;
        }
        deleteMe = deleteMe->next;
    }
}

void printList(Node* stack){
    Node* temp = stack;
    while(temp!=NULL){
        std::cout<<temp->data<<" ";
        temp = temp->next;
    }
    std::cout<<"\n";
}

int top(Node** stack){
    Node* top = *stack;
    while(top->next!=NULL){
        top = top->next;
    }
    return top->data;
}


int main(){
    Node* stack = NULL;
    // testing implementation below
    push(&stack,10);
    std::cout<<top(&stack)<<std::endl;
    push(&stack,20);
    std::cout<<top(&stack)<<std::endl;
    push(&stack,30);
    push(&stack,40);
    printList(stack);
    std::cout<<top(&stack)<<std::endl;
    pop(&stack);
    pop(&stack);
    push(&stack,40);
    std::cout<<top(&stack)<<std::endl;
}

Answer 1

Ваша реализация выглядит хорошо, еще одно улучшение можно сделать, поддерживая указатель головы и хвоста, так что вы можете удалить 1-й и последний элемент по мере необходимости. Вот пример кода C ++.

#include <iostream>
using namespace std;

template <class T> class node {
public:
  node<T>() {}
  ~node<T>() {}

  T data;
  node<T> *next;
};

template <class T> class linked_list {

public:
  linked_list<T>() : head(NULL), tail(NULL) {}
  ~linked_list<T>() {}

  virtual void addFirst(T data) {
    node<T> *n = new node<T>();

    if (head == NULL)
      tail = n;
    n->data = data;
    n->next = head;
    head = n;

    size++;
  }

  virtual void addLast(T data) {
    node<T> *n = new node<T>();

    n->data = data;

    if (tail == NULL) {
      head = n;
    } else {
      tail->next = n;
    }
    n->next = NULL;
    tail = n;
  }

  virtual void reverse() {
    if ((head == NULL) || (head->next == NULL))
      return;

    node<T> *current = head;
    node<T> *previous = NULL;
    node<T> *next = current->next;

    tail = current;

    while (current) {
      next = current->next;
      current->next = previous;
      previous = current;
      current = next;
    }

    head = previous;
  }

  virtual void print_nodes() {

    node<T> *temp = head;

    while (temp) {
      cout << temp->data << " " << flush;
      temp = temp->next;
    }

    cout << endl;
  }

  virtual void removeLast() {
    node<T> *temp = head;

    while (temp->next->next) {
      temp = temp->next;
    }
    tail = temp;
    delete temp->next;
    temp->next = NULL;
  }

  virtual void removeFirst() {
    node<T> *temp = head;
    head = head->next;
    delete temp;
  }

private:
  node<T> *head;
  node<T> *tail;
  uint32_t size;
};

int main(int argc, const char *argv[]) {

  linked_list<uint32_t> *llist = new linked_list<uint32_t>();

  llist->addLast(1);

  llist->addFirst(5);
  llist->addFirst(10);
  llist->addFirst(15);
  llist->addFirst(20);

  llist->addLast(30);

  llist->addFirst(40);

  llist->print_nodes();

  llist->reverse();

  llist->print_nodes();

  llist->removeLast();

  llist->print_nodes();

  llist->removeFirst();

  llist->print_nodes();

  return 0;
}