栈

栈（stack）是限定在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶（top），另一端称为栈底（bottom）

，栈又称为后进先出（Last In First Out)的线性表，简称LIFO结构。

示例程序：（改编自《大话数据结构》）

 C++ Code 

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

#include <iostream>
using namespace std;

#define  MAXSIZE 20

typedef int ElemType;
typedef struct
{
    ElemType data[MAXSIZE];
    int top; //栈顶指针
} SqStack;

/* 构造一个空栈*/
bool InitStack(SqStack *Sq)
{
    Sq->top = -1; //表示空栈
    return true;
}
/* 置为空栈 */
bool ClearStack(SqStack *Sq)
{
    cout << "Clear Stack ..." << endl;
    Sq->top = -1;
    return true;
}

bool StackEmpty(SqStack Sq)
{
    if (Sq.top == -1)
        return true;
    else
        return false;
}

int StackLength(SqStack Sq)
{
    cout << "Stack Length : ";
    return Sq.top + 1;
}
/* 返回栈顶元素 */
bool GetTop(SqStack Sq, ElemType *ptr)
{
    if (Sq.top != -1)
    {
        *ptr = Sq.data[Sq.top];
        cout << "Get Top Item " << *ptr << endl;
        return true;
    }
    return false;
}
/* 压栈 */
bool Push(SqStack *Sq, ElemType Elem)
{
    cout << "Push Item  " << Elem << endl;
    if (Sq->top + 1 > MAXSIZE - 1)
        return false;
    Sq->data[++Sq->top] = Elem;
    return true;
}
/* 出栈 */
bool Pop(SqStack *Sq, ElemType *ptr)
{
    if (Sq->top == -1)
        return false;

    *ptr = Sq->data[Sq->top--];
    cout << "Pop Item  " << *ptr << endl;
    return true;
}

bool StackTraverse(SqStack Sq)
{
    cout << "Traverse Stack ..." << endl;
    if (Sq.top == -1)
        return false;
    for (int i = 0; i <= Sq.top; i++)
        cout << Sq.data[i] << ' ';
    cout << endl;
    return true;
}

int main(void)
{
    SqStack Sq;
    InitStack(&Sq);
    for (int i = 0; i < 5; i++)
        Push(&Sq, i);
    StackTraverse(Sq);
    int result;
    Pop(&Sq, &result);
    StackTraverse(Sq);
    GetTop(Sq, &result);
    if (!StackEmpty(Sq))
        cout << StackLength(Sq) << endl;

    ClearStack(&Sq);

    return 0;
}

输出为：