0%

Stack and Queue (Part 1)

發表於 2024-09-29 分類於 dataStructure
文章字數： 7.4k 所需閱讀時間 ≈ 14 分鐘

Introduction

有了動態陣列之後，堆疊與佇列就可以被實作出來了。堆疊的基本概念是先進去的後出來，就像疊好的盤子。佇列則相反，先進去的會先出來，就像一群在排隊的人。

Stack

首先我們先來實作堆疊，你會發現，只要利用上次的push_back以及pop_back就可以很方便的做出堆疊的結構。

Template for your program

#include <iostream>
#include <vector>

struct Stack {
    std::vector<int> values;
    Stack& push(int value);
    Stack& pop();
    int top();
    int size();
};

Stack& Stack::push(int value) {
    // your code below

    // your code above
    return *this;
}

Stack& Stack::pop() {
    // your code below

    // your code above
    return *this;
}

int Stack::top() {
    // your code below

    // your code above
    return -1;
}

int Stack::size() {
    return values.size();
}

const int PUSH{1};
const int POP{2};
const int TOP{3};

int main(void) {
    int operation_num;
    std::cin >> operation_num;

    Stack st;
    for (int i{0}; i < operation_num; ++i) {
        int op, value;
        std::cin >> op;
        switch (op) {
        case PUSH:
            std::cin >> value;
            st.push(value);
            std::cout << st.size() << "\n";
            break;
        case POP:
            st.pop();
            break;
        case TOP:
            std::cout << st.top() << "\n";
            break;
        }
    }
}

Usage of Stack

Evaluation of Arithmetic expression

https://zerojudge.tw/ShowProblem?problemid=a017

My answer written in C.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>

#define LEN 131072
#define OP 1
#define NUM 2

typedef struct token {
    int64_t type, val;
} Token;

typedef struct stack {
    Token *val;
    int sz, base, top;
} Stack;

Stack NewStack(int sz);
void Rebase(Stack*);
void Push(Stack*, Token val);
void Pop(Stack*);
Token Top(Stack*);
void Delete(Stack*);

int64_t InfixToSufix(char [], Token []);
Token PostfixEval(Token [], int64_t);

int main(void) {
    char infix[LEN] = {0};
    Token postfix[LEN] = {0};
    while(fgets(infix, LEN, stdin) != NULL) {
        int64_t post_sz = InfixToSufix(infix, postfix);
        printf("%lld\n", PostfixEval(postfix, post_sz).val);
    }
}

// Create a new stack. 
// 
// Where sz means size
Stack NewStack(int sz) {
    Stack new_stack;
    new_stack.sz = sz;
    new_stack.base = 1;
    while(new_stack.base < new_stack.sz) {
        new_stack.base <<= 1;
    }
    new_stack.val = (Token*) calloc(new_stack.base, sizeof(Token));
    new_stack.top = -1;
    return new_stack;
}

void Rebase(Stack* st) {
    (st->base) <<= 1;
    Token *new_val = (Token*) calloc(st->base, sizeof(Token));
    for(int i = 0; i < st->sz; ++i) {
        new_val[i] = st->val[i];
    }
    free(st->val);
    st->val = new_val;
}

void Push(Stack *st, Token val) {
    if(st->top >= st->sz - 1) {
        st->sz++;
        if(st->sz >= st->base) {
            Rebase(st);
        }
    }
    st->top++;
    st->val[st->top] = val;
}

void Pop(Stack *st) {
    assert(st->top >= 0);
    st->top--;
}

Token Top(Stack *st) {
    assert(st->top >= 0);
    return st->val[st->top];
}

void Delete(Stack *st) {
    free(st->val);
}

int64_t InfixToSufix(char infix[], Token postfix[]) {
    Stack st = NewStack(16);
    int64_t prior[128] = {0};
    prior['+'] = prior['-'] = 1;
    prior['*'] = prior['/'] = prior['%'] = 2;

    int64_t inf_idx = 0, post_idx = 0;
    while(infix[inf_idx] != '\0' && infix[inf_idx] != '\n') {
        char token = infix[inf_idx];
        inf_idx++;
        if(token == ' ') {
            continue;
        } else if(isdigit(token)) {
            int64_t tp = 0;
            while(isdigit(token)) {
                // printf("%c", token);
                tp = (tp << 3) + (tp << 1) + (token - '0');
                token = infix[inf_idx];
                inf_idx++;
            }
            postfix[post_idx].type = NUM;
            postfix[post_idx].val = tp;
            post_idx++;
        }
        if(token == '\0' || token == '\n') break;
        if(token == ' ') continue;
        if(token == '(') {
            Token tok = {OP, '('};
            Push(&st, tok);
        } else if(token == ')') {
            while(st.top >= 0 && Top(&st).val != '('){
                // printf("%c", (char)Top(&st).val);
                postfix[post_idx++] = Top(&st);
                Pop(&st);
            }
            Pop(&st);
        } else {
            while(st.top >= 0 && prior[Top(&st).val] >= prior[token]) {
                // printf("%c", (char)Top(&st).val);
                postfix[post_idx++] = Top(&st);
                Pop(&st);
            }
            Token tok = {OP, token};
            Push(&st, tok);
        }
    }
    while(st.top >= 0) {
        // printf("%c", (char)Top(&st).val);
        postfix[post_idx++] = Top(&st);
        Pop(&st);
    }
    // printf("=");
    Delete(&st);
    return post_idx;
}

int64_t Add(int64_t a, int64_t b) {
    return a + b;
}

int64_t Sub(int64_t a, int64_t b) {
    return a - b;
}

int64_t Mul(int64_t a, int64_t b) {
    return a * b;
}

int64_t Div(int64_t a, int64_t b) {
    return a / b;
}

int64_t Mod(int64_t a, int64_t b) {
    return a % b;
}

Token PostfixEval(Token postfix[], int64_t post_sz) {
    if(post_sz == 0) {
        Token ret = {NUM, 0};
        return ret;
    }
    Stack st = NewStack(16);
    int64_t op_to_idx[128];
    op_to_idx['+'] = 0;
    op_to_idx['-'] = 1;
    op_to_idx['*'] = 2;
    op_to_idx['/'] = 3;
    op_to_idx['%'] = 4;

    int64_t (*op[5])(int64_t, int64_t) = {Add, Sub, Mul, Div, Mod};
    
    for(int64_t post_idx = 0; post_idx < post_sz; ++post_idx) {
        Token token = postfix[post_idx];
        if(token.type == NUM) {
            Push(&st, token);
        } else {
            Token a = Top(&st);
            Pop(&st);
            Token b = Top(&st);
            Pop(&st);
            Token push = {NUM, op[op_to_idx[token.val]](b.val, a.val)};
            Push(&st, push);
        }
    }
    Token ret = Top(&st);
    Delete(&st);
    return ret;
}

Home but not work

單調對列
模擬遞迴