logo
小吃货落樱
banner
数据结构的世界

Stack

Scroll down

栈的基本操作

我这里记录三种

  1. 顺序栈的结构体及基本操作

    头文件，所有的头文件都放在一个头文件All.h里

    1
    2
    3
    #include"SqStack.h"
    #include<stdio.h>
    #include<stdlib.h>
    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
    #pragma once
    #define MAXSIZE 128
    typedef int ElemType;

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

    //初始化栈
    void initStack(SqStack &S);

    //判断栈是否为空
    bool isEmpty(SqStack S);

    //如果栈没有满，将x入栈
    bool push(SqStack &S, ElemType x);

    //如果不为空，则将栈顶元素出栈，并返回
    ElemType pop(SqStack &S);

    //如果栈不为空，返回栈顶元素
    ElemType peek(SqStack S);

    //销毁栈
    void destroy(SqStack &S);

    //打印
    void printStack(SqStack S);

​ 函数实现：

​

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
#include "All.h"

//初始化栈
void initStack(SqStack &S)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		S.data[i]=0;
	}
		S.top=0;
		S.length=0;
}

//判断栈是否为空
bool isEmpty(SqStack S)
{
	return S.top==0?true:false;
}

//如果栈没有满，将x入栈
bool push(SqStack &S, ElemType x)
{
	if(S.length>MAXSIZE)//S.top>MAXSIZE
	{
		return false;
	}else{
		S.data[S.top]=x;
		S.top++;
	}
	S.length++;
	return true;
}

//如果不为空，则将栈顶元素出栈，并返回
ElemType pop(SqStack &S)
{
	if(isEmpty(S))
	{
		return -999;
	}
	int now=S.data[S.top-1];
	S.top--;
	S.length--;
	return now;
}

//如果栈不为空，返回栈顶元素
ElemType peek(SqStack S)
{
	if(isEmpty)
	{
		return -999;
	}else{
		return S.data[S.top-1];
	}
}

//销毁栈
void destroy(SqStack &S)
{
	for(int i=0;i<S.length;i++)
	{
		S.data[i]=0;
	}
	S.length=0;
	S.top=0;
}

//打印
void printStack(SqStack S)
{
	while(S.top>0)
	{
		printf("%-3d ",S.data[--S.top]);
	}
	printf("\n");
}

测试效果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include"All.h"

int main()
{
	Stack S;
	initStack(S);
	for(int i=0;i<5;i++)
	{
		push(S,i*10);
	}
	printStack(S);
	for(int i=0;i<3;i++)
	{
		ElemType ret=pop(S);
		printf("当前出栈元素：%d\n",ret);
	}

	system("pause");
	return 0;
}
1
2
3
4
5
40  30  20  10  0
当前出栈元素：40
当前出栈元素：30
当前出栈元素：20
请按任意键继续.

2.共享栈

1
2
3
#include"SharedStack.h"
#include<stdio.h>
#include<stdlib.h>
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
#pragma once

#define MAXSIZE 16
typedef int ElemType;

typedef struct{
	ElemType data[MAXSIZE];//共享栈的数据大小
	int top1;//第一个栈的栈顶指针
	int top2;//第二个栈的栈顶指针
	int size;
}SharedStack;

//初始化共享栈
void initStack(SharedStack &S);

//判断第一个栈是否为满
bool isFull1(SharedStack S);

//判断第二个栈是否满了
bool isFull2(SharedStack S);

//判断第一个栈是否为空
bool isEmpty1(SharedStack S);

//判断第二个栈是否为空
bool isEmpty2(SharedStack S);

//在第一个栈中压入元素e
bool push1(SharedStack &S,ElemType e);

//在第二个栈中入栈
bool push2(SharedStack &S,ElemType e);

//再第一个栈中出栈
int pop1(SharedStack &S);

//再第二个栈中出栈
int pop2(SharedStack &S);

//查看第一个栈的栈顶元素值
ElemType peek1(SharedStack S);

//查看第二个栈的栈顶元素值
ElemType peek2(SharedStack S);

//获取第一个栈的长度
int getLength1(SharedStack S);

//获取第二个栈的长度
int getLength2(SharedStack S);

//打印第一个栈
void printStack1(SharedStack S);

//打印第一个栈
void printStack2(SharedStack S);

//打印共享站中的所有元素
void printStack(SharedStack S);
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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include"All.h"

//初始化共享栈
void initStack(SharedStack &S)
{
	for(int i=0;i<MAXSIZE;i++)
	{
		S.data[i]=0;
	}
	S.top1=0;
	S.top2=MAXSIZE-1;
	S.size=0;
}

//判断第一个栈是否为满
bool isFull1(SharedStack S)
{
	return S.top1>S.top2;
}

//判断第二个栈是否满了
bool isFull2(SharedStack S)
{
	return S.top1>S.top2;
}

//判断第一个栈是否为空
bool isEmpty1(SharedStack S)
{
	if(S.top1==0)
	{
		return true;
	}else{
		return false;
	}
}

//判断第二个栈是否为空
bool isEmpty2(SharedStack S)
{
	if(S.top2==MAXSIZE)
	{
		return true;
	}else{
		return false;
	}
}

//在第一个栈中压入元素e
bool push1(SharedStack &S,ElemType e)
{
	if(!isFull1(S))
	{
		S.data[S.top1++]=e;
		S.size++;
		return true;
	}else{
		return false;
	}
}

//在第二个栈中入栈
bool push2(SharedStack &S,ElemType e)//top2往下移动
{
	if(!isFull2(S))
	{
		S.data[S.top2--]=e;
		S.size++;
	}else{
		return false;
	}
	return true;
}

