CODEWITHSUNDEEP
c++
RNGesus.exe
RNGesus.exe

Reputation: 197

I made my own custom stack and want to know how is there a way to iterate through the stack in reverse

This is the interface file

#ifndef STACK_H
#define STACH_H
#include<iostream>
using namespace std;

class Stack
{
    struct StackFrame{
        char data;
        StackFrame* next;
    };
    StackFrame* head;
public:
    Stack();
    void push(char);
    char pop();
    void empty();
    bool check_empty();
    void print();
    //Note:This code prints the data in stack format !!!
    ~Stack();
};



#endif // !STACK_H

This is the implementation file

#include "Stack.h"

Stack::Stack():head(nullptr){}

void Stack::push(char c)
{
    StackFrame* temp = new  StackFrame;
    temp->data = c;
    temp->next = nullptr;

    if (head == nullptr)
    {
        head = temp;
        return;
    }

    temp->next = head;
    head = temp;
}

char Stack::pop()
{
    if (head == nullptr)
    {
        cerr << "There is nothing in the stack to pop at the moment!!!" << endl;
        return '\0';
    }

    StackFrame* holder = head;
    char temp_chr = holder->data;

    head = head->next;
    free(holder);
    holder = nullptr;

    return temp_chr;
}

void Stack::empty()
{
    StackFrame* holder;
    while(head!=nullptr)
    {
        holder = head;
        head = head->next;
        free(holder);
    }
    holder = nullptr;
    head = nullptr;
}

bool Stack::check_empty()
{
    return head==nullptr;
}

void Stack::print() {
    if (head == nullptr)
    {
        cerr << "Nothing in stack at the moment :( " << endl;
        return;
    }

    StackFrame* holder = head;
    while (holder != nullptr)
    {
        cout << holder->data;
        holder = holder->next;
    }
    cout << endl;
}

Stack::~Stack()
{
    empty();
}

This is the application file

#include"Stack.h"
#include<string>

int main()
{
    int num;
    string push;
    Stack st;
    cout << "Enter your name = ";
    getline(cin, push);
    for (int i = 0; i < push.length(); i++)
    {
        st.push(push[i]);
    }
    st.print();

    cout << "How many times do you want to pop? = ";
    cin >> num;
    for (int i = 0; i < num; i++)
    {
        st.pop();
    }
    st.print();
    return EXIT_SUCCESS;
}

Can someone help me out on how to reverse iterate in this stack class which i made myself using the concept of linked list, i googled a bit and got the gist of things to use tail , Can someone elaborate another way if possible please or share a link to a site. It will help me out later a lot when i start working on binary trees and if i ever need to reverse iterate in the binary tree nodes.

Upvotes: 1

Views: 136

Answers (3)

Mehroz Mustafa
Mehroz Mustafa

Reputation: 222

I think you should add a second Stack object rather than a second list.

Upvotes: 1

franji1
franji1

Reputation: 3156

Recursive algorithm would have worked fine (use the recursive call stack as your "reverse" stack).

void Stack::print(StackFrame *pCurr) {
    if (pCurr != nullptr)
        {
        print(pCurr->Next);
        cout << pCurr->ch;
        }
    }

void Stack::print() {
    if (head == nullptr)
        {
        cerr << "Nothing in stack at the moment :( " << endl;
        return;
        }
    print(head);
    cout << endl;
    }

Upvotes: 0

user5550963
user5550963

Reputation:

First of all as mentioned above, stack is LIFO data structure and thus should use another data structure for that purpose.

Second, you can use second stack and copy data over to new stack, which is expensive.

Third option would be to go from the top and kip a track and store pointer to the previous node and to the pointer that point to the previous of previous node. Something like this:

struct reverseStack {
    StackFrame* node;
    reverseStack* previousPointer;

    reverseStack (StackFrame* n, ReverseStack* p) :
        node (n), previousPointer(p) { }
}

than using simple for loop you create pointer to the top, and go to the next and store that info into this structure. In your code you have something like this:

reverseStack top (nullptr, topFrame);
StackFrame currentFrame = top->next();
ReverseStack current; = top;
while (currentFrame != nullptr) {
    // alghoritm for linking previous nodes.
}

Upvotes: 2

Related Questions