栈的基本操作有初始化栈,判栈是否为空,入栈,出栈,获取栈顶元素。
栈可分为两种存储结构:顺序栈和链栈。
顺序栈
顺序栈结构:
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);
}