用栈模拟实现队列(c语言版)_堆栈模拟队列

前言

用"栈实现队列",力扣中一道oj题,可以帮助刚接触"栈"和"队列"的新手更好的理解栈和队列这两种结构.

题目来源于力扣:
题目链接:https://leetcode.cn/problems/implement-queue-using-stacks/
难度:简单

一、队列的各接口:

1.1 类型的声明(MyQueue):

//模拟队列类型的声明
typedef struct {
    ST stackpush;		//用于模拟队列的 入队操作
    ST stackpop;		//用于模拟队列的 出队操作
} MyQueue;
1
2
3
4
5

这里是借助两个栈用于模拟队列.
①:stackpush 模拟队列的入队
②:stackpop 模拟队列的出队

1.2 初始化(myQueueCreate):

该队列是由两个栈实现的,所以重点关注两个栈的初始化即可.

步骤:

1. 申请两个栈大小的空间.
   申请失败时判断一下.
2. 对队列中的两个栈,一次调用他们的初始化函数.(这个千万别漏掉了,牛牛漏掉之后找了好久的问题)

//队列的初始化
MyQueue* myQueueCreate() {
	//给队列开辟空间
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("obj malloc fail");
    }
    //一定要记得这里要初始化(别漏掉了哦)
    InitST(&obj->stackpush);
    InitST(&obj->stackpop);
    return obj;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3 入队列(myQueuePush)

对于入队列的模拟实现很简单,只需要将数据压入栈(模拟入队列:stackpush)即可.

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    STPush(&obj->stackpush,x);
}
1
2
3
4

1.4 出队列(myQueuePop)

函数要求:
将队首元素出队,并且返回刚刚出队的队首元素.

模拟出队相对复杂一些.

1. 初始状态下或者stackpop(模拟出队的栈)数据出队列到空时,里面是没有数据的,所以先判断stackpop是否有数据.
   有数据:则直接获取stackpop的栈顶元素作为队首元素.
   无数据:将数据从模拟入队列栈全部倒过来.(倒数据)
2. 获取stackpop的栈顶元素作为队首元素,使用top变量记录下来.(因为后面要执行出栈操作).
3. 出栈(模拟出队列),并返回top变量.

int myQueuePop(MyQueue* obj) {
     assert(obj);
     if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列的栈)为空,则向栈(stackpush模拟入队列的栈)要数据
     {
     		//下面循环结束的条件是不为空
          while(!STEmpty(&obj->stackpush))//将数据从模拟入队列栈全部倒过来
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
     }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    STPop(&obj->stackpop);
    return top;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.5 队列的判空(myQueueEmpty)

当两个栈中都没有元素时,则队列为空.

//写法1

bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈
    {
        return true;
    }
    else 
    return false;
}
1
2
3
4
5
6
7
8

//写法2.

bool myQueueEmpty(MyQueue* obj) {
    return STEmpty(&obj->stackpush)	&&	STEmpty(&obj->stackpop);
}
1
2
3

1.6 返回队首元素(myQueuePeek):

1. stackpop不为空时,则队首元素就是stackpop的栈顶元素.
2. stackpop为空时,则队首元素就是stackpush的栈底元素.
   所以这里也需要倒数据.

int myQueuePeek(MyQueue* obj) {
    assert(obj);
    if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出队列)为空,则向栈(stackpush模拟入队列)要数据
     {
        while(!STEmpty(&obj->stackpush))
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出队列)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
    }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    return top;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

与myQueuePop(出队列)函数比较,此函数只是将队首元素返回,并没有指向pop出队操作.
所以我们在实现myQueuePop函数时可以复用一下myQueuePeek函数.

int myQueuePop(MyQueue* obj) {
    int top=myQueuePeek(obj);
    STPop(&obj->stackpop);
    return top;
}
1
2
3
4
5

1.7 队列的销毁(myQueueFree):

1. 释放两个栈初始化开辟的空间
2. 释放队列申请的空间.

void myQueueFree(MyQueue* obj) {
    STDestory(&obj->stackpush);
    STDestory(&obj->stackpop);
    free(obj);
}
1
2
3
4
5

二、总代码:

前面的代码是栈的实现,由于c语言不能像c++那样直接调用库.

typedef  int stacktype;

typedef struct stack//定义栈的类型
{
	stacktype* data;
	int top;
	int capacaity;
}ST;
void InitST(ST* ps);//初始化栈
void STPush(ST* ps, stacktype x);//压栈
void STPop(ST* ps);//出栈
bool STEmpty(ST* ps);//判断是否为空栈
stacktype STTop(ST* ps);//返回栈顶元素
void STDestory(ST* ps);//栈的销毁

void InitST(ST* ps)//初始化栈
{
	assert(ps);
	ps->top = -1;
	ps->capacaity = 4;
	ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype));

}

void STPush(ST* ps, stacktype x)//压栈
{
	assert(ps);
	if (ps->top+1 == ps->capacaity)
	{
		ps->capacaity *= 2;
		ST* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype));
		if(tmp == NULL)
		{
			printf("增容失败\n");
		}
		ps->data = tmp;
	}
	ps->top++;
	ps->data[ps->top] = x;
	
}


void STPop(ST* ps)//出栈
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}

bool STEmpty(ST* ps)//判断是否为空栈,是空返回真
{
	assert(ps);
	if (ps->top == -1)
	{
		return true;
	}
	return false;
}
stacktype STTop(ST* ps)//返回栈顶元素
{
	assert(ps);
	return ps->data[ps->top];
}
void STDestory(ST* ps)//销毁栈
{
	assert(ps);
	free(ps->data);
	ps->data = NULL;
	ps->top = -1;
	ps->capacaity = 0;
}


//模拟队列类型的声明
typedef struct {
    ST stackpush;
    ST stackpop;
} MyQueue;

//队列的初始化
MyQueue* myQueueCreate() {
    MyQueue* obj=(MyQueue*)malloc(sizeof(MyQueue));
    if(obj==NULL)
    {
        perror("obj malloc fail");
    }
    //一定要记得这里要初始化
    InitST(&obj->stackpush);
    InitST(&obj->stackpop);
    return obj;
}

void myQueuePush(MyQueue* obj, int x) {
    assert(obj);
    STPush(&obj->stackpush,x);
}

int myQueuePop(MyQueue* obj) {
     assert(obj);
     if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据
     {
          while(!STEmpty(&obj->stackpush))
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
     }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    STPop(&obj->stackpop);
    return top;
}


bool myQueueEmpty(MyQueue* obj) {
    if(STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop))//如果都为空,则为空栈
    {
        return true;
    }
    else 
    return false;
    //return STEmpty(&obj->stackpush)&&STEmpty(&obj->stackpop);
}

int myQueuePeek(MyQueue* obj) {
    if(STEmpty(&obj->stackpop))//如果栈(stackpop模拟出栈)为空,则向栈(stackpush模拟入栈)要数据
     {
        while(!STEmpty(&obj->stackpush))
        {
            //将栈(stackpush模拟入队)的栈顶元素依次压入栈(stackpop模拟出栈)
            STPush(&obj->stackpop,STTop(&obj->stackpush));
            STPop(&obj->stackpush);
        }
    }
    int top=STTop(&obj->stackpop);//记录用来模拟出队列的栈的栈顶元素;
    return top;
    //return STTop(&obj->stackpop);
}


void myQueueFree(MyQueue* obj) {
    STDestory(&obj->stackpush);
    STDestory(&obj->stackpop);
    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

运行结果: