STACK

Posted by mapoto4 on 2017-04-03

栈是一个只能从一端进行插入或删除的线性表。

允许操作的一端称为栈顶(Top),另一端称为栈底,栈的插入和删除称为出栈和入栈。

栈的主要特点是先进后出(FILO),如同手枪子弹上膛一样。

当n个元素以某种顺序进栈并可以在任意时刻出栈,所获得的元素排列的数目N满足Catalan函数的计算:
N=1/(n+1)C(n,2n)

栈的应用

解决问题的过程出现一个状态,凭现有条件不能判断当前的状态是否能解决,需要记录等待以后出现可以解决当前状态的条件后返回再解决。

  • 匹配括号
  • 后缀式求值

栈的存储结构

1
2
3
4
5
typedef struct
{
int 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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

#include <iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef struct
{
int data[MAXSIZE];
int top;
}SqStack;

int InitStack(SqStack *s)
{
s->top = -1;
return OK;
}

int ClearStack(SqStack *s)
{
s->top = -1;
return OK;
}

int StackEmpty(SqStack s)
{
if (s.top == -1)
return TRUE;
else
return FALSE;
}

int StackLength(SqStack s)
{
return s.top + 1;
}

int GetTop(SqStack s, int *e)
{
if (s.top == -1)
return ERROR;
else
*e = s.data[s.top];
return OK;
}

int Push(SqStack *s, int e)
{
if (s->top == MAXSIZE - 1)
return ERROR;
else
s->top++;
s->data[s->top] = e;
return OK;
}

int Pop(SqStack *s, int &e)
{
if (s->top == -1)
return ERROR;
else
e = s->data[s->top];
s->top--;
return OK;
}

void print(SqStack s)
{


int i=0;
while (i <= s.top)
{
cout<<s.data[i++]<<" ";
}
cout<<endl;
}

void main()
{
SqStack s;
int j;
int e=0 ;
int f=0;
if (InitStack(&s) == OK)
for (j = 1; j <= 10; j++)
Push(&s, j);

cout << "1.显示栈中元素"<<endl;
cout << "2.返回栈顶元素" << endl;
cout << "3.返回栈的长度" << endl;
cout << "4.判断栈是否为空" << endl;
cout << "5.清空栈" << endl;
cout << "6.压栈" << endl;
cout << "7.出栈" << endl;

int switch_on = 1;
while (switch_on!=0)
{
cin >> switch_on;
switch (switch_on)
{
case 1:
print(s);
break;
case 2:
GetTop(s, &e);
cout << "栈顶元素" << e << endl;
break;
case 3:
cout << "栈的长度为" << StackLength(s) << endl;
break;
case 4:
cout << "栈空否 1:空 0:否 : " << StackEmpty(s) << endl;
break;
case 5:
ClearStack(&s);
cout << "清空完成!";
break;
case 6:
int input;
cout << "输入压入的数值:";
cin >> input;
Push(&s, input);
cout << "完成操作!"<<endl;
break;
case 7:
Pop(&s, f);
cout << "弹出的栈顶元素" << f << endl;
break;
case 0:
break;
}
}
}