由两个栈组成的队列

[编程题]由两个栈组成的队列

热度指数：7562 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

用两个栈实现队列，支持队列的基本操作。

输入描述:

第一行输入一个整数N，表示对队列进行的操作总数。

下面N行每行输入一个字符串S，表示操作的种类。

如果S为"add"，则后面还有一个整数X表示向队列尾部加入整数X。

如果S为"poll"，则表示弹出队列头部操作。

如果S为"peek"，则表示询问当前队列中头部元素是多少。

输出描述:

对于每一个为"peek"的操作，输出一行表示当前队列中头部元素是多少。

示例1

输入

6
add 1
add 2
add 3
peek
poll
peek

输出

1
2

备注:

1<=N<=1000000

-1000000<=X<=1000000

数据保证没有不合法的操作

算法知识视频讲解

helloxuanbao

#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdbool.h>

typedef struct {
    int *data;
    int top;
} stack;

stack *new_stack(int cap);

void push(stack *st, int val);

int pop(stack *st);

int top(stack *st);

bool is_empty(stack *st);

void destroy_stack(stack *st);

typedef struct {
    stack *data;
    stack *help;
} queue;

queue *new_queue(int n);

void add(queue *q, int val);

int poll(queue *q);

int peek(queue *q);

void destroy_queue(queue *q);

static void move(queue *q);

int main(void) {
    int n, x;
    char opt[10];
    scanf("%d", &n);
    queue *q = new_queue(n);
    for (int i = 0; i < n; i++) {
        scanf("%s", opt);
        if (strcmp(opt, "add") == 0) {
            scanf("%d", &x);
            add(q, x);
        } else if (strcmp(opt, "poll") == 0) {
            poll(q);
        } else {
            printf("%d\n", peek(q));
        }
    }
    destroy_queue(q);
    return 0;
}

stack *new_stack(int cap) {
    stack *st = (stack *) malloc(sizeof(stack));
    st->data = (int *) malloc(sizeof(int) * cap);
    st->top = -1;
    return st;
}

void push(stack *st, int val) {
    st->data[++st->top] = val;
}

int pop(stack *st) {
    return st->data[st->top--];
}

int top(stack *st) {
    return st->data[st->top];
}

bool is_empty(stack *st) {
    return st->top == -1;
}

void destroy_stack(stack *st) {
    free(st->data);
    free(st);
}

queue *new_queue(int n) {
    queue *q = (queue *) malloc(sizeof(queue));
    q->data = new_stack(n);
    q->help = new_stack(n);
    return q;
}

void add(queue *q, int val) {
    push(q->data, val);

}

int poll(queue *q) {
    if (is_empty(q->help)) {
        move(q);
    }
    return pop(q->help);
}

int peek(queue *q) {
    int x;
    if (is_empty(q->help)) {
        move(q);
    }
    x = top(q->help);
    return x;
}

void destroy_queue(queue *q) {
    destroy_stack(q->data);
    destroy_stack(q->help);
    free(q);
}

static void move(queue *q) {
    if (!is_empty(q->help)) {
        return;
    }
    while (!is_empty(q->data)) {
        push(q->help, pop(q->data));
    }
}

发表于 2022-02-16 00:08:40 回复(0)