//再第一个栈中出栈
int pop1(SharedStack &S)
{
	if(!isEmpty1(S))
	{
		S.size--;
		ElemType x=S.data[--S.top1];//入栈是先放进去，再++，即指针所指的位子是没有元素的
		S.data[S.top1]=0;
		return x;
	}
	else
	{
		return -999;
	}
}

//再第二个栈中出栈
int pop2(SharedStack &S)
{
	if(!isEmpty2(S))
	{
		S.size--;
		ElemType x=S.data[++S.top2];//入栈是先放进去，再++，即指针所指的位子是没有元素的
		S.data[S.top2]=0;
		return x;
	}
	else
	{
		return -999;
	}
}
//查看第一个栈的栈顶元素值
ElemType peek1(SharedStack S)
{
	if(!isEmpty1(S))
	{
		return S.data[S.top1-1];
	}else
	{
		return -999;
	}
}

//查看第二个栈的栈顶元素值
ElemType peek2(SharedStack S)
{
	if(!isEmpty2(S))
	{
		return S.data[S.top2+1];
	}else
	{
		return -999;
	}
}


//获取第一个栈的长度
int getLength1(SharedStack S)
{
	return S.top1;//下标为当前长度-1喔
}

//获取第二个栈的长度
int getLength2(SharedStack S)
{
	return MAXSIZE-1-S.top2;//此处用下标计算长度
}

//打印第一个栈
void printStack1(SharedStack S)
{
	for(int i=S.top1-1;i>=0;i--)
	{
		printf("%d ",S.data[i]);
	}
	printf("\n");
}

//打印第二个栈
void printStack2(SharedStack S)
{
	for(int i= S.top2+1;i<MAXSIZE;i++)//S.top所指的地方是空的，此处的共享站是先入栈后移动指针
	{
		printf("%d ",S.data[i]);
	}
	printf("\n");
}

//打印共享站中的所有元素
void printStack(SharedStack S)
{
	for(int i=0;i<S.size;i++)
	{
		printf("%d ",S.data[i]);
	
	}
	printf("\n");
}

3.链栈

需要的头文件

1
2
3
#include"LinkStack.h"
#include<stdio.h>
#include<stdlib.h>

基本操作及实现

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
#pragma once
typedef int ElemType;

typedef struct LNode{
	ElemType data;
	LNode*next;

}*LinkStack,LNode;

//初始化链栈
void initStack(LinkStack &S);

//判断栈是否为空
bool isEmpty(LinkStack S);

//入栈
void push(LinkStack &S,ElemType x);

//出栈
ElemType pop(LinkStack &S);

//取栈顶元素
ElemType peek(LinkStack S);

//销毁栈
void destroy(LinkStack &S);

//求栈长
int length(LinkStack S);

//打印栈
void print(LinkStack S);

没时间写注释

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

#include"All.h"

//初始化链栈
void initStack(LinkStack &S)
{
	S=(LinkStack)malloc(sizeof(LNode));
	S->next=NULL;
	S->data=0;//头节点存放链栈的长度
}

//判断栈是否为空
bool isEmpty(LinkStack S)
{
	return S->next==NULL?true:false;
}

//入栈
void push(LinkStack &S,ElemType x)
{
	LNode*last=(LinkStack)malloc(sizeof(LNode));
	last->data=x;
	last->next=S->next;
	S->next=last;
	S->data++;
}

//出栈
ElemType pop(LinkStack &S)
{
	if(S->next==NULL)
	{
		return -999;
	}
	LNode*last=S->next;
	S->next=last->next;
	ElemType x=last->data;
	free(last);
	S->data--;
	return x;
}

//取栈顶元素
ElemType peek(LinkStack S)
{
	if(S->next==NULL)
	{
		return -999;
	}
	return S->next->data;

}

//销毁栈
void destroy(LinkStack &S)
{
	LNode*pre=S->next,*last=S->next->next;
	while(last)
	{
		free(pre);
		pre=last;
		last=last->next;

	}
	S->next=NULL;
	S->data=0;
}

//求栈长
int length(LinkStack S)
{
	/*LNode*pre=S;
	int count=0;
	while(pre->next)
	{
		pre=pre->next;
		count++;
	}
	return count;*/
	return S->data;
}

//打印栈
void print(LinkStack S)
{	if(S->next==NULL||S==NULL)
	{
		return;
	}
	LNode*pre=S;
	while(pre->next)
	{
		pre=pre->next;
		printf("%d-> ",pre->data);
	}
	printf("\n");
}


栈的相关算法

1.判断序列是否合法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

bool check1(ElemType data[])
{
	SqStack S;
	initStack(S);
	int i=0;
	while(data[i]!='\0')
	{
		if(data[i]=='O')
		{
			if(isEmpty(S))
			{
				return false;
			}else{
				pop(S);
			}
		}else{
			push(S,'a');
		}
		i++;
	}
	return isEmpty(S);
}

测试：

1
2
3
4
5
6
7
8
9
10
11
12
IIIOOO
合法序列
请按任意键继续. .


OIOIOI
非法序列
请按任意键继续. . .

IOIOIOO
非法序列
请按任意键继续. . .

老爷，养我呜呜呜

其他文章
cover
HTML学习
  • 24/07/05
  • 21:16
  • HTML
cover
ERROR
  • 24/07/05
  • 21:16
  • 数据结构C语言版
网站标题

网站运行时间：0天

最后更新时间：00:00:00

目录导航 置顶
  1. 1. 栈的相关算法
请输入关键词进行搜索
  • to close