关注
数据结构:栈的顺序存储结构
栈(stack)是限定在表尾进行插入和删除操作的线性表。我们把允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom)
,栈又称为后进先出(Last In First Out)的线性表,简称LIFO结构。
示例程序:(改编自《大话数据结构》)
C++ Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
#include <iostream>using namespace std;#define MAXSIZE 20 typedef int ElemType;typedef struct { ElemType data[MAXSIZE]; int top; //栈顶指针 } SqStack;/* 构造一个空栈*/ bool InitStack(SqStack *Sq) { Sq->top = - 1 ; //表示空栈 return true ; }/* 置为空栈 */ bool ClearStack(SqStack *Sq) { cout << "Clear Stack ..." << endl; Sq->top = - 1 ; return true ; }bool StackEmpty(SqStack Sq) { if (Sq.top == - 1 ) return true ; else return false ; }int StackLength(SqStack Sq) { cout << "Stack Length : " ; return Sq.top + 1 ; }/* 返回栈顶元素 */ bool GetTop(SqStack Sq, ElemType *ptr) { if (Sq.top != - 1 ) { *ptr = Sq.data[Sq.top]; cout << "Get Top Item " << *ptr << endl; return true ; } return false ; }/* 压栈 */ bool Push(SqStack *Sq, ElemType Elem) { cout << "Push Item " << Elem << endl; if (Sq->top + 1 > MAXSIZE - 1 ) return false ; Sq->data[++Sq->top] = Elem; return true ; }/* 出栈 */ bool Pop(SqStack *Sq, ElemType *ptr) { if (Sq->top == - 1 ) return false ; *ptr = Sq->data[Sq->top--]; cout << "Pop Item " << *ptr << endl; return true ; }bool StackTraverse(SqStack Sq) { cout << "Traverse Stack ..." << endl; if (Sq.top == - 1 ) return false ; for ( int i = 0 ; i <= Sq.top; i++) cout << Sq.data[i] << ' ' ; cout << endl; return true ; }int main( void ) { SqStack Sq; InitStack(&Sq); for ( int i = 0 ; i < 5 ; i++) Push(&Sq, i); StackTraverse(Sq); int result; Pop(&Sq, &result); StackTraverse(Sq); GetTop(Sq, &result); if (!StackEmpty(Sq)) cout << StackLength(Sq) << endl; ClearStack(&Sq); return 0 ; }
输出为: