SatParamita六到彼岸

诵持三藏经律论 勤修六度波罗蜜

数据结构-栈

栈和队列

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
#include <stack>
#include <queue>
#include <stdio.h>
using namespace std;
int main()
{
// 栈,先进后出
stack<int> s;
for (int i = 0; i < 10; i++)
s.push(i);
while (!s.empty())
{
int data = s.top();
printf("%d ", data); //9 8 7 6 5 4 3 2 1 0
s.pop();
}
printf("\n");

// 队列,先进先出
queue<int> q;
for (int i = 0; i < 10; i++)
q.push(i);
while (!q.empty())
{
int data = q.front();
printf("%d ", data); //0 1 2 3 4 5 6 7 8 9
q.pop();
}

return 0;
}

进制转换

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
// 栈Stack
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

// 进制转换问题
void Convert(char *buffer, int value, int base)
{
const char *DATA = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
// create a stack, name it S, the data that stores in it is char
stack<char> S;

while (value != 0)
{
int d = value % base;
char D = d >= 10 ? 'A' + d - 10 : '0' + d; //大于10进制就用字母
// D = DATA[d];
S.push(D); //D进栈
value /= base;
}
if (S.empty()) //如果是空栈
S.push('0');

while (!S.empty()) //不空
{
*buffer++ = S.top(); //返回栈顶元素,存入buffer[]
S.pop(); //移除栈顶元素
}
*buffer = '\0';
}

int main()
{
char buffer[1024];
int value, base;

cout << "请输入一个数value和需要转换成的进制base。例:16 2" << endl;
cin >> value >> base;

// 在buffer中填写value的base进制表示串
Convert(buffer, value, base);

cout << buffer << endl;
return 0;
}

车厢调度

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
// 车厢调度问题
// 用顺序表模拟栈,描述站台结构
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;

const int MAXBUFFERLEN = 100;

struct Stack
{
int buffer[MAXBUFFERLEN];
int top; // top指向下一节车厢进入站台的位置
};
//初始化
int InitStack(Stack &S)
{
S.top = 0;
return 0;
}
int push(Stack &S, int data) //主要函数
{
if (S.top >= MAXBUFFERLEN)
return -1;

S.buffer[S.top] = data; //初始化中 S.top=0
S.top++;

return 0;
}

int pop(Stack &S)
{
S.top--;
return 0;
}

int empty(const Stack S) //不用&s,因为不修改s
{
return S.top <= 0; //判断是否为空,返回真假10
}

int top(const Stack S) //主要函数,
{
return S.buffer[S.top - 1];
}

int main()
{
int command, n = 1, m;
struct Stack S;
InitStack(S);

//先进后出
cout << "请输入进出栈命令: 0表示车厢进站;1表示车厢出站" << endl;
while (cin >> command)
{
if (command == 0)
{
if (push(S, n) != 0)
cout << "站台已满!" << endl;
else
{
cout << "车厢 " << n << " 运货进入站台。" << endl;
n++;
}
}
else if (command == 1)
{
if (empty(S))
cout << "站台上没有车厢!" << endl;
else
{
m = top(S);
pop(S);
cout << "车厢 " << m << " 运货出站。" << endl;
}
}
}
return 0;
}

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
#include <stdio.h>
#include <stdlib.h>
typedef char DataType;
#define StackSize 100
typedef struct
{
DataType stack[StackSize];
int top;
} SeqStack;

void InitStack(SeqStack *S)
/*将栈初始化为空栈只需要把栈顶指针top置为0*/
{
S->top = 0; /*把栈顶指针置为0*/
}
int StackEmpty(SeqStack S)
/*判断栈是否为空,栈为空返回1,否则返回0*/
{
if (S.top == 0) /*判断栈顶指针top是否为0*/
return 1; /*当栈为空时,返回1;否则返回0*/
else
return 0;
}
int GetTop(SeqStack S, DataType *e)
/*取栈顶元素。将栈顶元素值返回给e,并返回1表示成功;否则返回0表示失败。*/
{
if (S.top <= 0) /*在取栈顶元素之前,判断栈是否为空*/
{
printf("栈已经空!\n");
return 0;
}
*e = S.stack[S.top - 1]; /*在取栈顶元素*/
return 1;
}
int PushStack(SeqStack *S, DataType e)
/*将元素e进栈,元素进栈成功返回1,否则返回0.*/
{
if (S->top >= StackSize) /*在元素进栈前,判断是否栈已经满*/
{
printf("栈已满,不能进栈!\n");
return 0;
}
S->stack[S->top] = e; /*元素e进栈*/
S->top++; /*修改栈顶指针*/
return 1;
}
int PopStack(SeqStack *S, DataType *e)
/*出栈操作。将栈顶元素出栈,并将其赋值给e。出栈成功返回1,否则返回0*/
{
if (S->top <= 0) /*元素出栈之前,判断栈是否为空*/
{
printf("栈已经没有元素,不能出栈!\n");
return 0;
}
S->top--; /*先修改栈顶指针,即出栈*/
*e = S->stack[S->top]; /*将出栈元素赋值给e*/
return 1;
}
int StackLength(SeqStack S)
/*求栈的长度,即栈中元素个数,栈顶指针的值就等于栈中元素的个数*/
{
return S.top;
}

