顺序表实现顺序栈的原理
栈是一种特殊的线性表，它只能在线性表的一端进行插入删除操作，允许插入删除的一端称为栈顶，另一端称为栈底。栈的顺序存储即顺序栈是指，用一块连续的内存来存放一个栈，类似于数组，各元素在内存中是一个挨一个的。既然栈也是线性表，那么栈就可以通过线性表来实现，实现顺序栈只需在顺序表的插入删除操作时，只限定在一端操作即可。线性表的顺序存储文章链接如下
线性表可以在头部和尾部进行插入删除，而栈只能在栈顶进行插入删除，那么应该选择顺序表的哪一端作为栈顶呢？
假如线性表头部作为栈顶，如上图所示，也就是说线性表的0号位置处作为栈顶，那么每次插入删除，都需要后面的元素都后移或前移（在0号位置插入时，需要原来的0号变为1号，原来的1号变为2号，以此类推，每个元素都要往后移动一位；删除0号元素时，0号位置空出，应把1号前移变为0号，2号前移变为1号，每个元素都要前移一位），会造成大量的数据移动。所以，应选择线性表的尾部作为栈顶，这样插入删除都不要其他元素移动。
顺序栈的API
1. typedef void SequenceStack; 2. typedef void SequenceStackNode; 3. 4. SequenceStack* SequenceStack_Create(int capacity); 5. 6. void SequenceStack_Destroy(SequenceStack* stack); 7. 8. void SequenceStack_Clear(SequenceStack* stack); 9. 10. int SequenceStack_Push(SequenceStack* stack, SequenceStackNode* node); 11. 12. SequenceStackNode* SequenceStack_Top(SequenceStack* stack); 13. 14. SequenceStackNode* SequenceStack_Pop(SequenceStack* stack); 15. 16. int SequenceStack_Size(SequenceStack* stack);
顺序栈的API实现
1. SequenceStack* SequenceStack_Create(int capacity) 2. { 3. SequenceStack* pTemp = NULL; 4. pTemp = (SequenceStack*)LinearList_Create(capacity); 5. if (pTemp == NULL) 6. { 7. printf("LinearList_Create() err\n"); 8. return NULL; 9. } 10. return pTemp; 11. } 12. 13. void SequenceStack_Destroy(SequenceStack* stack) 14. { 15. LinearList_Destroy((LinearList*)stack); 16. } 17. 18. void SequenceStack_Clear(SequenceStack* stack) 19. { 20. LinearList_Clear((LinearList*)stack); 21. } 22. 23. int SequenceStack_Push(SequenceStack* stack, SequenceStackNode* node) 24. { 25. return LinearList_Insert((LinearList*)stack, node, LinearList_Length((LinearList*)stack)); 26. } 27. 28. SequenceStackNode* SequenceStack_Top(SequenceStack* stack) 29. { 30. return (SequenceStackNode*)LinearList_Get((LinearList*)stack, LinearList_Length((LinearList*)stack) - 1); 31. } 32. 33. SequenceStackNode* SequenceStack_Pop(SequenceStack* stack) 34. { 35. return (SequenceStackNode*)LinearList_Delete((LinearList*)stack, LinearList_Length((LinearList*)stack) - 1); 36. } 37. 38. int SequenceStack_Size(SequenceStack* stack) 39. { 40. return LinearList_Length((LinearList*)stack); 41. }
代码资源已经上传
