LeetCode | 225. 用队列实现栈

LeetCode | 225. 用队列实现栈

OJ链接

• 此题可以用两个队列去实现一个栈，每次始终保持一个队列为空，
  入栈操作相当于给非空队列进行入队操作

• 入数据，把不为空的队列入

• 出数据，把不为空的队列数据导入为空，直到最后一个

• 出栈操作相当于非空队列的队尾元素出队，此时需要把非空队列除最后一个元素之外的其余元素入队到空队列，然后出队最后一个队尾元素

代码如下：

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;


void QueueInit(Queue* pq);//队列初始化
void QueueDestroy(Queue* pq);//销毁
void QueuePush(Queue* pq,QDataType x);//添加
void QueuePop(Queue* pq);//删除
QDataType QueueFront(Queue* pq);//头数
QDataType QueueBack(Queue* pq);//尾数
int QueueSize(Queue* pq);//个数
bool QueueEmpty(Queue* pq);//判断是否为空


void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}
void QueueDestroy(Queue* pq)//销毁
{
	assert(pq);
	while (pq->head !=NULL)
	{
		QueueNode* tmp = pq->head;
		pq->head = pq->head->next;
		free(tmp);
	}
	pq->head = pq->tail = NULL;
}
void QueuePush(Queue* pq, QDataType x)//添加
{
	assert(pq);
	QueueNode* NewNode = (QueueNode*)malloc(sizeof(QueueNode));
	NewNode->data = x;
	NewNode->next = NULL;
	if (pq->head ==NULL)
		pq->head = pq->tail=NewNode;
	else
	{
		pq->tail->next = NewNode;
		pq->tail = NewNode;
	}
}
void QueuePop(Queue* pq)//删除
{
	assert(pq);
	assert(pq->head);
	if (pq->head == pq->tail)
		pq->tail = NULL;
	QueueNode* tmp = pq->head->next;
	free(pq->head);
	pq->head = tmp;
	
}
QDataType QueueFront(Queue* pq)//头数
{
	assert(pq);
	assert(pq->head);
	return pq->head->data;
}
QDataType QueueBack(Queue* pq)//尾数
{
	assert(pq);
	assert(pq->tail);
	return pq->tail->data;
}
int QueueSize(Queue* pq)//个数
{
	assert(pq);
	int count = 0;
	QueueNode* tmp = pq->head;
	while (tmp != NULL)
	{
		count++;
		tmp = tmp->next;
	}
	return count;
}
bool QueueEmpty(Queue* pq)//判断是否为空
{
	if (QueueSize(pq) == 0)
		return true;
	else
		return false;
}
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack *obj=(MyStack*)malloc(sizeof(MyStack));
    QueueInit(&obj->q1);
    QueueInit(&obj->q2);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    Queue*cur=&obj->q1;//选出含有数据的队列
    if(!QueueEmpty(&obj->q2))
        cur=&obj->q2;
    QueuePush(cur,x);
}

int myStackPop(MyStack* obj) {
    Queue*cur1=&obj->q1;//有数据
    Queue*cur2=&obj->q2;//无数据
    if(!QueueEmpty(&obj->q2))
    {
        cur1=&obj->q2;
        cur2=&obj->q1;
    }
    while(cur1->head!=cur1->tail)
    {
        QueuePush(cur2,QueueFront(cur1));
        QueuePop(cur1);
    }
    int top=QueueFront(cur1);
    QueuePop(cur1);
    return top;
}

int myStackTop(MyStack* obj) {
        Queue*cur=&obj->q1;
    if(!QueueEmpty(&obj->q2))
        cur=&obj->q2;
    return QueueBack(cur);
}

bool myStackEmpty(MyStack* obj) {
    return (QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2));
}

void myStackFree(MyStack* obj) {
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(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