leetCode-0232_用栈实现队列

Posted on | In |

题目描述

英文题目

  • Implement the following operations of a queue using stacks.

    • push(x) – Push element x to the back of queue.
    • pop() – Removes the element from in front of queue.
    • peek() – Get the front element.
    • empty() – Return whether the queue is empty.

    Example:

    1
    2
    3
    4
    5
    6
    7
    MyQueue queue = new MyQueue();

    queue.push(1);
    queue.push(2);  
    queue.peek();  // returns 1
    queue.pop();   // returns 1
    queue.empty(); // returns false

    Notes:

    • You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
    • Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
    • You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
中文题目

  • 使用栈实现队列的下列操作：

    • push(x) – 将一个元素放入队列的尾部。
    • pop() – 从队列首部移除元素。
    • peek() – 返回队列首部的元素。
    • empty() – 返回队列是否为空。

    示例:

    1
    2
    3
    4
    5
    6
    7
    MyQueue queue = new MyQueue();

    queue.push(1);
    queue.push(2);  
    queue.peek();  // 返回 1
    queue.pop();   // 返回 1
    queue.empty(); // 返回 false

    说明:

    • 你只能使用标准的栈操作 – 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
    • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
    • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。

解决方法

方法一
  • 描述

需要一个辅助栈tmp，把s的元素也逆着顺序存入tmp中，此时加入新元素x，再把tmp中的元素存回来，这样就是我们要的顺序了，其他三个操作也就直接调用栈的操作即可

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
typedef struct {
    LinkStack *s1;
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {
    MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));
    queue->s1 = link_stack_create();
    
    return queue;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    LinkStack *tmp = link_stack_create();
    while (!link_stack_is_empty(obj->s1)) {
        int data = 0;
        link_stack_top(obj->s1, &data);
        link_stack_push(tmp, data);
        link_stack_pop(obj->s1, &data);
    }
    
    link_stack_push(obj->s1, x);
    while (!link_stack_is_empty(tmp)) {
        int data = 0;
        link_stack_top(tmp, &data);
        link_stack_push(obj->s1, data);
        link_stack_pop(tmp, &data);
    }
    
    free(tmp);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    int data = 0;
    link_stack_pop(obj->s1, &data);
    return data;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    int data = 0;
    link_stack_top(obj->s1, &data);
    return data;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return link_stack_is_empty(obj->s1);
}

void myQueueFree(MyQueue* obj) {
    link_stack_destory(obj->s1);
    free(obj);
}
方法二
  • 描述

使用了两个栈_new和_old，其中新进栈的都先缓存在_new中，入股要pop和peek的时候，才将_new中所有元素移到_old中操作，提高了效率

  • 源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
typedef struct {
    LinkStack *s1;//新
    LinkStack *s2;//旧
} MyQueue;

/** Initialize your data structure here. */
MyQueue* myQueueCreate(int maxSize) {
    MyQueue *queue = (MyQueue *)malloc(sizeof(MyQueue));
    queue->s1 = link_stack_create();
    queue->s2 = link_stack_create();
    
    return queue;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    
    link_stack_push(obj->s1, x);
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if (link_stack_is_empty(obj->s2)) {
        while (!link_stack_is_empty(obj->s1)) {
            int data = 0;
            link_stack_top(obj->s1, &data);
            link_stack_push(obj->s2, data);
            link_stack_pop(obj->s1, &data);
        }
    }
    
    if (!link_stack_is_empty(obj->s2)) {
        int data = 0;
        link_stack_pop(obj->s2, &data);
        return data;
    }
    return 0;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
    if (link_stack_is_empty(obj->s2)) {
        while (!link_stack_is_empty(obj->s1)) {
            int data = 0;
            link_stack_top(obj->s1, &data);
            link_stack_push(obj->s2, data);
            link_stack_pop(obj->s1, &data);
        }
    }
    
    if (!link_stack_is_empty(obj->s2)) {
        int data = 0;
        link_stack_top(obj->s2, &data);
        return data;
    }
    return 0;
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return link_stack_is_empty(obj->s1) && link_stack_is_empty(obj->s2);
}

void myQueueFree(MyQueue* obj) {
    link_stack_destory(obj->s1);
    link_stack_destory(obj->s2);
    free(obj);
}

void testQueue()
{
    MyQueue *queue = myQueueCreate(5);
    myQueuePush(queue, 1);
    myQueuePush(queue, 2);
    myQueuePush(queue, 3);
    myQueuePush(queue, 4);
    
    while (!myQueueEmpty(queue)) {
        int data = myQueuePop(queue);
        printf("%d\n",data);
    }
    
}

题目来源

Implement Queue using Stacks

用栈实现队列

栈相关代码

数据结构-栈

##