时间戳

首页 > 解决方案 > 我制作了自己的自定义堆栈，并想知道如何反向遍历堆栈

c++ - 我制作了自己的自定义堆栈，并想知道如何反向遍历堆栈

问题描述

这是接口文件

#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

这是实现文件

#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();
}

这是申请文件

#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;
}

有人可以帮我解决如何在我自己使用链表的概念制作的这个堆栈类中进行反向迭代，我用谷歌搜索了一下，得到了使用tail的要点，如果可能的话，有人可以详细说明一下吗，或者分享一个链接到一个网站。当我开始研究二叉树并且我需要在二叉树节点中进行反向迭代时，它将帮助我很多。

标签： c++

解决方案

首先，如上所述，堆栈是 LIFO 数据结构，因此应该为此使用另一种数据结构。

其次，您可以使用第二个堆栈并将数据复制到新堆栈，这很昂贵。

第三种选择是从顶部开始并 kip 轨道并存储指向前一个节点的指针以及指向前一个节点的前一个节点的指针。像这样的东西：

struct reverseStack {
    StackFrame* node;
    reverseStack* previousPointer;

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

与使用简单的 for 循环相比，您创建指向顶部的指针，然后转到下一个并将该信息存储到此结构中。在您的代码中，您有以下内容：

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

推荐阅读