LeetCode 232.用栈实现队列_leetcode232

题目描述

232.用栈实现队列-力扣(LeetCode)

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

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

示例1

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路分析：

此题思路和用队列实现栈思路类似
用栈（先进后出）实现队列（先进先出），我们可以用两个栈来实现，一个栈(Stack PushSt)用来实现队列的入数据，当需要实现出队列时，只需将Stack PushSt中的所有数据导入另一个空栈(Stack PopSt)中，然后直接出栈就可实现队列先进先出

图解如下：

代码实现

typedef int STDataType;
typedef struct Stack
{
	STDataType* a;//动态数组
	int top;  //栈顶
	int capacity;  //容量
}Stack;
//初始化栈
void StackInit(Stack* pst);
//销毁栈
void StackDestroy(Stack* pst);
//入栈
void StackPush(Stack* pst, STDataType data);
//出栈
void StackPop(Stack* pst);
//获取栈中有效元素的个数
int StackSize(Stack* pst);
//获取栈顶元素
STDataType StackTop(Stack* pst);
//检测栈是否为空，为空返回1，非空返回0
int StackEmpty(Stack* pst);
//初始化栈
void StackInit(Stack* pst)
{
	assert(pst);
	pst->a = (STDataType*)malloc(sizeof(STDataType)* 4);
	if (pst->a == NULL)
	{
		printf("malloc fail");
	}
	pst->top = 0;
	pst->capacity = 4;
}
//销毁栈
void StackDestroy(Stack* pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}
//入栈
void StackPush(Stack* pst, STDataType data)
{
	assert(pst);
	//空间不够需要增容
	if (pst->top == pst->capacity)
	{
		//增容为原来的2倍
		int* tem = (STDataType*)realloc(pst->a, sizeof(STDataType)* pst->capacity * 2);
		if (tem == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		pst->a = tem;
		pst->capacity = pst->capacity * 2;
	}
	pst->a[pst->top] = data;
	pst->top++;
}
//出栈
void StackPop(Stack* pst)
{
	assert(pst);
	//判断栈是否为空
	//相当于assert(pst->top != 0);
	assert(!StackEmpty(pst));
	pst->top--;
}
//获取栈中有效元素的个数
int StackSize(Stack* pst)
{
	assert(pst);
	//因为初始化top是0,如果初始化top是-1则返回top+1;
	return pst->top;
}
//获取栈顶元素
STDataType StackTop(Stack* pst)
{
	assert(pst);
	assert(!StackEmpty(pst));
	return pst->a[pst->top - 1];
}
//检测栈是否为空，为空返回1，非空返回0
int StackEmpty(Stack* pst)
{
	assert(pst);
	return pst->top == 0 ? 1 : 0;
}

typedef struct {
    Stack PushSt;
    Stack PopSt;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));
    StackInit(&pst->PushSt);
    StackInit(&pst->PopSt);
    return pst;
}

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

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    //若PopSt为空则把PushSt中的数据全部导入
    if(StackEmpty(&obj->PopSt))
    {
        while(!StackEmpty(&obj->PushSt))
        {
            StackPush(&obj->PopSt,StackTop(&obj->PushSt));
            StackPop(&obj->PushSt);
        }
    }
    //保存队头数据，返回
    int Top = StackTop(&obj->PopSt);
    StackPop(&obj->PopSt);
    return Top;
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
        //若PopSt为空则把PushSt中的数据全部导入
    if(StackEmpty(&obj->PopSt))
    {
        while(!StackEmpty(&obj->PushSt))
        {
            StackPush(&obj->PopSt,StackTop(&obj->PushSt));
            StackPop(&obj->PushSt);
        }
    }
    return StackTop(&obj->PopSt);
}

/** Returns whether the queue is empty. */
bool myQueueEmpty(MyQueue* obj) {
    return StackEmpty(&obj->PushSt) && StackEmpty(&obj->PopSt);
}

void myQueueFree(MyQueue* obj) {
    StackDestroy(&obj->PushSt);
    StackDestroy(&obj->PopSt);
    free(obj);
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);
 
 * int param_2 = myQueuePop(obj);
 
 * int param_3 = myQueuePeek(obj);
 
 * bool param_4 = myQueueEmpty(obj);
 
 * myQueueFree(obj);
*/
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