stack

Stack Data Structure

The third and final list-typed data structure we will go over is the stack. A stack follows the Last In First Out (LIFO) structure, meaning that the most recent node to be added to the stack will be the first one removed. This is slightly different from the queue data structure which you can read about here. To better understand the stack data structure, visualize plates stacked on top of each other. The last plate that was placed on the stack is the first to be taken. Software applications of a stack are: undoing actions, going back an internet page, and evaluating expressions.

Below is a basic implementation of a stack in C++. We implement it using a doubly linked list and with three main functions:

Push - Add a node to the end of the stack
Pull - remove and return the node at the end of the stack
Peek - return the value of the end node but don't remove it

using namespace std;

#include <iostream>

class Node {

public:

int value;

Node* next;

Node* previous;

Node(int v) {

value = v;

}

Node() {}

};

class Stack {

public:

Node* head;

Node* back;

Stack() {}

void push(int newVal) {

Node* n = new Node(newVal);

if (head == NULL) {

head = n;

back = n;

}

else {

back->next = n;

n->previous = back;

back = n;

}

Node* pop() {

if (head == NULL) {

throw "Stack is empty";

}

else {

Node* returnValue = back;

back = back->previous;

back->next = NULL;

return returnValue;

}

Node* peek() {

if (head == NULL) {

throw "Stack is empty";

}

else {

return back;

}

};

void printStackValues(Stack* sArg) {

if (sArg->head == NULL) {

throw "Stack is empty";

}

else {

Node* current = sArg->head;

while (current->next != NULL) {

cout << current->value << ", ";

current = current->next;

}

cout << current->value;

}

int main(){

Stack* s = new Stack();

s->push(5);

s->push(10);

s->push(15);

s->push(20);

cout << "Values after pushing:\n";

printStackValues(s);

cout << "\nFirst Pop value:\n";

cout << s->pop()->value;

cout << "\nStack values after one Pop:\n";

printStackValues(s);

cout << "\nCurrent Peek value:\n";

cout << s->peek()->value;

}

Output:

Values after pushing:

5, 10, 15, 20

First Pop value:

Stack values after one Pop:

5, 10, 15

Current Peek value:

Click here to view the next section: Trees