以数制转换问题讲解栈数据结构的基本概念及其在计算机中的应用

一、栈的概念介绍

在我们的生活中，总有这么一些例子，①食堂在堆放餐盘的时候，总是从下往上，在取餐盘的时候，又是从上往下；②最先放入厢式货车的货物，最后才能取出；③普通手枪的子弹夹，先装进弹夹的子弹，最后才会被打出来。类似于这样的场景还有很多，这样的存取顺序，我们称之为先进后出（LIFO）。这种存取方式在解决某些计算机问题的时候非常高效，因此，在计算机科学中抽象出了一种数据结构，专门用于解决后进先出这类科学问题，在计算机中，这种后进先出的数据结构，我们称之为 栈。栈这种数据结构被抽想出来以后，就被广泛的应用于计算机软硬件系统中，在编译系统、操作系统等系统软件和各类应用软件中经常使用栈来高效的完成特定的算法设计。在许多程序语言设计中，函数的调用，就会使用栈来保存形参以及函数的返回值。在硬件层面，有专门的栈寄存器来配合栈数据结构的高效访问。(更好的阅读体验，请访问 程序员在旅途)
　　栈的逻辑结构是一种线性结构，和线性表相同，元素之间是一对一的关系，由于需要保证元素的后进先出规则，因此需要对线性表的运算操作进行一定的限制，即只允许在线性表的一端进行插入和删除来满足栈的要求。因此可以认为栈是限制在表的一端进行插入和删除的线性表。在线性表中允许插入、删除的这一端称为栈顶，栈顶的位置是动态变化的；不允许操作的这一端称为栈底，栈底是固定不变的。当表中没有元素时称为空栈。
　　对于栈而言，常用的操作有：①栈的初始化； ②判断栈是否为空；③入栈；④出栈；⑤取栈顶元素；⑥销毁栈。这些基本的操作是组成复杂程序的基础。栈的示意图如下：

栈示意图.png

栈的物理实现有两种方式，分别为 顺序存储方式 和 链式存储方式。采用顺序存储的栈我们称之为顺序栈，采用链式存储结构的栈称之为链式栈。

二、顺序栈的操作实现

和顺序表的定义实现一样，顺序栈的实现，要分配一块连续的存储空间存放栈中的内容，可以用一维数组来实现，同时定义一个top变量指明当前栈顶的位置。类型描述如下：

#define MAXSIZE 50
typedef struct{
　　ElementType　data[MAXSIZE];
　　int　top;
}SeqStack,*PSeqStack;

定义一个指向栈的指针：

PSeqStack　p　=　(PSeqStack)malloc(sizeof(SeqStack));

由于顺序栈的数据域是静态分配的存储空间，而栈的操作又是一个动态的过程，因此，在入栈的时候，可能出现栈中元素的个数超过栈的最大空间大小，这时候就产生栈的溢出现象，这称之为上溢。在出栈的时候，可能全部元素都出去了，再也没有元素可以出栈了，这也是栈的溢出现象，称之为下溢。在栈的操作实现过程中，要注意溢出的检测。

2.1初始化顺序栈

顺序栈的初始化，就是构造一个空栈，然后返回一个指向顺序表的指针。做法是使用malloc()分配栈这种结构体的存储空间，然后，将栈中top置为-1，标识空栈。代码如下：

PSeqStack init_seqstack(){
　　//给栈分配内存空间
　　PSeqStack p = (PSeqStack)malloc(sizeof(SeqStack));
　　if(p){
　　　　p->top = -1; //top=-1代表空栈；
　　}
　　return p;
}

2.2判断栈是否为空

判断栈中是否有元素，只要判断top是否等于-1即可。（要注意判断p是为非NULL）

int empty_seqstack(PSeqStack p){
　　if(p){
　　　　if(p->top == -1){
　　　　　　return 1; //1代表空栈
　　　　}else{
　　　　　　return 0; //0代表非空栈
　　　　}
　　}else{
　　　　return 1; //1代表空栈
　　}
}

2.3入栈

入栈是在栈的顶部插入元素，由于是逐渐递加的，因此，不需要移动元素。首先判断栈是否已满，若满了，则退出；由于栈的top指向栈顶，只要将入栈元素赋到top+1的位置。同时执行top++即可。

int push_seqstack(PSeqStack p, ElementType x){
　　//栈满则退出
　　if(p->top == MAXSIZE - 1){
　　　　return 0
　　}else{
　　　　//给栈顶元素赋值
　　　　p->top ++;
　　　　p->data[p->top] = x;
　　　　return 1;
　　}
}

