时间戳

首页 > 解决方案 > 我尝试使用堆栈和队列解决字符串回文问题，但面临逻辑问题

c++ - 我尝试使用堆栈和队列解决字符串回文问题，但面临逻辑问题

问题描述

问题：回文是前后读相同的字符串，例如radar、toot 和madam。接下来的挑战是编写一个算法，从左到右逐字读取一个句子，并确定它是否是回文。以回文串为例。

  • “夫人，我是亚当。”
  • “前夕。”

解决这个问题的算法比较简单，

  • 使用堆栈和队列。
  • 将令牌（单词）推送和入队到两个数据结构中。
  • 将标记（单词）弹出并出列并进行比较。
  • 执行删除操作，直到其中一个数据结构为空。如果情况是两者都是空的，则该句子是回文。

您的任务是确定用户输入的字符串是否为回文。

#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;

#define MAX 1000

class Stack
{
    int top;
public:
    string myStack[MAX];

    Stack() { top = -1; }
    bool push(string item)
    {
        if (top >= (MAX - 1)) {
            cout << "Stack is full";
            return false;
        }
        else {
            myStack[++top] = item;
            cout << item << endl;
            return true;
        }
    }
    string pop()
    {
        if (top < 0) {
            cout << "Stack Underflow!!";
            return 0;
        }
        else {
            string item = myStack[top--];
            return item;
        }
    }
    bool isEmpty()
    {
     if (top == -1)
         return true;
     else
         return false;

    }
};

class Queue
{ public:
    string myqueue[MAX];
    int front, rear;
    Queue()
    {
         front = -1;
        rear = -1;
    }
    bool isFull() {
        if (front == 0 && rear == MAX - 1) {
            return true;
        }
        return false;
    }

    bool isEmpty() {
        if (front == -1) 
            return true;
        else 
            return false;
    }

    void enQueue(string item) {
        if (isFull()) {
            cout << endl << "Queue is full!!";
        }
        else {
            if (front == -1) front = 0;
            rear++;
            myqueue[rear] = item;
            cout << item << " "<<endl;
        }
    }
    string deQueue() {
        string value;
        if (isEmpty()) {
            cout << "Queue is empty!!" << endl;
            return false;
        }
        else {
            value = myqueue[front];
            if (front >= rear)
            {
                front = -1;
                rear = -1;
            }
            else {
                front++;
            }
            return(value);
        }
    }
};

int main()
{
    bool palindrome = true;
    Stack stack;
    stack.push("m");
    stack.push("a");
    stack.push("d");
    stack.push("a");
    stack.push("m");

    Queue queue;
    queue.enQueue("m");
    queue.enQueue("a");
    queue.enQueue("d");
    queue.enQueue("a");
    queue.enQueue("m");

    while (sizeof stack == 0 || sizeof queue == 0 )
    {
        stack.pop();
        queue.deQueue();
    };

    if (sizeof stack == sizeof queue )
    {
        cout << "The given word is palindrome." << endl;
    }
    else
    {
        cout << "The given word is not a palindrome." << endl;
    }

    system("pause");
    return 0;
}

标签： c++data-structuresstackqueue

解决方案

啊的魔力sizeof。

sizeof具有非常具体的含义（您可以查找）。它不会神奇地让您获得您喜欢的任何大小，以您喜欢的任何方式定义。

这段代码

while (sizeof stack == 0 || sizeof queue == 0 )

应该

while (stack.isEmpty() || queue.isEmpty())

你写了你的isEmpty方法，你应该使用它们。

但即使该代码也是错误的（由于逻辑问题）。我猜（但不太确定）你的意思是

while (!stack.isEmpty() && !queue.isEmpty())

总之sizeof在这段代码中没有位置。如果您需要知道堆栈或队列的大小，您应该编写一个size返回大小的方法（可能称为）。

推荐阅读