【数据结构专栏】动态扩容顺序栈详解-阿里云开发者社区

顺序栈的定义

栈（stack），是仅限在表尾进行插入或者删除操作的线性表，因此，对栈来说，表尾端有其特殊含义，称为栈顶，表头端则称为栈底，不含元素的空表称为空栈。栈的修改是按照后进先出的原则进行的，因此，栈也被称为后进先出的线性表。

结构体定义

我们定义一个栈顶指针top和一个栈底指针base，栈顶指针和栈顶指针一开始指向同一片空间。

所以top==base可以作为栈空的标记。

当插入一个新数据时，栈顶指针加一，删除一个元素时，栈顶指针减一。

所以当顺序栈非空时，栈顶指针永远在栈顶元素的下一位。

#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
#define maxsize 100
#define inc 10
typedef struct Sqstack
{
  int* base;//栈顶指针
  int* top;//栈底指针
  int stacksize;//栈的容量
}stack;

顺序栈的初始化

上面也说了，顺序栈一开始栈顶指针和战地指针是指向一块空间的，因此这里就让栈顶指针和栈底指针相等。

我们使用动态内存开辟空间，先给栈一个默认的空间大小。

如果不够，后面的入栈会检测到并开辟空间。

如果空间开辟失败，就退出。

void InitStack(stack& s)
{
  s.base = (int*)malloc(sizeof(int) * maxsize);
  if (!s.base) exit(0);
  s.top=s.base;
  s.stacksize = maxsize;
}

判断顺序栈是否为空

这里没什么好说的，如果栈顶指针和栈底指针指向同一片空间，那就说明它们中间没有数据，顺序栈是空栈。

int isEmpty(stack s)
{
  if (s.base==s.top)
  {
  return 1;
  }
  return 0;
}

求顺序栈的长度

栈顶指针减去栈底指针的值即为顺序栈的长度。

int stacklength(stack s)
{
  return s.top - s.base;
}

清空顺序栈

如果顺序栈不是空栈，就让栈顶指针等于栈底指针，这就在逻辑上清空了顺序栈的元素。

如果顺序表是空栈，就表明顺序栈已经清空，不需要重复操作。

void stackclean(stack& s)
{
  if (s.base)
  {
  s.top = s.base;
  printf("顺序栈清空成功\n");
  }
  else
  {
  printf("顺序栈已清空，无需再次重复操作\n");
  }
}

销毁顺序栈

我们直接用delete函数来销毁栈底指针所指向的空间，也就是顺序栈。

之后不要忘记将栈顶指针和栈底指针置空，否则会造成内存泄露的问题。

void destorystack(stack& s)
{
  if (s.base)
  {
  delete(s.base);
  s.stacksize = 0;
  s.base = NULL;
  s.top = NULL;
  printf("销毁成功\n");
  }
  else
  {
  printf("栈已经被销毁，无需销毁\n");
  }
}

顺序栈的入栈

当顺序栈里的空间不够用的时候，就需要动态的开辟空间。

使用realloc函数来开辟新的空间，并让栈底指针指向这一片空间。

需要注意的是，栈顶指针和栈底指针在新空间的位置需要我们重新定义。

stacksize也要加上我们之前定义的增加量。

void push(stack& s,int e)
{
  if ((s.top - s.base) >= s.stacksize)
  {
  s.base = (int*)realloc(s.base, (maxsize + inc) * sizeof(int));
  if (!s.base) perror("realloc");
  s.top = s.base + s.stacksize;
  s.stacksize += inc;
  }
  else
  {
  *(s.top) = e;
  s.top++;
  printf("添加成功\n" );
  }
}

顺序栈的出栈

这里用到了之前判断顺序栈是否为空的函数。

如果为空，则打印无法弹出。

不为空，先让栈顶指针减一到栈顶第一个元素的位置，再将其值复制给指针变量e。成功弹出元素。

void pop(stack& s,int &e)
{
  if (isEmpty(s))
  {
  printf("栈为空，无法弹出\n");
  }
    else
  {
  if (s.top != s.base)
  {
    s.top--;
    e = *(s.top);
    printf("成功弹出\n");
  }
  }
}

求栈顶元素

求栈顶元素的操作看起来和出栈的操作一模一样。

是不是有的小伙伴会担心这里的操作会把数据弹出？？

那你就忽略了一个点，这里函数声明里所传的是一级指针，并没有改变实参的能力。

也就是说，这里函数声明里的形参只是实参的临时拷贝而已。翻不起风浪。

int top(stack s)
{
  if (isEmpty(s))
  {
  printf("栈为空，没有栈顶元素\n") ;
  return -1;
  }
  else
  {
  s.top--;
  return *(s.top);
  }
}

顺序栈的遍历

这里需要用到上面求长度的函数，求出长度遍历并打印顺序栈元素即可。

void traverse(stack s)
{
  int length = stacklength(s);
  if (length > 0)
  {
  for (int i = 0; i < stacklength(s); i++)
  {
    printf("%d ", s.base[i]);
  }
  }
  else
  {
  printf("顺序栈为空\n");
  }
}

菜单的打印

