【数据结构初阶-oj题】栈和队列的oj题（入门）

前言

栈会了，队列会了，这些也要会哦

栈和队列

题1 用队列实现栈

• 队列实现栈只有一个问题：
  • 尾删
• 咱们有两个队列，就可以采用 “多链表操作”
  • 把前面的 n-1 个数据 倒进另一空链表，留下最后一个元素
  • QueuePop即使是头删，删的也是“最后一个元素”了

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) 
{
    if(!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1, x);
    else
        QueuePush(&obj->q2, x);    
}

int myStackPop(MyStack* obj) 
{
    int top = 0;
    if(!QueueEmpty(&obj->q1))
    {
        while(QueueSize(&obj->q1) > 1)
        {
            QueuePush(&obj->q2, QueueFront(&obj->q1));
            QueuePop(&obj->q1);
        }
        top = QueueFront(&obj->q1);
        QueuePop(&obj->q1);
        return top;
    }
    else
    {
        while(QueueSize(&obj->q2) > 1)
        {
            QueuePush(&obj->q1, QueueFront(&obj->q2));
            QueuePop(&obj->q2);
        }
        top = QueueFront(&obj->q2);
        QueuePop(&obj->q2);
        return top;
    }
}

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

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

void myStackFree(MyStack* obj) 
{
    QNode* cur1 = obj->q1.head;
    QNode* cur2 = obj->q2.head;
    while(cur1)
    {
        QNode* del = cur1;
        cur1 = cur1->next;
        free(del);
    }
    while(cur2)
    {
        QNode* del = cur2;
        cur2 = cur2->next;
        free(del); 
    }
    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

• 全程注意保持一个队列为空，用来倒数据
• 所谓实现，只要符合准则（LIFO），能够实现功能就行
• myStackCreate：此处要求在接口内创建myStack并返回
• myStackPush：直接入到非空队列
• myStackPop：把 n-1 个数据倒进空队列，再Pop并返回原非空队列的Front
• myStackTop：栈是后进先出，所有返回非空队列的Back
• myStackEmpty：myStack由两个Queue组成，两个Queue都空，myStack也空
• myStackFree：队列由链表实现，要遍历释放

来源：leetcode-225.

题2 用栈实现队列

• 用栈实现队列，有如下问题:

  • 头插
  • 获取队头（栈只能获取队尾）

• 从栈和队列的原则入手：

  • 先进后出
  • 先进先出

• 把一个栈的元素全部入到另一个，发现逆序了

  • 逆序后，栈的尾删 StackPop(popST) 就变成 队列头删 了！
  • 同理，获取队头也就是获取栈顶！

  尾删 逆序 就是头删

  栈顶 逆序 就是栈底

typedef struct 
{
    ST pushST;
    ST popST;
} MyQueue;


MyQueue* myQueueCreate() 
{
    MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue));

    StackInit(&obj->pushST);
    StackInit(&obj->popST);

    return obj;
}

void PushST2PopST(MyQueue* obj)
{
   if(StackEmpty(&obj->popST))
    {
        while(!StackEmpty(&obj->pushST))
        {
            StackPush(&obj->popST, StackTop(&obj->pushST));
            StackPop(&obj->pushST);
        }
    }
}

void myQueuePush(MyQueue* obj, int x) 
{
    StackPush(&obj->pushST, x);
}

int myQueuePop(MyQueue* obj) 
{
    PushST2PopST(obj);

    int front = StackTop(&obj->popST);
    StackPop(&obj->popST);

    return front;
}

int myQueuePeek(MyQueue* obj) 
{
    PushST2PopST(obj);

    return StackTop(&obj->popST);
}

bool myQueueEmpty(MyQueue* obj) 
{
    return StackEmpty(&obj->pushST) && StackEmpty(&obj->popST);
}

void myQueueFree(MyQueue* obj) 
{
    free((obj->pushST).arr);
    free((obj->popST).arr);
    free(obj);

    obj = NULL;
}
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

• pushST 是专门用来入栈（入队列）的栈，popST是专门用来出栈（出队列）的栈

