栈 数据结构_栈数据结构

1.栈

栈，又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

原全代码：`

#include <stdio.h>
#include <malloc.h>
 
#define STACK_MAX_SIZE 10

typedef struct CharStack {
    int top;
    int data[STACK_MAX_SIZE]; d.
} *CharStackPtr;
 

CharStackPtr charStackInit() {
	CharStackPtr resultPtr = (CharStackPtr)malloc(sizeof(CharStack));
	resultPtr->top = -1;
	return resultPtr;
}

void outputStack(CharStackPtr paraStack) {
    for (int i = 0; i <= paraStack->top; i ++) {
        printf("%c ", paraStack->data[i]);
    }
}
 
void push(CharStackPtr paraStackPtr, int paraValue) {
    if (paraStackPtr->top >= STACK_MAX_SIZE - 1) {
        printf("栈已存满");
        return;
    }
	paraStackPtr->top ++;//上移top
    paraStackPtr->data[paraStackPtr->top] = paraValue;//元素赋值
}

char pop(CharStackPtr paraStackPtr) {
    if (paraStackPtr->top < 0) {
        printf("无法删除");
        return '\0';
    }
 
	paraStackPtr->top --;
    return paraStackPtr->data[paraStackPtr->top + 1];
}
void pushPopTest() {

    CharStackPtr tempStack = charStackInit();
	outputStack(tempStack);

	for (char ch = 'a'; ch < 'm'; ch ++) {
		printf("添加%c.\r\n", ch);
		push(tempStack, ch);
		outputStack(tempStack);
	}
	
	for (int i = 0; i < 3; i ++) {
		ch = pop(tempStack);
		printf("删除%c.\r\n", ch);
		outputStack(tempStack);
	}
}
void main() {
	pushPopTest();
}
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62

入栈

void push(CharStackPtr StackPtr, int a) {
    if (StackPtr->top >= STACK_MAX_SIZE - 1) {
    printf("error");
    return;
    }
	StackPtr->top ++;
    StackPtr->data[StackPtr->top] = a;
}
1
2
3
4
5
6
7
8

出栈

char pop(CharStackPtr StackPtr) {
    if (StackPtr->top < 0) {
        printf("fail");
        return '\0';
    }
	StackPtr->top --;
    return StackPtr->data[StackPtr->top + 1];
}
1
2
3
4
5
6
7
8

判断空栈

bool StackExistir(CharStackPtr StackPtr)
{
     if (StackPtr->top==-1)  
         return true;
     return false;
}

1
2
3
4
5
6
7

总结
注意栈的先进后出原则

2.括号匹配问题

bool bracketMatching(char* paraString, int paraLength) {
    CharStackPtr tempStack = charStackInit();
	push(tempStack, '#');
	char tempChar, tempPopedChar;
	for (int i = 0; i < paraLength; i++) {
		tempChar = paraString
		switch (tempChar) {
		case '(':
		case '[':
		case '{':
			push(tempStack, tempChar);
			break;
		case ')':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '(') {
				return false;
			}
			break;
		case ']':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '[') {
				return false;
			}
			break;
		case '}':
			tempPopedChar = pop(tempStack);
			if (tempPopedChar != '{') {
				return false;
			}
			break;
		default:
			
			break;
		}
	}
	tempPopedChar = pop(tempStack);
	if (tempPopedChar != '#') {
		return false;
	}
	return true;
}

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