void menu()
{
  printf("**********************************\n");
  printf("1.初始化\n");
  printf("2.判断栈是否为空\n");
  printf("3.求栈的长度\n");
  printf("4.清空栈\n");
  printf("5.销毁栈\n");
  printf("6.入栈\n");
  printf("7.出栈\n");
  printf("8.求栈顶元素\n");
  printf("9.遍历顺序栈\n");
  printf( "10.退出\n");
  printf( "**********************************\n" );
}

顺序栈的代码实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<errno.h>
typedef struct Sqstack
{
  int* base;//栈顶指针
  int* top;//栈底指针
  int stacksize;//栈的容量
}stack;
#define maxsize 100
#define inc 10
void InitStack(stack& s)
{
  s.base = (int*)malloc(sizeof(int) * maxsize);
  if (!s.base) exit(0);
  s.top=s.base;
  s.stacksize = maxsize;
}
int isEmpty(stack s)
{
  if (s.base==s.top)
  {
  return 1;
  }
  return 0;
}
int stacklength(stack s)
{
  return s.top - s.base;
}
void stackclean(stack& s)
{
  if (s.base)
  {
  s.top = s.base;
  printf("顺序栈清空成功\n");
  }
  else
  {
  printf("顺序栈已清空，无需再次重复操作\n");
  }
}
void destorystack(stack& s)
{
  if (s.base)
  {
  delete(s.base);
  s.stacksize = 0;
  s.base = NULL;
  s.top = NULL;
  printf("销毁成功\n");
  }
  else
  {
  printf("栈已经被销毁，无需销毁\n");
  }
}
void push(stack& s,int e)
{
  if ((s.top - s.base) >= s.stacksize)
  {
  s.base = (int*)realloc(s.base, (maxsize + inc) * sizeof(int));
  if (!s.base) perror("realloc");
  s.top = s.base + s.stacksize;
  s.stacksize += inc;
  }
  else
  {
  *(s.top) = e;
  s.top++;
  printf("添加成功\n" );
  }
}
void pop(stack& s,int &e)
{
  if (isEmpty(s))
  {
  printf("栈为空，无法弹出\n");
  }
    else
  {
  if (s.top != s.base)
  {
    s.top--;
    e = *(s.top);
    printf("成功弹出\n");
  }
  }
}
void traverse(stack s)
{
  int length = stacklength(s);
  if (length > 0)
  {
  for (int i = 0; i < stacklength(s); i++)
  {
    printf("%d ", s.base[i]);
  }
  }
  else
  {
  printf("顺序栈为空\n");
  }
}
int top(stack s)
{
  if (isEmpty(s))
  {
  printf("栈为空，没有栈顶元素\n") ;
  return -1;
  }
  else
  {
  s.top--;
  return *(s.top);
  }
}
void menu()
{
  printf("**********************************\n");
  printf("1.初始化\n");
  printf("2.判断栈是否为空\n");
  printf("3.求栈的长度\n");
  printf("4.清空栈\n");
  printf("5.销毁栈\n");
  printf("6.入栈\n");
  printf("7.出栈\n");
  printf("8.求栈顶元素\n");
  printf("9.遍历顺序栈\n");
  printf( "10.退出\n");
  printf( "**********************************\n" );
}
int main()
{
  int choice;
  stack s;
  int e1, e2;
  while (1)
  {
  menu();
  scanf("%d",&choice);
  switch (choice)
  {
  case 1:
    InitStack(s);
    printf( "初始化成功\n" );
    break;
  case 2:
    if (isEmpty(s))
    printf("栈为空\n" );
    else
    printf("栈不为空\n");
    break;
  case 3:
    printf("栈的长度为%d\n", stacklength(s));
    break;
  case 4:
    stackclean(s);
    break;
  case 5:
    destorystack(s);
    break;
  case 6:
    printf("请输入想要入栈的元素值:>");
    scanf("%d",&e1);
    push(s, e1);
    break;
  case 7:
    pop(s, e2);
    printf("弹出的元素为%d\n" ,e2 );
    break;
  case 8:
    if (top(s) != -1)
    printf("栈顶元素为%d\n" , top(s) );
    break;
  case 9:
    traverse(s);
    printf("\n");
    break;
  case 10:
    printf ( "成功退出\n" );
    exit(0);
  default:
    printf ("输入有误，请重新输入\n" );
    break;
  }
  }
}

运行实例

866f48502d4dfb66eb96541763cb6546_713766e2c568481cae3c5d199144fe7d.png

3eb6832c97114b2837c2eecbe91da085_1d77d6edefa14970b2d2319f0a56c1ce.png

c0ed301154d6643d9e47ec7e55aded60_c14f36a3a8e943ee947e835b33cbce89.png

7faa24fc7cd53920865ce377d6ef5f3a_0d94a88cb2ff4d46a0eaab2f44022194.png

总结

感谢观看，本文到这里就结束了，如果觉得有帮助，请给文章点个赞吧，让更多的人看到。🌹 🌹 🌹

cad3f4971ac28288f5f73c67c1f7b77b_7673ea0a00c3431893891e0c2913a10e.jpeg

也欢迎你，关注我。👍 👍 👍

原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！下期再见。🎉

【数据结构专栏】动态扩容顺序栈详解