leetCode-0225_用队列实现栈

Posted on | In |

###

题目描述

英文题目

Implement the following operations of a stack using queues.

  • push(x) – Push element x onto stack.
  • pop() – Removes the element on top of the stack.
  • top() – Get the top element.
  • empty() – Return whether the stack is empty.

Example:

1
2
3
4
5
6
7
MyStack stack = new MyStack();

stack.push(1);
stack.push(2);  
stack.top();   // returns 2
stack.pop();   // returns 2
stack.empty(); // returns false

Notes:

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

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

  • push(x) – 元素 x 入栈
  • pop() – 移除栈顶元素
  • top() – 获取栈顶元素
  • empty() – 返回栈是否为空

注意:

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

解决方法

方法一

  • 描述

    需要另外一个队列来辅助操作，我们总共需要两个队列，其中一个队列用来放最后加进来的数，模拟栈顶元素。剩下所有的数都按顺序放入另一个队列中。

    当push操作时，将新数字先加入模拟栈顶元素的队列中，如果此时队列中有数字，则将原本有的数字放入另一个队中，让新数字在这队中，用来模拟栈顶元素。

    当top操作时，如果模拟栈顶的队中有数字则直接返回，如果没有则到另一个队列中通过平移数字取出最后一个数字加入模拟栈顶的队列中。

    当pop操作时，先执行下top()操作，保证模拟栈顶的队列中有数字，然后再将该数字移除即可。

    当empty操作时，当两个队列都为空时，栈为空

  • 源码

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
typedef struct
{
    LinkQueue *q1;
    LinkQueue *q2;//模拟栈顶元素
}MyStack;

MyStack *myStackCreate(int maxSize)
{
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));
    stack->q1 = link_queue_create();
    stack->q2 = link_queue_create();
    
    return stack;
}

//当push操作时，将新数字先加入模拟栈顶元素的队列中，如果此时队列中有数字，则将原本有的数字放入另一个队中，让新数字在这队中，用来模拟栈顶元素
void myStackPush(MyStack *obj, int x)
{
    link_queue_enqueue(obj->q2, x);
    while (link_queue_length(obj->q2) > 1) {
        link_queue_enqueue(obj->q1, obj->q2->head->data);
        
        int data = 0;
        link_queue_dequeue(obj->q2, &data);
    }
}

//当top操作时，如果模拟栈顶的队中有数字则直接返回，如果没有则到另一个队列中通过平移数字取出最后一个数字加入模拟栈顶的队列中
int myStackTop(MyStack *obj)
{
    if (link_queue_is_empty(obj->q2)) {
        for (int i = 0; i < link_queue_length(obj->q1) - 1; i++) {
            link_queue_enqueue(obj->q1, obj->q1->head->data);
            int data = 0;
            link_queue_dequeue(obj->q1, &data);
        }
        link_queue_enqueue(obj->q2, obj->q1->head->data);
        int data = 0;
        link_queue_dequeue(obj->q1, &data);
    }
    return obj->q2->head->data;
}

//当pop操作时，先执行下top()操作，保证模拟栈顶的队列中有数字，然后再将该数字移除即可
int myStackPop(MyStack *obj)
{
    myStackTop(obj);
    int data;
    link_queue_dequeue(obj->q2, &data);
    
    return data;
}

//当empty操作时，当两个队列都为空时，栈为空
bool myStackEmpty(MyStack *obj)
{
    return link_queue_is_empty(obj->q1) && link_queue_is_empty(obj->q2);
}

void myStackFree(MyStack *obj)
{
    link_queue_destroy(obj->q1);
    link_queue_destroy(obj->q2);
    free(obj);
}

void testStack()
{
    MyStack *stack = myStackCreate(5);
    myStackPush(stack, 1);
    myStackPush(stack, 2);
    myStackPush(stack, 3);
    myStackPush(stack, 4);
    
    while (!myStackEmpty(stack)) {
        int data = myStackPop(stack);
        printf("%d\n", data);
    }
}
方法二
  • 描述

每次把新加入的数插到前头，这样队列保存的顺序和栈的顺序是相反的，它们的取出方式也是反的，那么反反得正，就是我们需要的顺序了。我们需要一个辅助队列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
57
58
59
60
61
62
63
64
65
66
67
68
69
typedef struct
{
    LinkQueue *q1;
}MyStack;

MyStack *myStackCreate(int maxSize)
{
    MyStack *stack = (MyStack *)malloc(sizeof(MyStack));
    stack->q1 = link_queue_create();
    
    return stack;
}

void myStackPush(MyStack *obj, int x)
{
    LinkQueue *tmp = link_queue_create();
    while (!link_queue_is_empty(obj->q1)) {
        link_queue_enqueue(tmp, obj->q1->head->data);
        int data = 0;
        link_queue_dequeue(obj->q1, &data);
    }
    
    link_queue_enqueue(obj->q1, x);
    while (!link_queue_is_empty(tmp)) {
        link_queue_enqueue(obj->q1, tmp->head->data);
        int data = 0;
        link_queue_dequeue(tmp, &data);
    }
    
    free(tmp);
}

int myStackTop(MyStack *obj)
{
    return obj->q1->head->data;
}

int myStackPop(MyStack *obj)
{
    int data;
    link_queue_dequeue(obj->q1, &data);
    
    return data;
}

bool myStackEmpty(MyStack *obj)
{
    return link_queue_is_empty(obj->q1);
}

void myStackFree(MyStack *obj)
{
    link_queue_destroy(obj->q1);
    free(obj);
}

void testStack()
{
    MyStack *stack = myStackCreate(5);
    myStackPush(stack, 1);
    myStackPush(stack, 2);
    myStackPush(stack, 3);
    myStackPush(stack, 4);
    
    while (!myStackEmpty(stack)) {
        int data = myStackPop(stack);
        printf("%d\n", data);
    }
}

题目来源

Implement Stack using Queues

用队列实现栈

队列相关代码

数据结构-队