C语言-用栈实现队列_maxstacknum

用栈实现队列

1. 栈是先进后出的数据结构，队列是先进先出的数据结构，所以当往队列中插入数据时，可以直接入栈。只是队列中先插入的在队首，队列中先插入的在栈底。
2. 弹出队首的数据，实际就是删掉栈底的数据，直接删除不了，可以利用另一个辅助栈，将当前栈中数据全部依次弹出，并push到辅助栈中，这时当前栈的栈底元素就变成了辅助栈的栈顶元素，直接pop掉辅助栈的栈顶元素就行。
3. 队列从队首到队尾的元素始终是辅助栈栈顶到栈底+当前栈栈底到栈顶。辅助栈栈顶对应着队列队首，当前栈栈底对应队列队尾。这就说明当辅助栈不为空时，队列的pop,可以直接对辅助栈pop。当辅助栈为空时，就要将当前栈搬运到辅助栈再弹出。而入栈可以直接push当当前栈。
   4

typedef struct{
	int* data;
	int top;
}MyStack;

typedef struct{
	MyStack* stackPush;
	MyStack* stackPop;
}MyQueue;

#define maxQueueNum  100		//队列空间
MyQueue* myQueueCreate(){
	MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
	
	queue->stackPush = (MyStack*)malloc(sizeof(MyStack));
	queue->stackPop = (MyStack*)malloc(sizeof(MyStack));
	
	queue->stackPush->data = (int*)malloc(sizeof(int) * maxQueueNum);
	queue->stackPush->top = -1;
	
	queue->stackPop->data = (int*)malloc(sizeof(int) * maxQueueNum);
	queue->stackPop->top = -1;
	
	return queue;
}

//入队
void myQueuePush(MyQueue* obj){
	if((obj->stackPush->top + obj->stackPop->top) == maxStackNum - 2)	//队列空间满
		return ;
	obj->stackPush->data[++obj->stackPush->top] = x;
}

//出队
int myQueuePop(MyQueue* obj){
	if(obj->stackPop->top != -1){		//辅助栈不为空，直接弹出
		return obj->stackPop->data[obj->stackPop->top--];
	}
	while(obj->stackPush->top != -1){	//辅助栈为空，将当前栈依次弹出并压到辅助栈中
		obj->stackPop->data[++obj->stackPop->top] = obj->stackPush->data[obj->stackPush->top--];
	}
	if(obj->stackPop->top == -1){		//辅助栈仍为空，说明对应队列为空，无值返回
		return -1;
	}
	else
	{
		return obj->stackPop->data[obj->stckPop->top--];
	}
}

//取队首值
int myQueuePeek(MyQueue* obj){
	if((obj->stackPush->top == -1) && (obj->stackPop->top == -1))//队列为空
		return -1；

	if(obj->stackPop->top != -1){
		return obj->stackPop->data[obj->stackPop->top];
	}
	else
	{
		while(obj->stackPush->top != -1){
			obj->stackPop->data[++obj->stackPop->top] = obj->stackPush->data[obj->stackPush->top--];
		}
		return obj->stackPop->data[obj->stackPop->top];
	}
}

//判断队列是否为空
bool myQueueEmpty(MyQueue* obj){
	if((obj->stackPush->top == -1) && (obj->stackPop->top == -1))
		return true;
	else
		return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj->stackPush->data);
    free(obj->stackPop->data);
    free(obj->stackPush);
    free(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