• 头删：pop 掉 popST 的栈顶

  • 如果 popST 空了，就到 pushST 取，完全不影响

• 获取队头：直接取 popST 的栈顶

  • 如果 popST 空了，就到 pushST取，完全不影响

• void PushST2PopST() 就是专门用来传数据的

题3 循环队列

：设计某种数据结构时，要考虑设计的结构方不方便实现需要的接口

• 因为数组头删效率低，所以先前的队列都是用链表实现；但此处的循环队列头删不需要删除元素，只需要 头指针往下走

  所以，循环队列用数组和链表都可以。那用哪个？

• 得从接口实现的效率和简单程度入手——循环队列的接口：

  • 出队：
    • 数组：front往后走
    • 链表：front往后走
  • 入队：
    • 数组：back往后走
    • 链表：back往后走
  • 判空：
    • 数组：…
    • 链表：…
  • 判满：
    • 数组：…
    • 链表：…

  不对啊，判空这里出问题了：判满和判空都是 return front == back ？？咋整？

  • 判空判满 方法1：循环队列结构体内定义size，capacity

    

  • 判空判满 方法2：既然判空和判满重合，那我们让 空 和 满 的 front 和 back 不一样不就好了！

    ：多开辟一个空间，结构体内定义一个 N（arr要开辟的元素个数） ，并在初始化接口中 赋值为 k+1

    • 数组

      • 

      • 空：front = back

      • 满：back + 1 = front

      • 警惕！如果用这里对下标进行 + 的操作了！很可能越界，所以实现的时候要检查下标合法性

    • 链表

      • 

      • 空：front = back

      • 满： back->next = front

  • 获取队头：

    • 数组：arr[0]
    • 链表：head->val

  • 获取队尾

    • 数组：arr[back - 1]？很可能越界！ arr[ (back - 1 + N) % N ] 才是正解——

      • 

      • % N 可以得到 0 ~ N-1 的数

    • 链表：不好取，除非搞个带头/双向，但这样进一步增加结构的复杂程度
      • 

分析到这里，用数组实现，虽然逻辑结构看起来没链表清晰，但是实际实现起来，还是数组更方便。
方法2：开辟额外空间

typedef struct 
{
    int* arr;
    int front;//队头
    int back;//队尾的下一位置
    int N;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));

    obj->N = k+1;
    obj->arr = (int*)malloc(sizeof(int) * obj->N);
    obj->front = obj->back = 0;
    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
    if(obj->back == obj->front)
        return true;
    else
        return false;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    if((obj->back + 1 + obj->N) % obj->N == obj->front)
        return true;
    else
        return false;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
    {
        return false;
    }

    obj->arr[obj->back] = value;
    obj->back++;
    obj->back %= obj->N;

    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
    {
        return false;
        
    }
    obj->front++;
    obj->front %= obj->N;

    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[obj->front];
}


int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->arr[(obj->back-1 + obj->N) % obj->N];
}


void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->arr);
    obj->arr = NULL;
    free(obj);
    obj = NULL;
}
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

方法1 ：封装size 和 capacity

typedef struct 
{
    int* arr;
    int front;
    int back;
    int size;
    int capacity;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) 
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    obj->arr = (int*)malloc(sizeof(int)*k);
    obj->front = obj->back = obj->size = 0;
    obj->capacity = k;

    return obj;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{   
    return obj->size == 0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
    return obj->size == obj->capacity;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
    if(myCircularQueueIsFull(obj))
        return false;

    obj->arr[obj->back] = value;
    obj->back++;
    obj->back %= obj->capacity;
    obj->size++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return false;

    obj->front++;
    obj->front %= obj->capacity;
    obj->size--;
    
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->arr[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
    if(myCircularQueueIsEmpty(obj))
        return -1;
    else
        return obj->arr[(obj->back - 1 + obj->capacity) % obj->capacity];
}


void myCircularQueueFree(MyCircularQueue* obj) 
{
    free(obj->arr);
    obj->arr = NULL;
    free(obj);
    obj = NULL;
}

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

---

本期分享就到这啦，不足之处望请斧正

培根的blog，和你共同进步！