# 数据结构（四）：栈

### 一、栈的定义

```ADT List
{
数据对象：
D={a(i)|1=<i<=n, a(i)是 ElemType类型}
数据关系：
R={<a(i), a(i+1)>|a(i),a(i+1)属于 D, i=1,2,3,···,n-1}
基本运算：
InitStack(&s): 初始化栈，构建一个空栈 s
ClearStack(&s): 销毁栈：释放栈 s所占的内存空间
StackLength(s): 求栈的长度: 返回栈 s中的元素个数
StackEmpty(s): 判断栈是否为空：若栈 s为空则返回真，否则返回假
Push(&s, e): 进栈：将元素 e添加到栈顶
Pop(&s, &e): 出栈：将栈顶元素赋值给 e并从栈顶删除
GetTop(s, &e): 取栈顶元素：将当前栈顶元素的值赋值给 e
DispStack(s)：显示栈中所有元素的值：按照从栈顶到栈底的顺序显示栈中所有元素的值
}```

### 二、栈的顺序存储结构与基本运算

```#define MaxSize 100

typedef char ElemType;
typedef struct Stack{
int STop;
ElemType data[MaxSize];
}Stack;```

#### 1、栈的初始化

```void InitStack(Stack* &s) {
s = (Stack*)malloc(sizeof(Stack));
s->STop = -1;
}//InitStack```

#### 2、销毁栈

```void ClearStack(Stack* &s) {
free(s);
s = NULL;
}//ClearStack```

#### 3、求栈的长度

```int StackLength(Stack* s) {
return s->STop + 1;
}//StackLengt```

#### 4、判断栈是否为空

```bool StackEmpty(Stack* s) {
if (s->STop < 0) {
return true;
}
else{
return false;
}
}//StackEmpty```

#### 5、进栈

```void Push(Stack* &s, ElemType e) {
s->STop++;

if (s->STop > MaxSize || s->STop < 0) {
throw;
}
else{
s->data[s->STop] = e;
}
}//Push```

#### 6、出栈

```void Pop(Stack* &s, ElemType &e) {
if (!StackEmpty(s)) {
e = s->data[s->STop];
s->STop--;
}
else {
throw;
}
}//Pop```

#### 7、取栈顶元素

```void GetTop(Stack* s, ElemType &e) {
if (!StackEmpty(s)) {
e = s->data[s->STop];
}
else {
throw;
}
}//GetTop```

#### 8、打印栈

```void DispStack(Stack* s) {
if (StackEmpty(s)) {
printf("stack is empty.\n");
}
else {
int top = s->STop;
while (top >= 0) {
printf("index: %d, value: %c\n", top, s->data[top]);
top--;
}
}
}//DispStack```

### 三、栈的链式存储结构与基本运算

```typedef char ElemType;
ElemType data;

#### 1、链栈的初始化

```void InitStack(LinkStack* &s) {
s->next = NULL;
}```

#### 2、销毁链栈

```void ClearStack(LinkStack* &s) {
while(s->next != NULL) {
free(s->next);
s->next = temp;
}
free(s);
s = NULL;
}```

#### 3、求链栈的长度

```int StackLength(LinkStack* s) {
int i = 0;
while (s->next != NULL) {
i++;
s->next = s->next->next;
}
return i;
}```

#### 4、判断链栈是否为空

```bool StackEmpty(LinkStack* s) {
return s->next == NULL;
}```

#### 5、进栈

```void Push(LinkStack* &s, ElemType e) {
if (new_node == NULL) {
throw;
}

new_node->data = e;
new_node->next = s->next;
s->next = new_node;
}```

#### 6、出栈

```void Pop(LinkStack* &s, ElemType &e) {
if (StackEmpty(s)) {
throw;
}

e = temp->data;
s->next = temp->next;
free(temp);
}```

#### 7、取栈顶元素

```void GetTop(LinkStack* s, ElemType &e) {
if (StackEmpty(s)) {
throw;
}

e = s->next->data;
}```

#### 8、打印栈

```void DispLStack(LinkStack* s) {
*temp = *s;

int i = 0;
while (temp->next != NULL) {
i++;
printf("index: %d, value: %c\n", i, temp->next->data);
temp->next = temp->next->next;
}
}```

70 篇文章18 人订阅

0 条评论

## 相关文章

9830

36170

11520

22590

8220

19360

10010

13240

10230

### JAVA中Sql时间格式与util时间格式转换

pst.setDate(1, ;//这里的Date是sql中的::得到的是日期

30350