栈

ADT

Note

ADT 栈(stack) Data

stack是一种先进后出(First In Last Out,FILO)或者后进先出(Last In First Out,LIFO)的数据结构,他只有一个出口 栈只有顶端元素才能被外界使用，因此栈不允许遍历

Operation

push():入栈 pop():出栈 top():返回栈顶元素 isemtpy():是否为空 size():返回元素个数

endADT

具体实现

栈体

• 顺序栈

typedef struct
{
    int top;
    elem Stack_data[NUMBER];
}Stack;

• 链栈

typedef struct
{
    int top;
    elem data;
    Stack* next;
}Stack;

初始化

void InitStack(Stack* S)
{
    S->top = -1;
    S->data = {NULL};
    //S->next = NULL;
}

void InitStack(Stack *S)
{
	
}

出入栈

• 出栈

void pop(Stack* S)
{
    if(S->top == -1)
    {
        printf("error");
        return;
	}
    S->data[S->top] = NULL;
    S->top--;
    /*S->data[(S->top)--] = NULL;*/
}

• 入栈

void push(Stack* S, elem data)
{
    if(S->top == NUMBER - 1)
    {
        printf("overflow");
        return;
    }
    S->top++;
	S->data[S->top] = data;
    /*S->data[++(S->top)] = data;*/
}

返回栈顶元素

int top(Stack* S)
{
    return S->data[S->top];
}

是否为空

bool isEmpty(Stack* S)
{
    if(S->top == -1)
    {
        return true;
    }
    return false;
}

元素个数

int size(Stack* S)
{
    return S->top + 1;
}

特殊操作

反转字符串

title:栈反转
 
因为栈本身就是先入后出，因此栈反转字符串或链表很简单

void Reverse(char ch[], int n)
{
    Stack S;
    for(int i = 0; i < n; i++)
    {
        S.push(ch[i]);
    }
    for(int i = 0; i < n; i++)
    {
        ch[i] = S.top();
        S.pop();
    }
}
 
Reverse(string, strlen(string));

括号匹配

bool CheckBalancedParenthesis(string exp)
{
	stack<char> s;
	for(int i = 0; i < exp.length(); i++)
	{
		if(exp[i] == '(' || exp[i] == '[' || exp[i] == '{')
		{
			s.push(exp[i]);
		}
		else
		{
			if(s.empty())
			{
				return false;
			}
 
			char topElem = s.top();
			s.pop();
			if(exp[i] == ')' && topElem != '(')
				return false;
			if(exp[i] == ']' && topElem != '[')
				return false;
			if(exp[i] == '}' && topElem != '{')
				return false;
		}
	}
	return s.empty();
}

逆波兰式

int EvaluatePostfix(char exp[])
{
    Stack* st;
    InitStack(st);
    for(int i = 0; i < strlen(exp) - 1; i++)
    {
        if(exp[i] >= '0' && exp[i] <= '9')
        {
            push(st, exp[i]);
        }
        else if(exp[i] == operator)
        {
            int oprand1, oprand2;
            int res;
            oprand1 = pop(st);
            oprand2 = pop(st);
            res = Perform(exp[i], oprand1, oprand2);//计算结果函数
            push(res);
        }
    }
    return top(st);
}

中缀表达式转后缀表达式

char* infixToProfix(char exp[i])
{
    Stack* st;
    char *res = NULL;
    for(int i = 0; i < strlen(exp) - 1; i++)
    {
        if(exp[i] >= '0' && exp[i] <= '9')
        {
            push(st, exp[i]);
        }
        else
        {
            if(exp[i] == operator)
            {
                while((!isEmpty(st)) && hasHigherPrec(top(st), exp[i])/*是否有更高级的操作符*/)
                {
                    res = res + top(st);//字符串结尾加
                    s.pop();
                }
                push(st, exp[i]);
            }
        }
    }
    while(!isEmpty(st))
    {
        res = res + top(st);
        pop(st);
    }
    return res;
}

没有考虑括号,可结合括号匹配判断

括号匹配进阶(含括号的表达式匹配)

卡特兰数

n种不同元素进栈，出战元素不同排列个数为$\frac{1}{n+1}{C}_{2n}^n$