int main()
{
DataType a[] = {'a', 'b', 'c', 'd', 'e'};
DataType e;

SeqStack S;
InitStack(&S);

for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)
if (PushStack(&S, a[i]) == 0)
{
printf("栈已满,不能进栈!");
return 0;
}

printf("出栈的元素是:");
if (PopStack(&S, &e) == 1)
printf("%4c", e);
if (PopStack(&S, &e) == 1)
printf("%4c", e);

printf("\n当前栈顶的元素是:");
if (GetTop(S, &e) == 0)
{
printf("栈已空!");
return 0;
}
else
printf("%4c\n", e);

if (PushStack(&S, 'f') == 0)
{
printf("栈已满,不能进栈!");
return 0;
}
if (PushStack(&S, 'g') == 0)
{
printf("栈已满,不能进栈!");
return 0;
}

printf("当前栈中的元素个数是:%d\n", StackLength(S));
printf("元素出栈的序列是:");
while (!StackEmpty(S))
{
PopStack(&S, &e);
printf("%4c", e);
}
return 0;
}

带头结点的链栈

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
#include <stdio.h>      
#include <string.h> /*包含字符串长度函数*/
#include <malloc.h> /*包含内存分配函数*/
typedef char DataType; /*类型定义为字符类型*/

typedef struct node
{
DataType data;
struct node *next;
} LStackNode, *LinkStack;

void InitStack(LinkStack *top)
/*将链栈初始化为空。动态生成头结点,并将头结点的指针域置为空。*/
{
*top = (LinkStack)malloc(sizeof(LStackNode));
(*top)->next = NULL; /*将链栈的头结点指针域置为空*/
}
int StackEmpty(LinkStack top)
/*判断链栈是否为空,就是通过判断头结点的指针域是否为空*/
{
if (top->next == NULL) /*判断链栈头结点的指针域是否为空*/
return 1; /*当链栈为空时,返回1;否则返回0*/
else
return 0;
}
int PushStack(LinkStack top, DataType e)
/*进栈操作就是要在链表的第一个结点前插入一个新结点,进栈成功返回1*/
{
/*定义指向第i个元素的前驱结点指针pre,指针p指向新生成的结点*/
LStackNode *p = (LStackNode *)malloc(sizeof(LStackNode));
p->data = e;
p->next = top->next; /*将结点插入到栈顶*/
top->next = p;
return 1;
}
int PopStack(LinkStack top, DataType *e)
/*删除单链表中的第i个位置的结点。删除成功返回1,失败返回0*/
{
LStackNode *p = top->next;
if (StackEmpty(top)) /*判断堆栈是否为空*/
{
printf("栈已空");
return 0;
}
top->next = p->next; /*将栈顶结点与链表断开,即出栈*/
*e = p->data; /*将出栈元素赋值给e*/
free(p); /*释放p指向的结点*/
return 1;
}
int StackLength(LinkStack top)
{
LStackNode *p = top;
int count = 0;
while (p->next != NULL)
{
p = p->next;
count++;
}
return count;
}
void DestroyStack(LinkStack top)
{
LStackNode *p = top;
while (!p)
{
LStackNode *q = p;
p = p->next;
free(q);
}
}
int GetTop(LinkStack top, DataType *e)
{
LStackNode *p = top->next;
if (!p) /*判断链栈是否为空*/
{
printf("栈已空");
return 0;
}
*e = p->data; /*将出栈元素赋值给e*/
return 1;
}

共享栈

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
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
/* 两栈共享空间结构 */
typedef struct
{
int data[MAXSIZE];
int top1; /* 栈1栈顶指针 */
int top2; /* 栈2栈顶指针 */
} SqDoubleStack;

