举一个简单的例子:在往箱子里面放衣物的时候,放在最上面的衣物总是我们最后放上去的;而当我们从箱子里取出衣物的时候,总是最先拿出上面的。这就是现实生活中的栈。
准确的讲,栈就是一种可以实现“先进后出(或者叫后进先出)”的存储结构。
学过数据结构的人都知道:栈可以用两种方式来实现,一种方法是用数组实现栈,这种栈成为静态栈;另外一种方法是用链表实现栈,这种栈叫做动态栈。
栈中通常存放着程序的局部变量等。栈通常有出栈和入栈操作。
空栈的结构:【其实就是栈顶和栈顶都指向一个无用的头结点】
存有结点的栈结构:【栈顶指针指向栈顶结点,栈底指针指向头结点】
下面是用C实现的一个栈结构的源码及详细注释:
-
#include
-
#include
-
#include
-
-
typedef struct Node
-
{
-
int data;
-
struct Node * pNext;
-
} NODE, * PNODE;
-
-
typedef struct Stack
-
{
-
PNODE pTop;
-
PNODE pBottom;
-
} STACK, * PSTACK;
-
-
void initStack(PSTACK pStack);
-
void pushStack(PSTACK pStack, int val);
-
bool popStack(PSTACK pStack, int * pVal);
-
void traverseStack(PSTACK pStack);
-
bool isEmpty(PSTACK pStack);
-
void clearStack(PSTACK pStack);
-
int main(void)
-
{
-
STACK stack;
-
int val;
-
initStack(&stack);
-
pushStack(&stack, 10);
-
pushStack(&stack, 20);
-
pushStack(&stack, 30);
-
pushStack(&stack, 50);
-
traverseStack(&stack);
-
-
if(popStack(&stack, &val))
-
printf("出栈成功,出栈的元素值为:%d\n", val);
-
else
-
printf(" 出栈失败!");
-
-
clearStack(&stack);
-
traverseStack(&stack);
-
system("pause");
-
return 0;
-
}
-
-
void initStack(PSTACK pStack)
-
{
-
-
pStack->pTop = (PNODE)malloc(sizeof(NODE));
-
if(NULL != pStack->pTop)
-
{
-
-
pStack->pBottom = pStack->pTop;
-
-
pStack->pTop->pNext = NULL;
-
-
}
-
else
-
{
-
printf("内存分配失败!程序退出!\n");
-
exit(-1);
-
}
-
return;
-
}
-
-
void pushStack(PSTACK pStack, int val)
-
{
-
-
PNODE pNew = (PNODE)malloc(sizeof(NODE));
-
-
pNew->data = val;
-
-
pNew->pNext = pStack->pTop;
-
-
pStack->pTop = pNew;
-
return;
-
}
-
-
bool popStack(PSTACK pStack, int * pVal)
-
{
-
if(isEmpty(pStack))
-
{
-
return false;
-
}
-
else
-
{
-
-
PNODE rNode = pStack->pTop;
-
*pVal = rNode->data;
-
pStack->pTop = rNode->pNext;
-
free(rNode);
-
rNode = NULL;
-
return true;
-
}
-
-
}
-
-
void traverseStack(PSTACK pStack)
-
{
-
-
PNODE pNode = pStack->pTop;
-
-
while(pStack->pBottom != pNode )
-
{
-
printf("%d ", pNode->data);
-
pNode = pNode->pNext;
-
}
-
printf("\n");
-
return;
-
}
-
-
bool isEmpty(PSTACK pStack)
-
{
-
if(pStack->pTop == pStack->pBottom)
-
return true;
-
else
-
return false;
-
}
-
-
void clearStack(PSTACK pStack)
-
{
-
if(isEmpty(pStack))
-
{
-
return;
-
}
-
else
-
{
-
-
PNODE p = pStack->pTop;
-
PNODE q = NULL;
-
-
while(p != pStack->pBottom)
-
{
-
q = p->pNext;
-
free(p);
-
p = q;
-
}
-
-
pStack->pTop = pStack->pBottom;
-
return;
-
}
-
}
阅读(711) | 评论(0) | 转发(0) |