A stack is a data structure that follows the LIFO (last-in, first-out) principle. This means that the last element added to the stack is the first one to be removed. A linked list is a data structure consisting of nodes, each containing data and a reference (a pointer in C++) to the next node in the list.
To implement a stack using a linked list, we can create a Node
class to represent each element in the list. Each Node
object would contain two fields: data
to store the actual data, and next
to store a reference to the next node in the list.
We begin by creating a
Node
class with two fields:data
to store the actual data, andnext
to store a pointer to the next node in the list.
We also define a constructor for the
Node
class that takes a data element as input and initializes thedata
field to the input value and thenext
field tonullptr
.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = nullptr;
}
};
We then create a
Stack
class to manage the linked list. TheStack
class has a single fieldtop
, which is a pointer to the top node in the list.
We define a constructor for the
Stack
class that initializestop
tonullptr
.
We then define a
push()
method that takes a data element as input, creates a newNode
object with that data, and inserts the new node at the top of the list. Iftop
isnullptr
, then we simply settop
to the new node. Otherwise, we set thenext
field of the new node to the currenttop
node, and then settop
to the new node.
We define a
pop()
method that removes the top node from the list and returns its data. Iftop
isnullptr
, then the stack is empty, so we simply return-1
. Otherwise, we settop
to the next node in the list, and then delete the old top node. We also return the data stored in the old top node.
Finally, we define an
is_empty()
method that checks iftop
is equal tonullptr
. Iftop
isnullptr
, then the stack is empty, so we returntrue
. Otherwise, we returnfalse
.
class Stack {
private:
Node* top;
public:
Stack() {
top = nullptr;
}
void push(int data) {
Node* new_node = new Node(data);
if (top == nullptr) {
top = new_node;
}
else {
new_node->next = top;
top = new_node;
}
}
int pop() {
if (top == nullptr) {
return -1;
}
else {
int popped_data = top->data;
Node* temp = top;
top = top->next;
temp->next = nullptr;
delete temp;
return popped_data;
}
}
bool is_empty() {
return top == nullptr;
}
};
Here's an example usage of the Stack
class:
int main() {
Stack s;
s.push(1);
s.push(2);
s.push(3);
cout << s.pop() << endl;
cout << s.pop() << endl;
cout << s.pop() << endl;
cout << s.pop() << endl; // this will print -1, indicating the stack is empty
return 0;
}
In this example, we create a new
Stack
objects
.We then push the elements 1, 2, and 3 onto the stack using the
push()
method.We then use the
pop()
method to remove and print the elements from the stack in LIFO order.Finally, we use the
pop()
method to attempt
Overall, implementing a stack using a linked list is relatively straightforward. The key idea is to use the next
field of each node to keep track of the next node in the list. This
allows us to easily insert and remove nodes from the list, and to keep
track of the top node in the stack.
Smm panel sektöründe ana sağlayıcı olarak hizmet veriyoruz
ReplyDelete