栈、队列的应用算法:输入一个字符串,分别进行回文判断和括号匹配。
时间: 2023-04-26 07:04:27 浏览: 171
栈和队列是常用的数据结构,它们可以用来解决很多实际问题。对于输入一个字符串,我们可以使用栈和队列来进行回文判断和括号匹配。
回文判断:我们可以将字符串中的每个字符依次入栈,然后再依次出栈,如果出栈的字符和原字符串中的字符相同,则说明该字符串是回文字符串。
括号匹配:我们可以使用栈来判断括号是否匹配。遍历字符串中的每个字符,如果是左括号,则将其入栈;如果是右括号,则将栈顶元素出栈,并判断是否与该右括号匹配。如果匹配,则继续遍历字符串;如果不匹配,则说明括号不匹配。
以上就是栈和队列在字符串回文判断和括号匹配中的应用算法。
相关问题
用顺序栈和顺序队列来设计算法判断一个输入的字符串是否是回文(c语音)
好的,我可以回答你的问题。下面是使用顺序栈和顺序队列来设计算法判断一个输入的字符串是否是回文的代码:
```
#include <stdio.h>
#include <string.h>
// 定义最大字符串长度
#define MAX_SIZE 50
// 定义栈结构体
typedef struct {
char data[MAX_SIZE];
int top;
} SeqStack;
// 定义队列结构体
typedef struct {
char data[MAX_SIZE];
int front;
int rear;
} SeqQueue;
// 初始化顺序栈
void InitStack(SeqStack *S)
{
S->top = -1;
}
// 判断顺序栈是否为空
int StackEmpty(SeqStack *S)
{
return S->top == -1;
}
// 入栈
int Push(SeqStack *S, char x)
{
if (S->top == MAX_SIZE - 1)
return 0;
S->data[++S->top] = x;
return 1;
}
// 出栈
int Pop(SeqStack *S, char *x)
{
if (StackEmpty(S))
return 0;
*x = S->data[S->top--];
return 1;
}
// 初始化顺序队列
void InitQueue(SeqQueue *Q)
{
Q->front = Q->rear = 0;
}
// 判断顺序队列是否为空
int QueueEmpty(SeqQueue *Q)
{
return Q->front == Q->rear;
}
// 入队
int EnQueue(SeqQueue *Q, char x)
{
if ((Q->rear + 1) % MAX_SIZE == Q->front)
return 0;
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MAX_SIZE;
return 1;
}
// 出队
int DeQueue(SeqQueue *Q, char *x)
{
if (QueueEmpty(Q))
return 0;
*x = Q->data[Q->front];
Q->front = (Q->front + 1) % MAX_SIZE;
return 1;
}
// 判断字符串是否是回文
int IsHuiwen(char *str)
{
SeqStack S;
SeqQueue Q;
int len = strlen(str);
int i, j;
char x, y;
InitStack(&S);
InitQueue(&Q);
// 字符串入栈、入队
for (i = 0; i < len; i++) {
Push(&S, str[i]);
EnQueue(&Q, str[i]);
}
// 判断是否是回文
for (i = 0; i < len / 2; i++) {
Pop(&S, &x);
DeQueue(&Q, &y);
if (x != y)
return 0;
}
return 1;
}
// 主函数
int main()
{
char str[MAX_SIZE];
printf("请输入一个字符串:");
scanf("%s", str);
if (IsHuiwen(str))
printf("%s 是回文\n", str);
else
printf("%s 不是回文\n", str);
return 0;
}
```
以上是使用顺序栈和顺序队列来设计算法判断一个输入的字符串是否是回文的代码。如果您还有其他问题,请继续提问。
使用顺序栈和顺序队列来设计算法判断一个输入的字符串是否是回文的代码(c语音)
以下是使用顺序栈和队列来实现判断字符串是否为回文的 C 语言代码:
```
#include <stdio.h>
#include <string.h>
#define MAXSIZE 100
typedef struct {
char data[MAXSIZE];
int top;
} Stack;
typedef struct {
char data[MAXSIZE];
int front, rear;
} Queue;
void initStack(Stack *st) {
st->top = -1;
}
void initQueue(Queue *q) {
q->front = q->rear = 0;
}
void push(Stack *st, char c) {
if (st->top == MAXSIZE - 1) {
printf("Stack overflow.\n");
return;
}
st->top++;
st->data[st->top] = c;
}
char pop(Stack *st) {
if (st->top == -1) {
printf("Stack underflow.\n");
return '\0';
}
char c = st->data[st->top];
st->top--;
return c;
}
void enqueue(Queue *q, char c) {
if ((q->rear + 1) % MAXSIZE == q->front) {
printf("Queue overflow.\n");
return;
}
q->data[q->rear] = c;
q->rear = (q->rear + 1) % MAXSIZE;
}
char dequeue(Queue *q) {
if (q->front == q->rear) {
printf("Queue underflow.\n");
return '\0';
}
char c = q->data[q->front];
q->front = (q->front + 1) % MAXSIZE;
return c;
}
int is_palindrome(char s[]) {
int len = strlen(s);
Stack st;
Queue q;
initStack(&st);
initQueue(&q);
for (int i = 0; i < len; i++) {
char c = s[i];
push(&st, c);
enqueue(&q, c);
}
while (st.top != -1) {
char c1 = pop(&st);
char c2 = dequeue(&q);
if (c1 != c2) {
return 0;
}
}
return 1;
}
int main() {
char s[MAXSIZE];
printf("Enter a string: ");
scanf("%s", s);
if (is_palindrome(s)) {
printf("%s is a palindrome.\n", s);
} else {
printf("%s is not a palindrome.\n", s);
}
return 0;
}
```
在这个代码中,我们定义了一个顺序栈和一个顺序队列来分别存储字符串中的字符,并使用 `push()` 和 `enqueue()` 函数将字符分别加入到栈和队列中。然后,我们使用 `pop()` 和 `dequeue()` 函数从栈和队列中取出字符并比较它们是否相等,如果所有字符都匹配,则该字符串是回文的,返回 1,否则返回 0。