Структура данных стека в связанном списке
Здесь у меня есть код C++ для реализации стека push() и pop() с использованием связанного списка. Я delete/pop() одни данные и все работает нормально, но я хочу pop()/ delete много элементов данных. Предположим, что данные 6 5 4 3 2 1, и я хочу удалить 6 5 4 3, что я могу сделать для этого?
#include <iostream>
using namespace std;
//Structure of the Node
struct Node
{
int data;
Node *next;
};
// top pointer to keep track of the top of the stack
Node *top = NULL;
//Function to check if stack is empty or not
bool isempty()
{
if (top == NULL){
return true;
} else {
}
return false;
}
void pushStack(int value){
Node *ptr = new Node();
ptr->data = value;
ptr->next = top;
top = ptr;
}
//Function to delete an element from the stack
void pop ( )
{
if ( isempty() )
cout << "Stack is Empty";
else
{
Node *ptr = top;
top = top->next;
delete(ptr);
}
}
// Function to Display the stack
void displayStack()
{
if ( isempty() )
cout << "Stack is Empty";
else
{
Node *temp = top;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
}
int main()
{
pushStack(1);
pushStack(2);
pushStack(3);
pushStack(4);
pushStack(5);
pushStack(6);
pop();
displayStack();
return 0;
}
@Remy Lebeau, почему я должен вызывать pop() четыре раза?
@willy Потому что это то, о чем вы просили: «Я хочу удалить 6 5 4 3». Это последние 4 числа, помещенные в стек, поэтому для их удаления требуется 4 вызова pop().
Я думал, что у вас есть связанный список, и я был сбит с толку оберткой и ограничением его поведения как стека. Вместо этого вы пишете связанный список и просто предоставляете ему интерфейс стека. Я не знаю, какой подход вы должны использовать, это зависит.
@Remy Lebeau, а что мне делать, если я хочу удалить элемент между 6 и 3?
Теперь комментарии звучат так, как будто OP просто хочет связанный список, а не стек.
@willy Затем вы просто перебираете список, пока не найдете узел с желаемым значением, delete его из списка и обновите указатель next предыдущего узла, чтобы он указывал на следующий узел в списке. Повторяйте по мере необходимости. Но это не то, как должен работать стек.
@sweenish можешь переписать коды?
Если бы я это сделал, это было бы совсем не похоже на то, что вы представили. Это связанный список в стиле C. И в зависимости от фактической цели, переписывание может быть не чем иным, как #include <stack>. Но я предполагаю, что это домашнее задание. Так что нет, я не буду писать за тебя домашнюю работу.
@sweenish как должно быть
@sweenish только для обучения и расширения знаний
Настоящий класс для одного. Предпочтительно класс-шаблон, поскольку контейнер должен быть контейнером независимо от типа данных, которые он содержит. Класс стека должен действительно просто обертывать какой-то другой более общий контейнер. Если вы проделали тяжелую работу и уже написали связанный список, ваш класс стека будет содержать список в частном порядке, а общедоступный API для класса гарантирует, что связанный список будет вести себя только как стек.
Тогда я бы предложил найти лучший учебный ресурс, поскольку ваши вопросы до сих пор указывали на то, что вы не знаете, что такое стек, и это проблема, если вы пытаетесь его написать.
@willy посмотри обновление, которое я только что сделал для своего ответа
Ответы 1
У вас есть 6 элементов, помещенных в стек, и вы просите удалить последние 4 элемента, которые были помещены в стек. Просто позвоните pop() 4 раза, например:
int main()
{
pushStack(1);
pushStack(2);
pushStack(3);
pushStack(4);
pushStack(5);
pushStack(6);
displayStack(); // displays "6 5 4 3 2 1"
pop();
pop();
pop();
pop();
displayStack(); // displays "2 1"
return 0;
}
Онлайн демо
ОБНОВЛЯТЬ:
В комментариях вы спрашиваете, как удалить определенные узлы из середины стека. Хотя это легко сделать с помощью связанного списка, стек не предназначен для такой работы. Стек представляет собой контейнер First-In-Last-Out (FILO), что означает, что первое помещенное значение является последним извлеченным значением. Таким образом, вы должны помещать и извлекать значения только из вершины стека, и больше нигде.
Но если вы действительно хотите это сделать, это будет выглядеть примерно так:
#include <iostream>
using namespace std;
//Structure of the Node
struct Node
{
int data;
Node *next;
};
// top pointer to keep track of the top of the stack
Node *top = NULL;
//Function to check if stack is empty or not
bool isEmpty()
{
return (top == NULL);
}
//Function to add an element to the top of the stack
void pushStack(int value){
Node *ptr = new Node();
ptr->data = value;
ptr->next = top;
top = ptr;
}
//Function to delete the top element from the stack
void pop()
{
if ( isEmpty() )
cout << "Stack is Empty\n";
else
{
Node *ptr = top;
top = top->next;
delete ptr;
}
}
void removeValue(int value)
{
if ( isEmpty() )
cout << "Stack is Empty\n";
else
{
Node *temp = top, **ptr = ⊤
while (temp != NULL)
{
if (temp->data == value)
{
*ptr = temp->next;
delete temp;
return;
}
ptr = &(temp->next);
temp = temp->next;
}
cout << "Value not found\n";
}
}
// Function to display the stack
void displayStack()
{
if ( isEmpty() )
cout << "Stack is Empty\n";
else
{
Node *temp = top;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << "\n";
}
}
int main()
{
pushStack(1);
pushStack(2);
pushStack(3);
pushStack(4);
pushStack(5);
pushStack(6);
displayStack(); // displays "6 5 4 3 2 1"
removeValue(4);
removeValue(5);
displayStack(); // displays "6 3 2 1"
return 0;
}
Онлайн демо
Позвольте мне погрузиться в
⟼Помните, что всегда важно, особенно когда вы изучаете и задаете вопросы о Stack Overflow, поддерживать как можно более организованный код. Постоянный отступ помогает передать структуру и, что важно, намерение, что помогает нам быстро перейти к корню проблемы, не тратя много времени на попытки расшифровать, что происходит.