棧和隊列 Detail - 棧,隊列,數據結構月亮給蒙娜麗莎 Blog

棧和隊列

一、關於模擬棧使用何種模型

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;
}

月亮給蒙娜麗莎 Blog

@yuelianggeimengnalisha

Tags

數據結構 (48)

隊列 (24)

c++11 (23)

棧 (7)

指針 (2)

Stories

棧和隊列 - Stories Detail

棧和隊列

Add a new Comments