栈的定义以及基本运算

栈和队列实质上是俩种受限制的线性表

一 栈的定义：

　栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

二 栈的顺序存储结构

实质上是运算受限的线性表

（1）顺序栈的类型定义

[cpp] view plain copy

1. #define StackSize 100//假定预先分配100元素  
2. typedef char DataType;//假定栈元素的数据类型为字符  
3. typedef struct   
4. {  
5.     DataType data[StackSize];  
6.     int top;  
7. }SeqStack;  
8.   
9. 注：top用来指示当前栈顶的位置，因为在栈低是不变的  
10. 三 顺序栈的基本操作  
11. 规定： S是SeqStack类型指针，s->data[0]为栈底元素  
12. (1)进栈操作  
13. 进栈时，需要将S-＞top加1  
14. 　 ①S-＞top==StackSize-1表示栈满  
15.  　②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。  
16. (2)出栈操作  
17. 　退栈时，需将S-＞top减1  
18. 　 ①S-＞top<0表示空栈  
19. 　 ②"下溢"现象——当栈空时，做退栈运算产生的溢出现象。  
20.  置栈空  
21.   void InitStack（SeqStack *S）  
22.     {//将顺序栈置空  
23.         S->top=-1;  
24.     }   
25.   
26. 判栈空  
27.   int StackEmpty（SeqStack *S）  
28.     {  
29.         return S->top==-1;  
30.     }  
31.   
32. 判栈满  
33.   int StackFull（SeqStack *S）  
34.      {  
35.        return S->top==StackSize-1;  
36.      }  
37.  进栈  
38.   void Push（SeqStack *S，int x）  
39.      {  
40.        if (StackFull(S))  
41.              printf("Stack overflow"); //上溢，退出运行  
42.        S->data[++S->top]=x;//栈顶指针加1后将x入栈  
43.      }  
44.   
45.  退栈  
46.   DataType Pop（SeqStack *S）  
47.     {  
48.       if(StackEmpty(S))  
49.         {  
50.              printf("Stack underflow"); //下溢，退出运行  
51.              exit(0);  
52.         }  
53.             
54.       return S->data[S->top--];//栈顶元素返回后将栈顶指针减1  
55.     }  
56.   
57. 取栈顶元素  
58.   DataType StackTop（SeqStack *S）  
59.     {  
60.        if(StackEmpty(S))  
61.            {  
62.              printf("Stack is empty");   
63.              exit(0);  
64.            }   
65.        return S->data[S->top];  
66.      }  

转载：http://blog.csdn.net/xsf50717/article/details/39934051