一、实验目的
1. 掌握栈的顺序表示和实现；
2. 掌握队列的链式表示和实现。
二、实验原理
1.栈是限定仅在表尾进行插入或删除的线性表，又称为先进后出的线性表。栈有两种存储表示，顺序表示（顺序栈）和链式表示（链栈）。栈的主要操作是进栈和出栈，对于顺序栈的进栈和出栈操作要注意判断栈满或栈空。
2.队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端删除元素。队列也有两种存储表示，顺序表示（循环队列）和链式表示（链队）。队列的主要操作是进队和出队，对于顺序的循环队列的进队和出队操作要注意判断队满或队空。凡是涉及队头或队尾指针的修改都要将其对MAXQSIZE求模。
三、实验内容及步骤
（一）实验内容
1.链栈实现数制的转换。
2.实现队列的链式表示和实现。
（二）实验步骤
1. 初始化链栈
2. 插入元素
3. 删除栈顶元素
4. 取栈顶元素
5. 遍历链栈
6. 置空链栈
7. 初始化并建立链队列
8. 入链队列
9. 出链队列
10. 遍历链队列
1. #include<iostream> 2. using namespace std; 3. 4. #define OK 1 5. #define ERROR 0 6. #define OVERFLOW -2 7. 8. typedef int Status; 9. typedef struct SNode { 10. int data; 11. struct SNode *next; 12. } SNode, *LinkStack; 13. 14. Status InitStack(LinkStack &S) { 15. S=NULL; 16. return OK; 17. } 18. bool StackEmpty(LinkStack S) { 19. if (!S) 20. return true; 21. return false; 22. } 23. Status Push(LinkStack &S, int e) { 24. LinkStack p; 25. p=new SNode; 26. p->data=e; 27. p->next=S; 28. S=p; 29. return OK; 30. } 31. Status Pop(LinkStack &S, int &e) { 32. LinkStack p; 33. if(S==NULL) return ERROR; 34. e=S->data; 35. p=S; 36. S=S->next; 37. delete p; 38. return OK; 39. } 40. //算法3.20 数制的转换(链栈实现) 41. void conversion(int N) {//对于任意一个非负十进制数，打印输出与其等值的八进制数 42. int e; 43. LinkStack S; 44. InitStack(S); //初始化空栈S 45. while (N) //当N非零时,循环 46. { 47. Push(S,N%8); //把N与8求余得到的八进制数压入栈S 48. N=N/8; //N更新为N与8的商 49. } 50. while (!StackEmpty(S)) //当栈S非空时，循环 51. { 52. Pop(S, e); //弹出栈顶元素e 53. cout << e; //输出e 54. } 55. } 56. int main() {//对于输入的任意一个非负十进制数，打印输出与其等值的八进制数 57. int n, e; 58. cout << "输入一个非负十进制数:" << endl; 59. cin >> n; 60. conversion(n); 61. return 0; 62. }
