思路

不是非常熟练,这里就用一种简单的,用两个队列来辅助实现栈

对于队列:

1
2
3
1. 用head==rear==-1,来判断队列是否为空
2. 入队列的时候,如果为空先把head置为0,用循环队列表示,rear=(rear+1)%size;
3. 出队列的时候是吧head出出来, head=(head+1)%size;

对于双队列表示栈:

1
1. 用两个队列来表示栈,栈是后进先出,而队列是先进先出,想来就是出队列的最后一个就是栈出的第一个,实现的思路就是两个队列,要入栈的时候放在不空的那个队列里,要出栈的时候把有内容的队列出队列到另一个队列直到只剩一个,弹出这个就是栈的机制了

代码:

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
#define LEN 20
typedef struct queue{
    int *data;
    int head;
    int rear;
    int size;
}Queue;

typedef struct {
    Queue *queue1,*queue2;    
} MyStack;

Queue* initQueue(int k){
    Queue* obj=(Queue*)malloc(sizeof(Queue));
    obj->data=(int *)malloc(k*sizeof(int));
    obj->head=-1;
    obj->rear=-1;
    obj->size=k;
    return obj;
}

void enQueue(Queue* obj,int e){
    if(obj->head==-1){
        obj->head=0;
    }
    obj->rear=(obj->rear+1)%obj->size;
    obj->data[obj->rear]=e;
}

int deQueue(Queue* obj){
    int a=obj->data[obj->head];
    if(obj->head==obj->rear){
        obj->head=-1;
        obj->rear=-1;
        return a;
    }
    obj->head=(obj->head+1)%obj->size;
    return a;
}

int isEmpty(Queue * obj){
    return obj->head==-1;
}

MyStack* myStackCreate() {
    MyStack*obj=(MyStack*)malloc(sizeof(MyStack));
    obj->queue1=initQueue(LEN);
    obj->queue2=initQueue(LEN);
    return obj;
}

void myStackPush(MyStack* obj, int x) {
    if(isEmpty(obj->queue1)){
        enQueue(obj->queue2,x);
    }else{
        enQueue(obj->queue1,x);
    }
}

int myStackPop(MyStack* obj) {
    if(isEmpty(obj->queue1)){
        while(obj->queue2->head!=obj->queue2->rear){
            enQueue(obj->queue1,deQueue(obj->queue2));
        }
        return deQueue(obj->queue2);
    }
    while(obj->queue1->head!=obj->queue1->rear){
        enQueue(obj->queue2,deQueue(obj->queue1));
    }
    return deQueue(obj->queue1);
}


int myStackTop(MyStack* obj) {
    if (isEmpty(obj->queue1) && isEmpty(obj->queue2)) {
        return -1;
    }   
    if(isEmpty(obj->queue1)){
        return obj->queue2->data[obj->queue2->rear];
    }
    return obj->queue1->data[obj->queue1->rear];
}

bool myStackEmpty(MyStack* obj) {
    if (isEmpty(obj->queue1) && isEmpty(obj->queue2)) {
        return true;
    }
    else{
        return false;
    }
}

void myStackFree(MyStack* obj) {
    free(obj->queue1->data);
    obj->queue1->data=NULL;
    free(obj->queue1);
    obj->queue1=NULL;
    free(obj->queue2->data);
    obj->queue2->data=NULL;
    free(obj->queue2);
    obj->queue2=NULL;
    free(obj);
    obj=NULL;

}