Understanding Stacks with Pointers (USP)

AVAILABLE:    5

The complete operations of a stack are as follows:

1. Declaring a Stack with Pointers

The declaration process for a stack involves creating the stack structure in memory. When using pointers, two structures are created:

• A node structure that contains data and a pointer to the next node.
• A stack structure that stores the count of stack elements and a pointer to the top of the stack.

Node Declaration:

struct node {
    int bil;
    struct node *next;
};

Stack Declaration:

struct stack {
    int jumlah;
    struct node *top;
};

2. Initialization

Stack initialization involves creating an empty stack. For pointer-based stacks, this is done by setting the top field to NULL.

stack.top = NULL;

3. Check if Stack is Empty

This operation checks whether the stack is empty, which is crucial for the pop operation. If the stack is empty, pop cannot proceed. This check is performed by evaluating the number of elements in the stack. If the count is 0, the stack is empty.

int cekKosong(stack *stack) {
    if (stack->jumlah == 0)
        return 1;
    else
        return 0;
}

4. Check if Stack is Full

This operation determines whether the stack is full. It returns true (1) if the top field matches the stack size.

int cekPenuh(stack *stack) {
    if (stack->jumlah == size)
        return 1;
    else
        return 0;
}

5. Push Operation

This operation adds a new element to the stack at the top position and updates the top pointer. Steps include:

• Check if the stack is full.
• If not full, proceed with the push operation.
• Link the new node to the current top, update the top pointer, and increment the count.

void Push(stack *stack) {
    node *baru;
    if (cekPenuh(stack)) {
        cout << "Stack full";
        getch();
    } else {
        baru = new(node);
        cout << "\nEnter value to push into the stack: ";
        cin >> baru->bil;
        baru->next = stack->top;
        stack->top = baru;
        stack->jumlah++;
        cout << "\nPush successful";
        getch();
    }
}

6. Pop Operation

This operation removes the last (top) element from the stack and updates the top pointer. Steps include:

• Check if the stack is empty.
• If not empty:
  • Use a helper pointer to read the top node.
  • Update the top pointer to the previous node.
  • Decrement the count.
  • Delete the helper node.

void Pop(stack *stack) {
    node *hapusPtr;
    hapusPtr = stack->top;
    if (cekKosong(stack)) {
        cout << "Stack Empty";
        getch();
    } else {
        stack->top = stack->top->next;
        stack->jumlah--;
        delete hapusPtr;
        cout << "\nPop operation successful\n";
        getch();
    }
}

Full Program Implementation

#include <iostream.h>
#include <conio.h>
#define size 5

struct node {
    int bil;
    struct node *next;
};

struct stack {
    int jumlah;
    struct node *top;
};

int cekPenuh(stack *stack) {
    if (stack->jumlah == size)
        return 1;
    else
        return 0;
}

int cekKosong(stack *stack) {
    if (stack->jumlah == 0)
        return 1;
    else
        return 0;
}

void Push(stack *stack) {
    node *baru;
    if (cekPenuh(stack)) {
        cout << "Stack full";
        getch();
    } else {
        baru = new(node);
        cout << "\nEnter value to push into the stack: ";
        cin >> baru->bil;
        baru->next = stack->top;
        stack->top = baru;
        stack->jumlah++;
    }
}

void cetak(stack *stack) {
    node *bacaPtr;
    bacaPtr = stack->top;
    if (cekKosong(stack)) {
        cout << "\nStack empty";
        getch();
    } else {
        clrscr();
        cout << "\nTOP\n";
        cout << "---------\n";
        while (bacaPtr != NULL) {
            cout << bacaPtr->bil << endl;
            cout << "---------\n";
            bacaPtr = bacaPtr->next;
        }
        getch();
    }
}

void Pop(stack *stack) {
    node *hapusPtr;
    hapusPtr = stack->top;
    if (cekKosong(stack)) {
        cout << "Stack Empty";
        getch();
    } else {
        stack->top = stack->top->next;
        stack->jumlah--;
        delete hapusPtr;
        cout << "\nPop operation successful\n";
        getch();
    }
}

void Top(stack *stack) {
    int dataTop;
    if (cekKosong(stack)) {
        cout << "\nTop = NULL\n";
        getch();
    } else {
        dataTop = stack->top->bil;
        cout << "\nTop = " << dataTop << endl;
        getch();
    }
}

void hapus(stack *stack) {
    node *bantuHapus;
    while (stack->top != NULL) {
        bantuHapus = stack->top;
        stack->top = stack->top->next;
        delete bantuHapus;
    }
    stack->jumlah = 0;
}

void main() {
    stack stack;
    stack.jumlah = 0;
    stack.top = NULL;
    char pilih;

    do {
        clrscr();
        cout << "STACK MENU" << endl;
        cout << "[1]. Clear Stack" << endl;
        cout << "[2]. Push" << endl;
        cout << "[3]. Pop" << endl;
        cout << "[4]. View Top of Stack" << endl;
        cout << "[5]. Display Stack" << endl;
        cout << "[6]. Exit\n" << endl;
        cout << "\nChoice: ";
        cin >> pilih;

        if (pilih == '1') hapus(&stack);
        if (pilih == '2') { Push(&stack); cetak(&stack); }
        if (pilih == '3') { Pop(&stack); cetak(&stack); }
        if (pilih == '4') Top(&stack);
        if (pilih == '5') cetak(&stack);

    } while (pilih != '6');
}

Source:

Data Structures Course, STMIK EL Rahma Yogyakarta.
Prepared by Eko Riswanto