乐趣区

关于栈:栈和队列

jiezi

栈和队列

一、对于模仿栈应用何种模型

1. 程序表：尾插尾删很快，缓存利用率高，然而要扩容

2. 单链表：应用链表头作为栈顶来插入删除数据也很快

3. 带头双向循环链表：也能够，工夫也是 O(1)

二、栈的模仿实现 

//"stack.h"
typedef int type;
typedef struct stack
{
    type* a;
    int top;
    int capacity;
}st;
//stack.c
#include"stack.h"
void st_init(st* sta)
{assert(sta);
    sta->a = NULL;
    sta->top = 0;// 数组下标的意思，是数据下一个下标，外面没有值;top = -1, 则是 top 指向最初一个元素
    sta->capacity = 0;
}
void st_push(st* sta, type x)
{assert(sta);

    if (sta->top == sta->capacity)
    {
        // 满了
        int newcapa = sta->capacity == 0 ? 4 : 2 * sta->capacity;
        type* t = realloc(sta->a, sizeof(type) * newcapa);// 扩容；如果 a == NULL，它的行为就和 malloc 一样
        if (t == NULL)
        {printf("realloc fail\n");
            exit(-1);
        }
        sta->a = t;
        sta->capacity = newcapa;
    }

    sta->a[sta->top] = x;
    ++sta->top;
}
void st_destroy(st* sta)
{assert(sta);
    free(sta->a);
    sta->a = NULL;
    sta->top = 0;
    sta->capacity = 0;
}
void st_pop(st* sta)
{assert(sta);
    assert(sta->top > 0);
    sta->top--;
}
type st_top(st* sta)
{assert(sta);
    assert(sta->top > 0);

    return sta->a[sta->top - 1];
}
bool st_empty(st* sta)
{assert(sta);

    return sta->top == 0;
}
int st_size(st* sta)
{assert(sta);

    return sta->top; 
}

三、根底 oj

1. 无效的括号

https://leetcode.cn/problems/valid-parentheses/

给定一个只包含 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否无效。

无效字符串需满足：左括号必须用雷同类型的右括号闭合。左括号必须以正确的程序闭合。每个右括号都有一个对应的雷同类型的左括号。

思路：做括号入栈；有括号就和出栈的括号匹配 

bool isValid(string s) 
{if(s.size()%2 != 0 )return false;
    stack<char>st;
    for(auto x:s)
    {if(x == '(' || x=='[' ||x=='{')
            st.push(x);
        else
        {if(st.empty())return false;
            if(st.top() == '(' && x==')')
            {st.pop();
                continue;
            }
                
            else if(st.top() == '[' && x==']')
            {st.pop();
                continue;
            }
            else if(st.top() == '{' && x=='}')
            {st.pop();
                continue;
            }
            else 
                return false;
        }
    }
  if(st.empty()) 
      return true;
  return false; 
}

2. 栈的压入、弹出序列

https://www.nowcoder.com/exam/company?tag=581)

输出两个整数序列，第一个序列示意栈的压入程序，请判断第二个序列是否可能为该栈的弹出程序。假如压入栈的所有数字均不相等。例如序列 1,2,3,4,5 是某栈的压入程序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

bool IsPopOrder(vector<int> pushV,vector<int> popV) 
{
    stack<int>st;
    int j = 0;

    for(auto x:pushV)
    {st.push(x);

        while(!st.empty() && st.top() == popV[j])
        {st.pop();
            ++j;
        }
    }
    if(st.empty())
        return true;
    return false;
}

3. 用队列实现栈

https://leetcode.cn/problems/implement-stack-using-queues/

请你仅应用两个队列实现一个后入先出（LIFO）的栈，并反对一般栈的全副四种操作（push、top、pop 和 empty）

typedef int type;
struct queuenode
{
    struct queue* next;
    type data;
};
typedef struct queue
{
    struct queuenode* head;
    struct queuenode* tail;
}queue;
void queue_init(queue* q)
{assert(q);
    q->head = NULL;
    q->tail = NULL;
}
void queue_destroy(queue* q)
{assert(q);
    struct queuenode* cur = q->head;
    while (cur != NULL)
    {
        struct queuenode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = NULL;
}
void queue_push(queue* q, type x)
{assert(q);
    struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));
    newnode->data = x;
    newnode->next = NULL;
    
    if (q->head == NULL)
    {q->head = q->tail = newnode;}
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
void queue_pop(queue* q)
{assert(q);
    assert(q->head);

    if (q->head == q->tail)
    {free(q->head);
        q->head = q->tail = NULL;
    }
    else
    {
        struct queuenode* next = q->head->next;
        free(q->head);
        q->head = next;
    }
}
bool queue_empty(queue* q)
{assert(q);
    return q->head == NULL;
}
struct queuenode* buy_node(type x)
{struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));
    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}
