{
DataType stack[MaxStackSize]
int top
} SeqStack
void StackInitiate(SeqStack *S) /*初始化顺序堆栈S*/
{S->top = 0/*定义初始栈顶下标值*/
}
int StackNotEmpty(SeqStack S)
/*判顺序堆栈S非空否，非空则返回1，否则返回0*/
{if(S.top <= 0) return 0
else return 1
}
int StackPush(SeqStack *S, DataType x)
/*把数据元素值x压入顺序堆栈S，入栈成功则返回1，否则返回0 */
{if(S->top >= MaxStackSize)
{printf("堆栈已满无法插入! \n")
return 0
}
else
{ S->stack[S->top] = x
S->top ++
return 1
}
}
int StackPop(SeqStack *S, DataType *d)
/*d出顺序堆栈S的栈顶数据元素值到参数d ，出栈成功则返回1，否则返回0*/
{if(S->top <= 0)
{
printf("堆栈已空无数据元素出栈! \n")
return 0
}
else
{
S->top --
*d = S->stack[S->top]
return 1
}
}
int StackTop(SeqStack S, DataType *d)
/*取顺序堆栈S的当前栈顶数据元素值到参数d ，成功则返回1，否则返回0*/
{
if(S.top <= 0)
{ printf("堆栈已空! \n")
return 0
}
else
{ *d = S.stack[S.top - 1]
return 1
}
}
1. 快速得到最大值的栈
结构
需要两个数组：一个数组stackItem保存栈的元素，另一个数组link2NextMaxValueIndex保存下一个最大值的位置
两个指针：一个为stackTop指向栈顶，另一个为maxValueIndex指向最大值的下标
*** 作
插入时：比较插入元素与最大值的大小，如果比最大值还大呢，link2NextMaxValueIndex指向原来最大值的位置（即maxValueIndex），而maxValueIndex变为现在插入元素的位置；否则link2NextMaxValueIndex指向-1
删除时：删除元素的位置出，如果maxValueIndex与当前位置相同，此时maxValueIndex为link2NextMaxValueIndex[satckTop]
返回栈的最大元素
图示
以入栈2 7 1，出栈为例：
#include <iostream>
#include <climits>
#define MAX 100
using namespace std
class stack
{
public:
stack() : stackTop(-1), maxValueIndex(-1) {}
void push(int val)
int pop()
int max()
int size() { return stackTop + 1}
int empty() { return stackTop <0 ? 1 : 0}
private:
int stackItem[MAX]
int link2NextMaxValueIndex[MAX]
int stackTop
int maxValueIndex
}
void stack::push(int val)
{
++stackTop
if(stackTop == MAX)
{
cout <<"The stack has been full!" <<endl
return
}
else
{
stackItem[stackTop] = val
if(max() <val)
{
link2NextMaxValueIndex[stackTop] = maxValueIndex
maxValueIndex = stackTop
}
else
link2NextMaxValueIndex[stackTop] = -1
}
}
int stack::pop()
{
int ret
if(stackTop == -1)
{
cout <<"The stack is empty!" <<endl
return -1
}
else
{
ret = stackItem[stackTop]
if(stackTop == maxValueIndex)
maxValueIndex = link2NextMaxValueIndex[stackTop]
--stackTop
return ret
}
}
int stack::max()
{
if(maxValueIndex >= 0)
return stackItem[maxValueIndex]
else
return INT_MIN
}
int main()
{
stack s
cout <<"s.empty():" <<s.empty() <<endl
s.push(3)
s.push(4)
cout <<"s.top():" <<s.pop() <<endl
cout <<"s.top():" <<s.pop() <<endl
cout <<"s.top():" <<s.pop() <<endl
cout <<"s.size():" <<s.size() <<endl
cout <<"s.empty():" <<s.empty() <<endl
}
结果
/*你提供的那个代码是伪代码，我帮你写成了
C
的代码。
你提供的伪代码，我用注释写到了对应的行的后面。
根据你提供的代码还只能转换含有一个字母或
[0,9]
区间内的数字的解析式。
补充了一点栈的基本算法
执行后输出：
原式子（中缀表达式）：
a+b*c
新式子（后缀表达式）：
a
b
c
*
+
代码使用
Linux
+
GCC
3.4.5
编译通过
July.28th,2009
14:30pm.
main()
在最下边
*/
#include
struct
_stack
{
char
__stack[1024]
int
__top
}
//
模拟栈
inline
init_stack(
struct
_stack
*
p_stack
)
//
初始化栈
{
int
i
=
0
for(
i
=
0
i
<=
1024
i++
)
p_stack->__stack[i]
=
'\0'
p_stack->__top
=
0
}
inline
void
push(
struct
_stack
*
p_stack,
char
p_op
)
//
进栈
{
p_stack->__stack[p_stack->__top]
=
p_op
(
p_stack->__top
)++
}
inline
char
pop(
struct
_stack
*
p_stack
)
//
出栈
{
(
p_stack->__top
)--
return
p_stack->__stack[p_stack->__top]
}
inline
int
precedence(
char
p_char
)
//
比较优先级
{
if(
p_char
==
'+'
||
p_char
==
'-'
)
return
1
else
if(
p_char
==
'/'
||
p_char
==
'*'
)
return
2
else
return
0
}
char
postString[1024]
char
*
infix_to_postfix(
char
*inString
)
{
int
l
=
strlen(
inString
)
struct
_stack
stack
char
p
=
'\0'
int
i
=
0
char
c
=
'\0'
l
=
strlen(
inString
)
//
l
<-
Length
of
inString
for(
i
=
0
i
<=
1024
i++
)
postString[i]
=
'\0'
//
postString
<-
empty
string
init_stack(
&stack
)
//
stack
<-
Empty
stack
for(
i
=
0
i
<=
l
i++
)
//
for
i
<-
0
to
l
{
c
=
inString[i]
//
c
<-
inString[i]
if(
(
c
>=
'0'
&&
c
<=
'9'
)||(
c
>=
'a'
&&
c
<=
'z'
)||(
c
>=
'A'
&&
c
<=
'Z'
)
)
//
if
c
is
an
operand
{
if(
postString[0]
==
'\0'
){postString[0]
=
ccontinue}
sprintf(
postString,
"%s
%c",
postString,
c
)
//
add
c
at
the
end
of
postString
}//
end
if
if(
c
==
'+'
||
c
==
'-'
||
c
==
'*'
||
c
==
'/'
)
//
if
c
is
an
operator
{
if(
stack.__top==0
||
precedence(
stack.__stack
[stack.__top]
)<
precedence(
c
)
)
//
if
stack
is
empty
OR
if
precedence(
stack_top
)<
precedence(
c
)
{
push(
&stack,
c
)
//
push
c
into
stack
}
else
{
while(
precedence(
stack.__stack
[stack.__top]
)>=
precedence(
c
)
)
//
while
precedence(
stack_top
)>=
precedence(
c
)
{
p
=
pop(
&stack
)
//
p
<-
pop
from
stack
sprintf(
postString,
"%s
%c",
postString,
p
)
//
add
p
at
the
end
of
postString
}
//
end
while
push(
&stack,
c
)
//
push
c
into
stack
}
//
end
if
}
//
end
if
}
//
end
for
while(
stack.__top
)
//
while
stack
is
not
empty
{
p
=
pop(
&stack
)
//
p
<-
pop
from
stack
sprintf(
postString,
"%s
%c",
postString,
p
)
//
add
p
at
the
end
of
postString
}
//
end
while
return
postString
}
int
main(
)
{
char
exp[]
=
"a+b*c"
char
*
p
=
0
p
=
infix_to_postfix(
exp
)
printf(
"原式子（中缀表达式）：\n\t%s\n新式子（后缀表达式）：\n\t%s\n",
exp,
p
)
return
0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）