1、栈是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶，表头端称为栈底。栈的修改是是按照后进先出的原则进行的，因此，栈又成为后进先出(last in first out)的线性表(简称LIFO结构)。
2、当栈顶指针跟栈底指针相同时说明栈空了，因此非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
3、以下是栈的顺序存储表示以及基本操作的算法描述：
#define STACK_INIT_SIZE 100 //存储空间初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct {
SElemType *base; //在栈构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
status InitStack(SqStack &S)
{
//构造一个空栈
S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if (!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
Status GetTop(SqStack S, SElemType &e)
{
//若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR
if (S.top == S.base) return ERROR;
e = *(S.top - 1);
return OK;
}
Status Push(SqStack &S, SElemType e)
{
//插入元素e为新的栈顶元素
if (S.top -S.base >= S.stackszie) //栈满，追加存储空间
{
S.base = (SElemType *)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if (!S.base) exit(OVERFLOW); //存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
Status Pop(SqStack &S, SElemType &e)
{
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if (S.top == S.base) return ERROR;
e = * --S.top;
return OK;
}
4、对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数，用C语言伪代码实现如下：
void conversion()
{
InitStask(S); //构造空栈
scanf("%d", N);
while (N)
{
Push(S, N%8);
N = N/8;
}
while (!StackEmpty(S))
{
Pop(S,e);
printf("%d", e);
}
}
5、括号匹配的检查可以用栈来实现，在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性都降了一级。在算法的开始和结束时，栈都应该是空的。
6、行编辑程序可以用栈来实现，设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户缓冲区。允许用户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可以补进一个退格符”#“，以表示以前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可键入一个退行符”@”，以表示当前行中的字符无效。例如从终端接受了这样两行字符：
whli##ilr#e(s# *s) outcha@putchar( *s=# ++ );
则实际有效的是下面两行：
while( *s) putchar( *s ++ );
为此，可设这个输入缓冲区为一个栈结构，每当从终端接受了一个字符之后作如下判别：如果它既不是退格符也不是退行符，则将该字符压入栈顶；如果是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将字符栈清为空栈。上述过程可用C语言伪代码实现如下：
void LineEdit()
{
//利用字符栈S，从终端接收一行并传送至调用过程的数据区。
InitStack(S); //构造空栈S
ch = getchar(); //从终端接收第一个字符
while (ch != EOF) //EOF为全文结束符
{
while (ch != EOF && ch != '\n')
{
switch (ch)
{
case '#': Pop(S, c); break; //仅当栈非空时退栈
case '@': ClearStack(S); break; //重置S为空栈
default: Push(S, ch); break; //有效字符进栈，未考虑栈满情况
}
ch = getchar(); //从终端接收下一个字符
}
save(S); //将栈底到栈顶的栈内字符传送至调用过程的数据区
ClearStack(S); //重置S为空栈
if (ch != EOF) ch = getchar();
}
DestroyStack(S);
}
除非注明，文章均为CppLive 编程在线原创，转载请注明出处，谢谢。