2.4出栈

出栈也是在栈的顶部进行元素的删除操作，也是无需移动元素，只要改变top的指向即可，然后把出栈的那个元素返回。思路是：首先判断栈是否为空，若空则退出；否则由于栈的top指向栈顶，只要修改top为top-1即可。

int pop_seqstack(PSeqStack p, ElementType *x){//传进来的是一个指针变量，这个起到保存出栈的数据的目的。
　　if(empty_seqstack(p)){ //栈为空，则无法出栈
　　　　return 0;
　　}
　　*x = p->data[p->top]; //将栈顶元素赋给*x；
　　p->top --;
　　return 1;
}

2.5取栈顶元素

取栈顶元素就是取栈的top变量指向的元素。思路是：首先判断栈是否为空，若空则退出；否则由于栈的top指向栈顶，返回top所指单元的值即可，栈本身不发生变化。

int getTop_seqstack(PSeqStack p, ElementType *x){
　　if(empty_seqstack(p)){ //栈为空，则无法取值
　　　　return 0;
　　}
　　*x = p->data[p->top];
　　return 1;
}

2.6销毁栈

栈被初始化之后就在内存中分配了一块连续的存储空间，因此，如果在使用完之后，必须要将其销毁，释放其占用的空间。

void destory_seqstack(PSeqStack *p){ //注意，这里传入的是*p；是为了释放p指向的地址空间。
　　if(*p){
　　　　free(*p);
　　}
　　*p = NULL;
　　return ;
}

三、链式栈的操作实现

栈的链式存储结构一般用单链表表示，节点结构与单链表的结构相同，由于栈只是栈顶在做插入和删除操作，所以栈顶应该放在单链表的头部。由于不需要为了各个节点的统一操作增加一个头节点，所以栈使用的链表是没有头结点的。链表的节点结构如下：

typedef struct node{
　　ElementType data;
　　struct node *next;
}StackNode,*PStackNode;

放了方便操作，同时强调栈顶是栈的一个属性，我们可以定义如下的栈的结构：

typedef struct{
　　PStackNode top;
}LinkStack,*PLinkStack;

定义一个指向栈的指针：

 PLinkStack p = (PLinkStack)malloc(sizeof(LinkStack));

要注意的是：对于链栈来说，基本不存在栈满的情况，除非内存已经没有使用空间了。对于空栈来说，链表原来的定义是头指针指向空，那么链栈的空其实就是top＝NULL。

3.1初始化空栈

栈在使用之前，要进行初始化，申请栈顶节点需要的内存空间。注意，这里申请的是栈结构LinkStack需要的内存空间，而不是节点结构StackNode的节点空间。入栈的时候，申请的是StackNode节点空间。top的值类型是StackNode。

PLinkStack init_linkstack(){
　　PLinkStack p = (PLinkStack)malloc(sizeof(LinkStack)); //初始化链栈，申请top节点的内存空间
　　if(p){
　　　　p->top = NULL;
　　}
　　return p;
}

3.2判断空栈

在出栈，取栈顶元素之前，首先得要判断栈是否为空，如为空，则不取。

//判断空栈;1表示空栈，0表示非空栈
int empty_linkstack(PLinkStack p){
　　if(p){
　　　　return (p->top == NULL);
　　}
　　return 1;
}

3.3入栈

和顺序栈一样，入栈的概念都是在栈顶插入元素。申请StackNode节点空间，赋给top。

//入栈。1入栈成功，0入栈失败
int push_linkstack(PLinkStack p, ElementType x){
　　PStackNode temp_stacknode = (PStackNode)malloc(sizeof(StackNode));
　　if(temp_stacknode){
　　　　//这里是入栈的核心操作，将最新申请的节点赋给top。
　　　　temp_stacknode->data = x;
　　　　temp_stacknode->next = p->top;
　　　　p->top = temp_stacknode;
　　　　return 1;
　　}else{
　　　　printf("内存空间不足，申请失败\n");
　　　　return 0;
　　}
}

3.4出栈

出栈就是弹出栈顶元素，然后修改top的值。

//出栈。0出栈失败1出栈成功
int pop_linkstack(PLinkStack p, ElementType *x){
　　if(empty_linkstack(p)){
　　　　printf("栈空，不能出栈");
　　　　return 0;
　　}{
　　　　//取栈顶元素，然后将这个top指向的节点free掉。
　　　　*x = p->top->data;
　　　　PStackNode x = p->top;
　　　　p->top = p->top->next;
　　　　free(x);
　　　　return 1;
　　}
}

