Stack Implementation using Linked List: CSU1051P - Shoolini U

Implementation of Stack Using Linked List

To understand the implementation of a stack using linked list using C++

Objective

To understand the implementation of a stack using linked list using C++

#include <iostream>
using namespace std;

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

class Stack {
private:
    Node* top;
public:
    Stack() { top = NULL; }

    void push(int val) {
        Node* temp = new Node();
        temp->data = val;
        temp->next = top;
        top = temp;
    }

    void pop() {
        if (top == NULL) {
            cout << "Stack is empty" << endl;
            return;
        }
        Node* temp = top;
        top = top->next;
        delete(temp);
    }

    int view() {
        if (top != NULL)
            return top->data;
        else
            return -1;
    }
};

int main() {
    Stack s;
    s.push(1);
    s.push(2);
    s.push(3);
    cout << "Popped: " << s.view() << endl;
    s.pop();
    cout << "Top of Stack: " << s.view() << endl;

    return 0;
}

Discussion of Algorithms

  1. Start
  2. Create a Node structure with element and next node reference
  3. Create a Stack class that will use the Node structure
  4. Implement the push operation to add element at the top of the stack
  5. Implement the pop operation to remove the element from the top of the stack
  6. Implement the view operation to get the top element of the stack
  7. End

Representations


Flow Diagram

   +----------------------------------+
   |                                  |
   |           Start                  |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |      Declare Stack object s      |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Push operations          |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Print the top of the stack    |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |         Pop operation            |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |    Print the new top of stack    |
   |             |                    |
   +----------------------------------+
                  |
                  V
   +----------------------------------+
   |                                  |
   |             Exit                 |
   |             |                    |
   +----------------------------------+

Tabular Dry Run

Push | Pop | View | Elements
  1  |     |      | 1
  2  |     |      | 1 2
  3  |     |      | 1 2 3
     |     |  3   | 1 2 3
     |  3  |      | 1 2
     |     |  2   | 1 2

Results/Output

Popped: 3
Top of Stack: 2