type queue_back(queue* q)
{assert(q);
    assert(q->tail);
    return q->tail->data;
}
type queue_front(queue* q)
{assert(q);
    assert(q->head);
    return q->head->data;
}
int queue_size(queue* q)
{if (q->head == NULL)return 0;
    if (q->head == q->tail)return 1;
    struct queuenode* t = q->head;
    int count = 0;
    while (t != NULL)
    {
        ++count;
        t = t->next;
    }
    return count;
}
typedef struct 
{
    queue q1;
    queue q2;

} MyStack;


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

void myStackPush(MyStack* obj, int x) {if(!queue_empty(&obj->q1))
    {queue_push(&obj->q1, x);
    }
    else
    {queue_push(&obj->q2, x);
    }
}

int myStackPop(MyStack* obj) {
    queue* aempty = &obj->q1;
    queue* noempty = &obj->q2;

    if(!queue_empty(&obj->q1))
    {
        aempty = &obj->q2;
        noempty = &obj->q1;
    }

    while(queue_size(noempty)>1)
    {queue_push(aempty,queue_front(noempty));
        queue_pop(noempty);
    }
    int top = queue_front(noempty);
    queue_pop(noempty);
    return top;
}

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

}

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

}

void myStackFree(MyStack* obj) {queue_destroy(&obj->q1);
    queue_destroy(&obj->q2);
    free(obj);
}

4. 用栈实现队列

https://leetcode.cn/problems/implement-queue-using-stacks/

请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（push、pop、peek、empty）

typedef int type;
typedef struct stack
{
    type* a;
    int top;
    int capacity;
}st; 
typedef struct {
    st pushst;
    st popst;
} MyQueue;

void st_init(st* sta)
{assert(sta);
    sta->a = NULL;
    sta->top = 0;// 数组下标的意思，是数据下一个下标，外面没有值;top = -1, 则是 top 指向最初一个元素
    sta->capacity = 0;
}
void st_push(st* sta, type x)
{assert(sta);

    if (sta->top == sta->capacity)
    {
        // 满了
        int newcapa = sta->capacity == 0 ? 4 : 2 * sta->capacity;
        type* t = realloc(sta->a, sizeof(type) * newcapa);// 扩容；如果 a == NULL，它的行为就和 malloc 一样
        if (t == NULL)
        {printf("realloc fail\n");
            exit(-1);
        }
        sta->a = t;
        sta->capacity = newcapa;
    }

    sta->a[sta->top] = x;
    ++sta->top;
}
void st_destroy(st* sta)
{assert(sta);
    free(sta->a);
    sta->a = NULL;
    sta->top = 0;
    sta->capacity = 0;
}
void st_pop(st* sta)
{assert(sta);
    assert(sta->top > 0);
    sta->top--;
}
type st_top(st* sta)
{assert(sta);
    assert(sta->top > 0);

    return sta->a[sta->top - 1];
}
bool st_empty(st* sta)
{assert(sta);

    return sta->top == 0;
}
int st_size(st* sta)
{assert(sta);

    return sta->top; 
}
MyQueue* myQueueCreate() {MyQueue * q = (MyQueue*)malloc(sizeof(MyQueue));
    st_init(&q->popst);
    st_init(&q->pushst);

    return q;
}

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

int myQueuePop(MyQueue* obj) {if(st_empty(&obj->popst))
    {while(!st_empty(&obj->pushst))
        {st_push(&obj->popst, st_top(&obj->pushst));
            st_pop(&obj->pushst);
        }
    }
    type x = st_top(&obj->popst);
    st_pop(&obj->popst);
    return x;
}

int myQueuePeek(MyQueue* obj) {if(st_empty(&obj->popst))
    {while(!st_empty(&obj->pushst))
        {st_push(&obj->popst,st_top(&obj->pushst));
            st_pop(&obj->pushst);
        }
    }
    return st_top(&obj->popst);
}

bool myQueueEmpty(MyQueue* obj) {return st_empty(&obj->pushst) && st_empty(&obj->popst);

}

