栈的定义及实现(C语言)

1.1 栈的定义和特点

栈：只能在表尾插入或删除元素的线性表

栈顶(top)：线性表的表尾

栈底(bottom)：线性表的表头

操作原则：后进先出原则(LIFO)

1.2 栈的操作

创建栈 Init_Stack()

添加元素 push()

删除元素 pop()

获取栈顶元素 top()

获取栈实际长度 size()

1.3 顺序栈的实现

1.3.1 定义一个栈结构体
1
2
3
4
typedef struct stack{
    int *elem;
    int length;
}stack;
1.3.2 初始化
1
2
3
4
5
void Init_Stack(stack &sq){
    sq.elem = (int*)malloc(sizeof(int) * stack_size);
    sq.length = 0;
    cout << "初始化成功" << endl;
}
1.3.3 将元素压入栈
1
2
3
4
5
void push(stack &sq,int elem){
    if(sq.length >= stack_size) return;
    sq.elem[sq.length] = elem;
    sq.length++;
}
1.3.4 将元素弹出栈
1
2
3
4
5
6
7
void pop(stack &sq){
    if(sq.length <= 0){
        return;
    }
    sq.elem[sq.length-1] = 0;
    sq.length--;
}
1.3.5 获取栈顶元素
1
2
3
int  top(stack &sq){
    return sq.elem[sq.length-1];
}
1.3.6 获取栈实际长度
1
2
3
int size(stack &sq){
    return sq.length;
}

1.4 链栈的实现

需要另外定义一个全局的整形变量 length 来存放栈的长度。

1.4.1 定义一个栈结构体
1
2
3
4
typedef struct Stack{
    int elem;
    struct Stack *next;
}*stack,*node;
1.4.2 初始化

需要为头结点分配空间

1
2
3
4
void Init_Stack(stack &sq){
    sq = (stack)malloc(sizeof(Stack));
    sq->next = NULL;
}
1.4.3 将元素压入栈

需要为新节点分配空间

1
2
3
4
5
6
7
void push(stack &sq,int e){
    node p = (node)malloc(sizeof(Stack));
    p->elem = e;
    p->next = sq->next;
    sq->next = p;
    length++;
}
1.4.4 将元素弹出栈
1
2
3
4
5
6
7
void pop(stack &sq){
    if(sq->next == NULL) return;
    node p = sq->next;
   sq->next = sq->next->next;
   delete p;
   length--;
}
1.4.5 获取栈顶元素
1
2
3
4
int  top(stack &sq){
    if(sq->next == NULL) return -1;
    return sq->next->elem;
}
1.4.6 获取栈实际长度
1
2
3
int size(stack &sq){
    return length;
}

1.5 栈的问题解决

1.5.1 括号匹配

苗苗今天刚刚学会使用括号，不过他分不清小括号，中括号，大括号和尖括号，不知道怎么使用这些括号，请帮助他判断括号使用是否正确。

输入格式

共一行，包含一个由 <,(,{,[,>,),},] 构成的字符串。

输出格式

如果输入的字符串中的括号正确匹配则输出 yes，否则输出 no。

数据范围

输入字符串长度不超过 1000010000。

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
#include<iostream>
using namespace std;
#include<stack>
stack<char> sq;
int main(){
    string s;
    cin >> s;
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '(' || s[i] == '[' || s[i] == '<' || s[i] == '{'){
            sq.push(s[i]);
        }else{
            //如果不是左括号并且栈内无元素，直接判断非法
            if (sq.empty())
            {
                cout << "no";
                return 0;
            }
            //接下来逐一判断是否匹配
            else if (s[i] == '>' && sq.top() == '<')
            {
                sq.pop();
            }
            else if (s[i] == ')' && sq.top() == '(')
            {
                sq.pop();
            }
            else if (s[i] == ']' && sq.top() == '[')
            {
                sq.pop();
            }
            else if (s[i] == '}' && sq.top() == '{')
            {
                sq.pop();
            }
            else{
                cout << "no";
                return 0;
            }
        }
    }
    //需要再次判断栈中是否还有字符
    if(sq.empty()){
        cout << "yes";
        return 0;
    }
    cout << "no";
    return 0;
}