/* 构造一个空栈S */
int InitStack(SqDoubleStack *S)
{
S->top1 = -1;
S->top2 = MAXSIZE;
return OK;
}
/* 插入元素e为新的栈顶元素 */
int Push(SqDoubleStack *S, int e, int stackNumber)
{
if (S->top1 + 1 == S->top2) /* 栈已满,不能再push新元素了 */
return ERROR;

if (stackNumber == 1) /* 栈1有元素进栈 */
S->data[++S->top1] = e; /* 若是栈1则先top1+1后给数组元素赋值。 */
else if (stackNumber == 2) /* 栈2有元素进栈 */
S->data[--S->top2] = e; /* 若是栈2则先top2-1后给数组元素赋值。 */
return OK;
}
int StackTraverse(SqDoubleStack S)
{
for (int i = 0; i < S.top1; i++)
printf("%d ", S.data[i]);

for (int i = S.top2; i < MAXSIZE; i++)
printf("%d ", S.data[i]);

printf("\n");
return OK;
}
/* 若栈S为空栈,则返回TRUE,否则返回FALSE */
int StackEmpty(SqDoubleStack S)
{
if (S.top1 == -1 && S.top2 == MAXSIZE)
return TRUE;
else
return FALSE;
}
/* 返回S的元素个数,即栈的长度 */
int StackLength(SqDoubleStack S)
{
return (S.top1 + 1) + (MAXSIZE - 1 - S.top2);
}
/* 若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK;否则返回ERROR */
int Pop(SqDoubleStack *S, int *e, int stackNumber)
{
if (stackNumber == 1)
{
if (S->top1 == -1)
return ERROR; /* 说明栈1已经是空栈,溢出 */

*e = S->data[S->top1]; /* 将栈1的栈顶元素出栈 */
S->top1--;
}
else if (stackNumber == 2)
{
if (S->top2 == MAXSIZE)
return ERROR; /* 说明栈2已经是空栈,溢出 */

*e = S->data[S->top2]; /* 将栈2的栈顶元素出栈 */
S->top2++;
}
return OK;
}
int main()
{
int j, e;
SqDoubleStack s;

if (InitStack(&s) == OK)
{
for (j = 1; j <= 5; j++)
Push(&s, j, 1);
for (j = MAXSIZE; j >= MAXSIZE - 2; j--)
Push(&s, j, 2);
}

printf("栈中元素依次为:");
StackTraverse(s);

printf("当前栈中元素有:%d \n", StackLength(s));

Pop(&s, &e, 2);
printf("弹出的栈顶元素 e=%d\n", e);
printf("栈空否:%d(1:空 0:否)\n", StackEmpty(s));

for (j = 6; j <= MAXSIZE - 2; j++)
Push(&s, j, 1);
printf("栈中元素依次为:");
StackTraverse(s);

printf("栈满否:%d(1:否 0:满)\n", Push(&s, 100, 1));

InitStack(&s);
printf("清空栈后,栈空否:%d(1:空 0:否)\n", StackEmpty(s));

return 0;
}

共享栈

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
typedef struct
{
DataType stack[StackSize];
int top[2];
} SSeqStack;

void InitStack(SSeqStack *S)
/*共享栈的初始化操作*/
{
S->top[0] = 0;
S->top[1] = StackSize - 1;
}
int PushStack(SSeqStack *S, DataType e, int flag)
/*共享栈进栈操作。进栈成功返回1,否则返回0*/
{
if (S->top[0] == S->top[1]) /*在进栈操作之前,判断共享栈是否为空*/
return 0;
switch (flag)
{
case 0: /*当flag为0,表示元素要进左端的栈*/
S->stack[S->top[0]] = e; /*元素进栈*/
S->top[0]++; /*修改栈顶指针*/
break;
case 1: /*当flag为1,表示元素要进右端的栈*/
S->stack[S->top[1]] = e; /*元素进栈*/
S->top[1]--; /*修改栈顶指针*/
break;
default:
return 0;
}
return 1;
}
int PopStack(SSeqStack *S, DataType *e, int flag)
{
switch (flag) /*在出栈操作之前,判断是哪个栈要进行出栈操作*/
{
case 0:
if (S->top[0] == 0) /*左端的栈为空,则返回0,表示出栈操作失败*/
return 0;
S->top[0]--; /*修改栈顶指针*/
*e = S->stack[S->top[0]]; /*将出栈的元素赋值给e*/
break;
case 1:
if (S->top[1] == StackSize - 1) /*右端的栈为空,则返回0,表示出栈操作失败*/
return 0;
S->top[1]++; /*修改栈顶指针*/
*e = S->stack[S->top[1]]; /*将出栈的元素赋值给e*/
break;
default:
return 0;
}
return 1;
}
int GetTop(SSeqStack S, DataType *e, int flag)
/*取栈顶元素。将栈顶元素值返回给e,并返回1表示成功;否则返回0表示失败。*/
{
switch (flag)
{
case 0:
if (S.top[0] == 0)
return 0;
*e = S.stack[S.top[0] - 1];
break;
case 1:
if (S.top[1] == StackSize - 1)
return 0;
*e = S.stack[S.top[1] + 1];
break;
default:
return 0;
}
return 1;
}
int StackEmpty(SSeqStack S, int flag)
{
switch (flag)
{
case 0:
if (S.top[0] == 0)
return 1;
break;
case 1:
if (S.top[1] == StackSize - 1)
return 1;
break;
default:
return 0;
}
return 0;
}
0%