void myQueueFree(MyQueue* obj) {st_destroy(&obj->popst);
    st_destroy(&obj->pushst);
    free(obj);
}

5. 设计循环队列

https://leetcode.cn/problems/design-circular-queue/

设计你的循环队列实现。循环队列是一种线性数据结构，其操作体现基于 FIFO（先进先出）准则并且队尾被连贯在队首之后以造成一个循环。它也被称为“环形缓冲器”。

循环队列的一个益处是咱们能够利用这个队列之前用过的空间。在一个一般队列里，一旦一个队列满了，咱们就不能插入下一个元素，即便在队列后面仍有空间。然而应用循环队列，咱们能应用这些空间去存储新的值。

思路：无论是链表还是数组模仿，都须要空一个格子，来代表曾经满了的状况。head 和 tail 在同一地位时，代表队列为空。tail 的下一个地位是 head 代表队列曾经满了。要存 x 个数据，就须要 x + 1 的空间。

#include<stdbool.h>
typedef struct {
    int*a;
    int head;
    int tail;
    int k;
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* q = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    q->a = (int *)malloc(sizeof(int)* (k + 1));
    q->head = q->tail = 0;
    q->k = k;
    return q;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) {return obj->head == obj->tail;}

bool myCircularQueueIsFull(MyCircularQueue* obj) {return (obj->tail + 1)%(obj->k +1) == obj->head;
}
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {// 在队列中加数据
    if(myCircularQueueIsFull(obj))
        return false;
    obj->a[obj->tail] = value;
    obj->tail = (obj->tail + 1)%(obj->k + 1);
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))
        return false;
    obj->head = (obj->head + 1)%(obj->k + 1);
    return true;
}

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

int myCircularQueueRear(MyCircularQueue* obj) {if(myCircularQueueIsEmpty(obj))
        return -1;
    return obj->a[(obj->tail + obj-> k)%(obj->k + 1)];// 留神这里，(tail - 1 + k + 1)%(k + 1)，因为 tail- 1 会小于 0，所以须要加上数组长度
}
 
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->a);
    free(obj);
}

四、模仿队列应用的模型

如果应用数组的话，须要在数组头插入删除数据，效率低。所以这里应用单链表实现，并且保护它的尾指针。将队列的头指针和尾指针放入构造体，这样的话批改它们的时候就不须要传二级指针了，而只须要构造体的一级指针。

五、模仿实现队列 

//queue.h
typedef int type;
struct queuenode
{
    struct queue* next;
    type data;
};
// 将指针放在一个构造体中，这样批改他们时就不须要二级指针，而是只须要构造体的一级指针就能够了
typedef struct queue
{
    struct queuenode* head;
    struct queuenode* tail;
}queue;
//queue.c
#define _CRT_SECURE_NO_WARNINGS 1 
#include"queue.h"

void queue_init(queue* q)
{assert(q);
    q->head = NULL;
    q->tail = NULL;
}
void queue_destroy(queue* q)
{assert(q);
    struct queuenode* cur = q->head;
    while (cur != NULL)
    {
        struct queuenode* next = cur->next;
        free(cur);
        cur = next;
    }
    q->head = q->tail = NULL;
}
void queue_push(queue* q, type x)
{assert(q);
    struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));
    newnode->data = x;
    newnode->next = NULL;
    
    if (q->head == NULL)
    {q->head = q->tail = newnode;}
    else
    {
        q->tail->next = newnode;
        q->tail = newnode;
    }
}
void queue_pop(queue* q)
{assert(q);
    assert(q->head);

    if (q->head == q->tail)
    {free(q->head);
        q->head = q->tail = NULL;
    }
    else
    {
        struct queuenode* next = q->head->next;
        free(q->head);
        q->head = next;
    }
}
bool queue_empty(queue* q)
{assert(q);
    return q->head == NULL;
}
struct queuenode* buy_node(type x)
{struct queuenode* newnode = (struct queuenode*)malloc(sizeof(struct queuenode));
    newnode->data = x;
    newnode->next = NULL;

    return newnode;
}
type queue_back(queue* q)
{assert(q);
    assert(q->tail);
    return q->tail->data;
}
type queue_front(queue* q)
{assert(q);
    assert(q->head);
    return q->head->data;
}
int queue_size(queue* q)
{if (q->head == NULL)return 0;
    if (q->head == q->tail)return 1;
    struct queuenode* t = q->head;
    int count = 0;
    while (t != NULL)
    {
        ++count;
        t = t->next;
    }
    return count;
}
退出移动版