用队列实现栈 <难度系数⭐>

发表于

「这是我参与11月更文挑战的第9天，活动详情查看：2021最后一次更文挑战」

📝 题述：请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

1️⃣ void push(int x) 将元素 x 压入栈顶。

2️⃣ int pop() 移除并返回栈顶元素。

3️⃣ int top() 返回栈顶元素。

4️⃣ boolean empty() 如果栈是空的，返回 true ；否则，返回 false

⚠ 注意

1️⃣ 你只能使用队列的基本操作——也就是push to back、peek/pop from front、size和is empty这些操作。

2️⃣ 你所使用的语言也许不支持队列。你可以使用list (列表) 或者deque (双端队列) 来模拟一个队列，只要是标准的队列操作即可。

💨 示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”] - 调用函数接口简称
[[], [1], [2], [], [], []] - 参数

输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

🍳 提示

1️⃣ 1 <= x <= 9

2️⃣ 最多调用100 次 push、pop、top 和 empty

3️⃣ 每次调用 pop 和 top 都保证栈不为空

⚜ 进阶
你能否实现每种操作的均摊时间复杂度为 O(1) 的栈？换句话说，执行 n 个操作的总时间复杂度 O(n) ，尽管其中某个操作可能需要比其他操作更长的时间。你可以使用两个以上的队列。

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：队列的数据是不能从队尾出的，只能从队头出，而这里要实现的是队列实现栈，所以只能遵循栈的特性——后进先出。这里就需要另外一个队列，具体步骤如下：

1、一个队列有数据，一个队列没数据

2、入数据时向不为空的那个入

3、出数据时，就将不为空的队列的前 size-1 个拷贝至另一个队列，然后再Pop掉剩下的一个数据

leetcode原题

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
c复制代码//声明
    //结构体
typedef int QDataType;
typedef struct QueueNode
{
    struct QueueNode* next; //指向下一个节点
    QDataType data; //存储整型数据
}QueueNode;

typedef struct Queue
{
    QueueNode* phead;//头指针
    QueueNode* ptail;//尾指针
}Queue;

    //函数
void QueueInit(Queue* pq); 
void QueuePush(Queue* pq, QDataType x);	
bool QueueEmpty(Queue* pq);
void QueuePop(Queue* pq);
QDataType QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
void QueueDestory(Queue* pq);
//函数实现
void QueueInit(Queue* pq)
{
    assert(pq);
    //把2个指针置空
    pq->phead = pq->ptail = NULL;
}
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    //malloc空间,如果需要频繁的开辟空间建议再实现一个BuyQueueNode用于malloc
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newnode == NULL)
    {
	printf("malloc fail\n");
	exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    //第一次插入
    if (pq->phead == NULL)
    {
	pq->phead = pq->ptail = newnode;
    }
    //非第一次插入
    else
    {
	pq->ptail->next = newnode;
	pq->ptail = newnode;
    }
}
bool QueueEmpty(Queue* pq)
{
    assert(pq);
    //空链表返回true，非空链表返回false
    return pq->phead == NULL;
}
void QueuePop(Queue* pq)
{
    assert(pq);
    //链表为空时不能删除
    assert(!QueueEmpty(pq));
    //只有一个节点的情况
    if (pq->phead->next == NULL)
    {
	free(pq->phead);
	pq->phead = pq->ptail = NULL;
    }
    //多个节点的情况
    else
    {
	QueueNode* next = pq->phead->next;
	free(pq->phead)	;
	pq->phead = next;
    }
}
QDataType QueueSize(Queue* pq)
{
    assert(pq);
    //如果需要频繁的调用QueueSize这个接口，可以在Queue这个结构体中增加一个成员用于记录长度
    int sz = 0;
    QueueNode* cur = pq->phead;
    while (cur)
    {
	sz++;
	cur = cur->next;
    }
    return sz;
}
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    //链表为空时不能取头
    assert(!QueueEmpty(pq));

    return pq->phead->data;
}
QDataType QueueBack(Queue* pq)
{
    assert(pq);
    //链表为空时不能取尾
    assert(!QueueEmpty(pq));

    return pq->ptail->data;
}
void QueueDestory(Queue* pq)
{
    assert(pq);
	
    QueueNode* cur = pq->phead;
    //遍历链表
    while (cur)
    {
	QueueNode* next = cur->next;
	free(cur);
	cur = next;
    }
    pq->phead = pq->ptail = NULL;
}

typedef struct 
{
    Queue q1;
    Queue q2;
} MyStack;

/** Initialize your data structure here. */

MyStack* myStackCreate() 
{
    //malloc空间
    MyStack* pst = (MyStack*)malloc(sizeof(MyStack));
    //Init两个队列
    QueueInit(&pst->q1);
    QueueInit(&pst->q2);
    return pst;
}

/** Push element x onto stack. */
void myStackPush(MyStack* obj, int x) 
{
    assert(obj);
    //QueueEmpty为空时返回true，不为空时返回false
        //往不为空的那个队列里插入数据(q1不为空往q1插入，q2不为空往q2插入)
    if(!QueueEmpty(&obj->q1))
    {
        QueuePush(&obj->q1, x);
    }
    else
    {
        QueuePush(&obj->q2, x);
    }
}

/** Removes the element on top of the stack and returns that element. */
int myStackPop(MyStack* obj) 
{
    assert(obj);
    //先默认q1为空，q2不为空
    Queue* emptyQ = &obj->q1;
    Queue* nonemptyQ = &obj->q2;
    //q1不为空，重新赋值
    if(!QueueEmpty(&obj->q1))
    {
        emptyQ = &obj->q2;
        nonemptyQ = &obj->q1;
    }
    //拷贝 - 将非空队列的size-1个数据拷贝
    while(QueueSize(nonemptyQ) > 1)
    {
        //将非空的队列拷贝至空的队列
        QueuePush(emptyQ, QueueFront(nonemptyQ));
        //删除迭代
        QueuePop(nonemptyQ);
    }
    //top记录非空队列的剩下一个值
    int top = QueueFront(nonemptyQ);
    //删除非空队列的剩下一个数据，这个数据就是栈顶的数据
    QueuePop(nonemptyQ);
    //返回
    return top;
}

/** Get the top element. */
int myStackTop(MyStack* obj) 
{
    assert(obj);
    //q1不为空，取q1的数据
    if(!QueueEmpty(&obj->q1))
    {
        return QueueBack(&obj->q1);
    }
    //q2不为空，取q2的数据
    else
    {
        return QueueBack(&obj->q2);
    }
}

/** Returns whether the stack is empty. */
bool myStackEmpty(MyStack* obj) 
{
    assert(obj);
    //q1和q2一定有一个为空
    //q1为空返回真，q2为空返回真，mystackEmpty为空返回真;
    //q1为空返回真，q2为非空返回假，myStackEmpty为非空，返回假
    //q1为非空返回假，q2为空返回真，myStackEmpty为非空，返回假
    return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}

void myStackFree(MyStack* obj) 
{
    assert(obj);
    //结合上面的代码分析我们需要回收两个队列和myStackcreate里malloc的空间
    QueueDestory(&obj->q1);
    QueueDestory(&obj->q2);

    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%