栈

栈也是一种线性表，它也可以由顺序表，和链表来实现。

只不过栈是一种被限制的线性表，它只能对栈顶（线性表的最末端的元素）进行基本操作（增删改查）。

本次，主要讲栈的顺序存储结构。

顺序栈

结构

  1. 数组data[MaxSize]
  2. 当前栈顶top
1
2
3
4
typedef struct {
	ElemType data[MaxSize];
	int top;
}SqStack;

操作流程图

实现代码

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
void Init(SqStack &s) {
	s.top = -1;
}

bool IsEmpty(SqStack s) {
	if (s.top == -1) {
		return true;
	}	
	return false;
}

bool IsFull(SqStack s) {
	if (s.top >= MaxSize - 1) {
		return true;
	}
	return false;
}

bool Push(SqStack& s, ElemType e) {
	if (IsFull(s)) {
		return false;
	}
	s.data[++s.top] = e;
	return true;
}

bool Pop(SqStack& s, ElemType &e) {
	if (IsEmpty(s)) {
		return false;
	}
	e=s.data[s.top--];
	return true;
}

bool GetTop(SqStack s, ElemType& e) {
	if (IsEmpty(s)) {
		return false;
	}
	e = s.data[s.top];
	return true;
}