3.5取栈顶元素

//取栈顶元素
int getTop_linkstack(PLinkStack p, ElementType *x){
　　if(empty_linkstack(p)){
　　　　printf("栈空");
　　　　return 0;
　　}{
　　　　//取栈顶元素，然后将这个top指向的节点free掉。
　　　　*x = p->top->data;
　　　　return 1;
　　}
}

3.6销毁栈

和顺序栈一样，栈结构使用完之后，都要进行销毁，以释放其占用的内存空间。

//销毁栈
void destory_linkstack(PLinkStack *p){
　　if(*p){
　　　　PStackNode x,s;
　　　　x = (*p)->top;
　　　　//遍历栈，然后将其每一个节点都给释放掉。
　　　　while(x){
　　　　　　s = x;
　　　　　　x = x->next;
　　　　　　free(s);
　　　　}
　　　　free(*p);
　　}
　　*p = NULL;
}

四、栈的典型应用实例 — 数制转换问题。

在学习计算机组成原理的时候，会经常的处理各种数制之间进行转换的问题，而辗转相除法就是我们最经常用的一种方法。辗转相除法即是欧几里得算法，主要用于计算两个正整数a，b的最大公约数，应用领域有数学和计算机两个方面，拓展应用领域很广泛，辗转相除法在处理数制转换问题上非常有效，算法效率也很高。
　　将十进制数N转换成r进制的数，采用辗转相除法示意图如下：以N= 1234，r=8为例进行转换 。


辗转相除法示意.png

从上图看，余数由低位向高位依次产生，而八进制数则是从高位到低位输出，具备后进先出的特性，因此恰好可以使用栈来保存这个结果。思路就是将N%r的结果依次入栈，待到N/r=0的时候算法结束，依次出栈即可。程序如下：

4.1顺序栈算法

int numerical_conversition(int n, int r){
　　PSeqStack p;
　　ElementType x;
　　if(!r){
　　　　printf("基数不能为0\n");
　　　　return 0;
　　}
　　p = init_seqstack();
　　if(!p){
　　　　printf("栈初始化失败\n");
　　　　return 0;
　　}
　　while(n){
　　　　//余数依次入栈
　　　　push_seqstack(p,n%r);
　　　　n = n / r;
　　}
　　while(!empty_seqstack(p)){
　　　　//依次出栈
　　　　pop_seqstack(p,&x);
　　　　printf("%d ",x);
　　}
　　printf("\n");
　　destory_seqstack(&p);
　　return 1;
}

4.2 链式栈算法

int numerical_conversition(int n, int r){
　　PLinkStack p;
　　ElementType x;
　　if(!r){
　　　　printf("基数不能为0\n");
　　　　return 0;
　　}
　　p = init_linkstack();
　　if(!p){
　　　　printf("栈初始化失败\n");
　　　　return 0;
　　}
　　while(n){
　　　　//余数依次入栈
　　　　push_linkstack(p,n%r);
　　　　n = n / r;
　　}
　　while(!empty_linkstack(p)){
　　　　//依次出栈
　　　　pop_linkstack(p,&x);
　　　　printf("%d ",x);
　　}
　　printf("\n");
　　destory_linkstack(&p);
　　return 1;
}

完整程序如下：
　　①链式栈

#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;

typedef struct node{
  ElementType  data;
  struct node  *next;
}StackNode,*PStackNode;

typedef struct{
  PStackNode top;
}LinkStack,*PLinkStack;


//初始化空栈
PLinkStack init_linkstack(){

  PLinkStack p = (PLinkStack)malloc(sizeof(LinkStack));  //初始化链栈，申请top节点的内存空间
  if(p){

      p->top = NULL;
  }
  return p;
}

