栈的基本操作-阿里云开发者社区

我们来总体看下数据结构所包含的一些概念

我们可以通过顺序表和链表来实现栈，分别叫做顺序栈和链栈。

栈无疑是数据结构中非常重要的一种存储结构。

我们今天来介绍栈

什么是栈？

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

栈是只能在表的一端进行数据存取的数据结构。我们来看图示。其实还是很好理解的。

我们来回顾下顺序表和链表，我们将栈与之对比。

顺序表的定义

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

我们来看示意图

我们要明白，顺序表是以数组来存储的

其实顺序表在生活中的例子很多

我们来看链表

链表的定义

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

栈其实是一种特殊的线性表

我们来看顺序栈如何创建

我们先来看栈结构

我们来看代码：

typedef struct SqStack
{
  int data[100];
  int top;  
}SqStack;

我们来看图：

top被称为栈顶指针，初始值为负一。前面讲过，栈是一种特殊的线性表，我们的顺序表是线性表的一种，我们的顺序表是通过数组来实现的，所以这里的顺序栈也要通过数组来实现。

我们来看初始化栈,其实就是使栈顶指针指向负一，就是代表了空栈。里面没有任何数据，

void InitStack(SqStack *s)
{
  s->top=-1;
}

感觉一步一步分析就很好理解，哈哈，很简单的。

我们来看如何判断栈空

其实就是看栈顶指针的值

int Stackempty(SqStack *s)
{
  if(s->top==-1)
  return 0;
  else
  return 1; 
}

下面我们来看进栈操作

int push(SqStack *s,int e)
{
  if(s->top==MAX-1)
  { 
  printf("栈满\n");
  return 0;
  }
  s->data[++s->top]=e;
  return 1;  
}

我们再来看出栈

int pop(SqStack *s,int  n)
{
  if(s->top==-1)
  {
  printf("栈空\n");
  return 0;
  }
  n=s->data[s->top--];
  print(n);
  return 1;  
}

代码很重要，但是理解代码的实现思路更重要。

我们来看主函数

int main() {
    int n;
   SqStack *s=InitStack()
    Push(s, 5);
    Push(s, 6);
    Push(s, 4);
    Push(s, 7);
    pop(s,n)
}

其实啊，我们没必要专们定义结构体，我们可以这样：

由于更好理解，我们给出完整代码

#include <stdio.h>
//元素elem进栈
int push(int* a,int top,int elem){
    a[++top]=elem;
    return top;
}
//数据元素出栈
int pop(int * a,int top){
    if (top==-1) {
        printf("空栈");
        return -1;
    }
    printf("弹栈元素：%d\n",a[top]);
    top--;
    return top;
}
int main() {
    int a[100];
    int top=-1;
    top=push(a, top, 1);
    top=push(a, top, 2);
    top=push(a, top, 3);
    top=push(a, top, 4);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    top=pop(a, top);
    return 0;
}

想想，还很好理解的。

我们来看链栈的相关操作

要用到链式存储结构的特点

来看图：

或者像这样

链栈不是链表，终究只能在一端操作

就像这样

我们来看它的结点结构：

这里和链表的定义结点太像了

typedef struct lineStack{
    int data;
    struct lineStack* next;
};

我们来看压栈操作

lineStack* push(lineStack* stack,int a) {
     //我们这里进行了空间动态的申请
    lineStack* temp = (lineStack*)malloc(sizeof(lineStack));
    temp->data = a;
    //
    temp->next = stack;
    //移动头指针的位置
    stack = temp;
    return stack;

我们再看出栈

lineStack* pop(lineStack* stack) {
    if (stack) {
      //声明一个新指针指向栈顶节点
        lineStack *p = stack;
        //更新头节点
        stack = stack->next;
        printf("出栈元素：%d \n",p->data);
        if (stack) {
            printf("新栈顶元素：%d\n",stack->data);
        }
        else {
            printf("栈已空\n");
        }
        free(p);
    }
    else {
        printf("栈内没有元素\n");
        return stack;
    }
    return stack;

我们来看完整的代码

#include<stdlib.h>
#include<stdio.h>
//链表中节点结构
typedef struct lineStack{
    int data;
    struct lineStack* next;
};
//压栈 stack 当前链栈  a 入栈元素
lineStack* push(lineStack* stack,int a) {
     //创建存储新元素的节点
    lineStack* temp = (lineStack*)malloc(sizeof(lineStack));
    temp->data = a;
    //新节点与头节点建立关联
    temp->next = stack;
    //更新头指针指向
    stack = temp;
    return stack;
}
//栈顶元素出栈的实现函数
lineStack* pop(lineStack* stack) {
    if (stack) {
      //声明一个新指针指向栈顶节点
        lineStack *p = stack;
        //更新头节点
        stack = stack->next;
        printf("出栈元素：%d ",p->data);
        if (stack) {
            printf("新栈顶元素：%d\n",stack->data);
        }
        else {
            printf("栈已空\n");
        }
        free(p);
    }
    else {
        printf("栈内没有元素\n");
        return stack;
    }
    return stack;
}
int main() {
    lineStack * stack = NULL;
    stack = push(stack, 1);
    stack = push(stack, 2);
    stack = push(stack, 3);
    stack = push(stack, 4);
    stack = pop(stack);
    stack = pop(stack);
    stack = pop(stack);
    stack = pop(stack);
    stack = pop(stack);
    return 0;
}

我们来做一个栈的应用，将输入的二进制转换为十进制。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 20 //初始化栈的容量
#define STACKININCREMENT 10 //每次扩容的容量
typedef char ElemType;
typedef struct
{   //栈底和栈顶指针
  ElemType *base;
  ElemType *top;
  int stackSiize; //记录栈容量
}sqStack;
//初始化栈的操作
void InitStack(sqStack *s)
{
  s->base = (ElemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType));//申请指定的容量
  if(!s->base)//如果申请失败
  {
  exit(0);//退出
  }
  s->top = s->base;//初始栈顶指向栈底
  s->stackSize = STACK_INIT_SIZE; 
}
//压栈的操作
void Push(sqStack *s,ElemType e)
{ //如果空间不足。再申请空间
  if(s->top-s->base>=s->stackSize)
  {
  s->base =(ElemType *)realloc(s-base,(s->stackSize+STACKINCREMENT)*sizeof(ElemType));
  if(!s->base)
  {
    exit(0);
  }
  }
  *(s->top)=e;
  s->top++;
}
void Pop(sqStack *s ,ElemType *e)
{
  if(s->top == s->base)
  {
  return ;
  }
  *e =*--(s->top);
}
int Stacklen(sqStzck s)
{
  return(s.top-s.base);
}
int main()
{
  ElemType c;
  sqStack s;
  int len. i, sum=0;
  printf("请输入二进制数，输入符号#表示结束！\n");
  scanf("%c",&c);
  while(c !='#')
  {
  Push(&s,c);
  scanf("%c",&c);
  }
  getchar();//把回车从缓冲区去掉
  len = StackLen(s);
  printf("栈的当前容量是：%d\n",len);
  for (i = 0;i<len;i++)
  {
  Pop(&s,&c);
  sum = sum + (c-48)*pow(2,i);
  }
  printf("转化为十进制数是：%d",sum);
  return 0;
}

栈的基本操作

热门文章

最新文章

相关课程

相关电子书