打印
[文档下载]

数据结构->栈

[复制链接]
752|3
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
奥德赛|  楼主 | 2016-1-15 21:19 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
数据结构中的栈是什么
  举一个简单的例子:在往箱子里面放衣物的时候,放在最上面的衣物总是我们最后放上去的;而当我们从箱子里取出衣物的时候,总是最先拿出上面的。这就是现实生活中的栈。
  准确的讲,栈就是一种可以实现“先进后出(或者叫后进先出)”的存储结构。
  学过数据结构的人都知道:栈可以用两种方式来实现,一种方法是用数组实现栈,这种栈成为静态栈;另外一种方法是用链表实现栈,这种栈叫做动态栈。
  栈中通常存放着程序的局部变量等。栈通常有出栈和入栈操作。
  栈的结构
  空栈的结构:【其实就是栈顶和栈顶都指向一个无用的头结点】
  存有结点的栈结构:【栈顶指针指向栈顶结点,栈底指针指向头结点】
  栈的实现
  下面是用C实现的一个链栈结构的源码及详细注释:
#include
  #include
  #include
  //定义结点结构体
  typedef struct Node
  {
  int data; //内容
  struct Node * pNext; //指向下一结点的指针
  } NODE, * PNODE; //NODE等价于struct Node, PNODE等价于struct Node *
  //定义栈的结构体
  typedef struct Stack
  {
  PNODE pTop; //栈顶结点
  PNODE pBottom; //栈底结点
  } STACK, * PSTACK; //STACK等价于struct Stack, PSTACK等价于struct Stack *
  //函数声明
  void initStack(PSTACK pStack); //对栈进行初始化的函数
  void pushStack(PSTACK pStack, int val); //入栈的函数
  bool popStack(PSTACK pStack, int * pVal);//出栈的函数,*pVal用来保存出栈的元素内容
  void traverseStack(PSTACK pStack); //遍历栈的函数
  bool isEmpty(PSTACK pStack); //判断栈是否为空的函数
  void clearStack(PSTACK pStack); //清空栈的函数


沙发
奥德赛|  楼主 | 2016-1-15 21:20 | 只看该作者
//栈调用示例
int main(void)
  {
  STACK stack; //定义一个栈变量,STACK等价于struct 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)
  {
  //创建一个空结点,让pTop指向它
  pStack->pTop = (PN ODE)malloc(sizeof(NODE));
  if(NULL != pStack->pTop)
  {
  //将pBottom也指向空节点
  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不能换成pStack->pBottom
  //pTop指向新的结点
  pStack->pTop = pNew;
  return;
  }
  bool popStack(PSTACK pStack, int * pVal)
  {
  if(isEmpty(pStack))
  {
  return false;
  }
  else
  {
  //先保存栈顶元素的地址,然后将pTop指向下一元素,最后释放之前栈顶元素的内存
  PNODE rNode = pStack->pTop;
  *pVal = rNode->data;
  pStack->pTop = rNode->pNext;
  free(rNode);
  rNode = NULL;
  return true;
  }
  }

使用特权

评论回复
板凳
奥德赛|  楼主 | 2016-1-15 21:22 | 只看该作者
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;
  }
  }

栈的典型应用
  生产消费模型常用栈来实现。生产者生产的东西都放入栈中,然后消费者从栈中依次取出东西,当栈顶和栈底指向都指向首结点时,生产的东西就被消耗光了。

使用特权

评论回复
地板
quray1985| | 2016-1-17 20:37 | 只看该作者
堆和栈的区别还是最大的,栈就是把局部变量存入内存当中

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

46

主题

397

帖子

3

粉丝