//判断空栈;1表示空栈，0表示非空栈
int empty_linkstack(PLinkStack p){
  if(p){

       return (p->top ==  NULL);
  }

  return 1;
}
//入栈。1入站成功，0入栈失败
int push_linkstack(PLinkStack p, ElementType x){
  PStackNode temp_stacknode = (PStackNode)malloc(sizeof(StackNode));

  if(temp_stacknode){
      //这里是入栈的核心操作，将最新申请的节点赋给top。
      temp_stacknode->data = x;
      temp_stacknode->next = p->top;
      p->top = temp_stacknode;
      return 1;

  }else{

      printf("内存空间不足，申请失败\n");
      return 0;
  }
}
//出栈.0出栈失败1出栈成功
int pop_linkstack(PLinkStack p, ElementType *x){
  if(empty_linkstack(p)){

      printf("栈空，不能出栈");
      return 0;
  }{
      //取栈顶元素，然后将这个top指向的节点free掉。
      *x = p->top->data;
      PStackNode x = p->top;
      p->top = p->top->next;
      free(x);

      return 1;
  }
}
//取栈顶元素
int getTop_linkstack(PLinkStack p, ElementType *x){
  if(empty_linkstack(p)){
      printf("栈空");
      return 0;
  }{
      //取栈顶元素，然后将这个top指向的节点free掉。
      *x = p->top->data;
      return 1;
  }
}
//销毁栈
void destory_linkstack(PLinkStack *p){
  if(*p){

      PStackNode x,s;
      x = (*p)->top;
      //遍历栈，然后将其每一个节点都给释放掉。
      while(x){
          s = x;
          x = x->next;
          free(s);
      }

      free(*p);
  }

  *p = NULL;
}

int numerical_conversition(int n, int r){

  PLinkStack p;
  ElementType x;

  if(!r){
      printf("基数不能为0\n");
      return 0;
  }

  p = init_linkstack();
  if(!p){
      printf("栈初始化失败\n");
      return 0;
  }

  while(n){
      //余数依次入栈
      push_linkstack(p,n%r);
      n = n / r;
  }

  while(!empty_linkstack(p)){
      //依次出栈
      pop_linkstack(p,&x);
      printf("%d ",x);
  }

  printf("\n");
  destory_linkstack(&p);

  return 1;
}

int main(){

  numerical_conversition(1234,8);

  return 0;
}

②顺序栈

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 100

typedef int ElementType;

typedef struct{

    ElementType data[MAXSIZE];
    int top;

}SeqStack,*PSeqStack;


//初始化栈
PSeqStack init_seqstack(){

  //给栈分配内存空间
  PSeqStack  p = (PSeqStack)malloc(sizeof(SeqStack));

  if(p){

      p->top = -1;
  }

  return p;
}

int empty_seqstack(PSeqStack p){
  if(p){

          if(p->top == -1){

              return 1; //1代表空栈
          }else{

              return 0; //0代表非空栈
          }
  }else{

      return 1; //1代表空栈
  }
}

//入栈
int push_seqstack(PSeqStack p, ElementType x){
  //栈满则退出
  if(p->top == MAXSIZE - 1){
      
      return 0;
  }else{

      //给栈顶元素赋值
      p->top ++;
      p->data[p->top] = x;
      
      return 1;
  }
}

//弹出栈
int pop_seqstack(PSeqStack p, ElementType *x){//传进来的是一个指针变量，这个起到保存出栈的数据的目的。

  if(empty_seqstack(p)){  //栈为空，则无法出栈
      return 0;
  }

  *x = p->data[p->top]; //将栈顶元素赋给*x；
  p->top --;

  return 1;
}

//获取栈顶元素
int getTop_seqstack(PSeqStack p, ElementType *x){
  
  if(empty_seqstack(p)){  //栈为空，则无法取值
      return 0;
  }

  *x = p->data[p->top];
  return 1;
}

//销毁栈
void destory_seqstack(PSeqStack *p){ //注意，这里传入的是*p；是为了释放p指向的地址空间。

  if(*p){
      free(*p);
  }

  *p = NULL;
  return ;
}

int numerical_conversition(int n, int r){
  PSeqStack p;
  ElementType x;
  if(!r){
      printf("基数不能为0\n");
      return 0;
  }
  p = init_seqstack();
  if(!p){
      printf("栈初始化失败\n");
      return 0;
  }
  while(n){
      //余数依次入栈
      push_seqstack(p,n%r);
      n = n / r;
  }
  while(!empty_seqstack(p)){
      //依次出栈
      pop_seqstack(p,&x);
      printf("%d ",x);
  }
  printf("\n");
  destory_seqstack(&p);
  return 1;
}

int main(){

   numerical_conversition(1234,8);

  return 0;

}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,542评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,596评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,021评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,682评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,792评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,985评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,107评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,845评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,299评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,612评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,747评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,441评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,072评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,828评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,069评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,545评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,658评论 2赞 350