栈的基本操作有初始化栈，判栈是否为空，入栈，出栈，获取栈顶元素。
栈可分为两种存储结构：顺序栈和链栈。
顺序栈
顺序栈结构：
typedef struct
{
ElemType data[MAXSIZE];
int top;
} SqStack;
顺序栈四个要素：
（1）栈空条件：st.top == -1
（2）栈满条件: st.top == MAXSIZE - 1
（3）进栈条件: st.top++; st.data[st.top] = data;
（4）出栈条件: st.data[st.top] = 0; st.top--;
顺序栈基本操作
#include "stdafx.h" #include <stdlib.h> #define MAXSIZE 10 typedef int ElemType; /* 顺序栈结构 */ typedef struct { ElemType data[MAXSIZE]; //存放栈中元素 int top; //栈指针 } SqStack; void InitStack(SqStack &stack) { stack.top = -1; }; bool IsStackEmpty(SqStack stack) { if (-1 == stack.top) { return true; } return false; } int Push(SqStack &stack, ElemType data) { if (MAXSIZE - 1 == stack.top) { printf("stack is full, push failed!\r\n"); return 1; } printf("Push data : %d\r\n", data); stack.top++; stack.data[stack.top] = data; return 0; } int Pop(SqStack &stack, ElemType &data) { if (IsStackEmpty(stack)) { printf("stack is empty, pop failed!\r\n"); return 1; } data = stack.data[stack.top]; printf("Pop data : %d\r\n", data); stack.data[stack.top] = 0; stack.top--; return 0; } int GetTop(SqStack stack, ElemType &data) { if (IsStackEmpty(stack)) { printf("stack is empty, get top failed!\r\n"); return 1; } data = stack.data[stack.top]; return 0; } void PrintStack(SqStack stack) { int index = stack.top; printf("The element of stack:\r\n"); while (index >= 0) { printf("%d\t", stack.data[index]); index--; } printf("\r\n"); } int main() { ElemType array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int i = 0; int data = 0; SqStack stack = { 0 }; InitStack(stack); for (i = 0; i < sizeof(array)/sizeof(ElemType); i++) { Push(stack, array[i]); } PrintStack(stack); Pop(stack, data); Pop(stack, data); GetTop(stack, data); printf("Top value : %d\r\n", data); PrintStack(stack); return 0; }
链栈
链栈结构：
typedef struct LinkNode
{
ElemType data;
struct LinkNode *next;
} LiStack;
链栈四个要素：
（1）栈空条件：NULL == st->next
（2）栈满条件: 不存在栈满情况
（3）进栈条件: node->next = st->next; st->next = node;
（4）出栈条件: node = st->next; data = node->data; st->next = node->next; free(node);
链栈基本操作
#include "stdafx.h" #include <stdlib.h> typedef int ElemType; typedef struct LinkNode { ElemType data; struct LinkNode* next; } STACK; void InitStack(STACK *&stack) { if (NULL == stack) { stack = (STACK *)malloc(sizeof(STACK)); stack->next = NULL; } } bool IsEmpty(STACK *stack) { if (NULL == stack->next) { return true; } return false; } void Push(STACK *&stack, ElemType data) { STACK *pNewNode = NULL; pNewNode = (STACK *)malloc(sizeof(STACK)); pNewNode->data = data; pNewNode->next = stack->next; stack->next = pNewNode; } void Pop(STACK *&stack, ElemType &data) { STACK *pTmpNode = NULL; if (NULL == stack->next) { return; } pTmpNode = stack->next; data = pTmpNode->data; stack->next = pTmpNode->next; free(pTmpNode); } int GetTop(STACK *stack) { if (NULL != stack->next) { return stack->next->data; } return 0; } void PrintStack(STACK *stack) { STACK *node = stack->next; while (NULL != node) { printf("%d\t", node->data); node = node->next; } printf("\r\n"); } int _tmain(int argc, _TCHAR* argv[]) { ElemType array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9}; int i = 0; int x = 0; STACK *stack = NULL; InitStack(stack); for (i = 0; i < sizeof(array)/sizeof(ElemType); i++) { Push(stack, array[i]); } PrintStack(stack); Pop(stack, x); Pop(stack, x); PrintStack(stack); }
