数据结构之栈与队列面试题：共享栈（利用一个数组实现两个栈）

时间：2022-01-19 12:59:57

利用数组来实现栈，这个我们已经实现了。今天我们利用一个数组，来实现两个栈的操作。首先我们得考虑，一个数组怎么才能当做两个栈，这里我有两个思路。

  1. 在数组的两头开始相向而插。
  2. 在数组奇偶下标分别插入

考虑到我们两个栈的可延展性，我最终决定利用第二种方式来插入。具体思路如下：

首先我们要创建新的结构体来控制我们这个数组及其栈。

#pragma once

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

typedef char StackType;//定义栈内元素类型

typedef struct _2Stack_ByArray{
  StackType *data;  
  size_t Stack1;//将来插入栈一时的下标
  size_t Stack2;/插入栈二时的下标
  size_t size1;//栈一元素个数
  size_t size2;//栈二元素个数
  size_t capacity; //栈总元素个数，可扩充
}_2Stack;

接下来应该有这个栈的基本操作：

//在这里，我们考虑到，在操作时可能仅仅只对其中某一个栈进行操作
//而不是二者同时进行，所以我们引进一个新的参数choose
//choose来确定要对哪个进行操作


void _2Stack_ByArrayInit(_2Stack* s);//初始化栈

void _2Stack_ByArrayEmpty(_2Stack* s, int choose);//清空栈

void _2Stack_ByArrayPush(_2Stack* s, StackType value, int choose);//入栈

void _2Stack_ByArrayPop(_2Stack* s, int choose);//出栈

int _2Stack_ByArrayTop(_2Stack* s, StackType* value, int choose);//取栈顶元素

接下来我们对里面的操作进行逐一实现

//初始化栈

void _2Stack_ByArrayInit(_2Stack* s)//初始化栈
{
  if(s == NULL) {
    return;
  }

  s->size1 = s->size2 = 0;//首先将两个栈内元素个数置为0
  s->capacity = 1000;//给定元素个数
  s->data = (StackType*)malloc(s->capacity * sizeof(StackType));//申请空间，以备扩容
  s->Stack1 = 0;//栈一初始角标设为0
  s->Stack2 = 1;//栈二初始角标设为1
  return;
}

//清空栈

void _2Stack_ByArrayEmpty(_2Stack* s, int choose)//清空栈
{
  if(s == NULL) {
    return;
  }

  if(choose == 1) {//对栈一进行清空
    s->size1 = 0;//注：清空时不仅仅要清空size，还要将其初始角标清空
    s->Stack1 = 0;
  } else {//对栈二进行清空
    s->size2 = 0;
    s->Stack2 = 1;
  }

  return;
}

//入栈

void _2Stack_ByArraySet(_2Stack* s) //扩容
{
  if(s == NULL) {
    return;
  } 
  if(s->size1 + s->size2 < s->capacity) {//再次判断是否满，起到了双保险作用
    return;
  }

  StackType* new_set = (StackType*)malloc(2*s->capacity*sizeof(StackType)+1);//这里加一是防止capacity为0 
  size_t i = 0;

  for(; i < s->capacity; i++) {//拷贝原来栈内元素
    new_set[i] = s->data[i];
  }
  s->data = new_set;

  return;
}

void _2Stack_ByArrayPush(_2Stack* s, StackType value, int choose)//入栈
{
  if(s == NULL) {
    return;
  }
  if(s->size1 + s->size2 >= s->capacity) {
    _2Stack_ByArraySet(s);//如果栈内元素满了，则扩容
  }

  if(choose == 1) {//这里与顺序栈入栈的操作一样，只是需要判断给栈一还是二进行入栈
    s->data[s->Stack1] = value;
    s->Stack1 += 2;
    s->size1++;
  }
  else {
    s->data[s->Stack2] = value;
    s->Stack2 += 2;
    s->size2++;
  }

  return;
}

//出栈

void _2Stack_ByArrayPop(_2Stack* s, int choose)//出栈
{
  if(s == NULL) {
    return;
  }

  if(choose == 1) {
    if(s->size1 == 0) {//判断是否为空栈
      return;
    }
    s->Stack1 -= 2;
    s->size1--;
  } else {
    if(s->size2 == 0) {//判断是否为空栈
      return;
    }
    s->Stack2 -= 2;
    s->size2--;
  }
  return;
}

//取栈顶元素

int _2Stack_ByArrayTop(_2Stack* s, StackType* value, int choose)//取栈顶元素
{
  if(s == NULL) {
    return -1;
  }

  if(choose == 1) {
    if(s->size1 == 0) {
      return -1;
    }
    *value = s->data[s->Stack1-2];
    return 1;
  } else {
    if(s->size2 == 0) {
      return -1;
    }
    *value = s->data[s->Stack2-2];
    return 1;
  }
}

为了我们再测试时方便观察，我们对打印栈内元素进行实现。

//打印栈内元素

void _2Stack_ByArrayPrint(_2Stack* s, int choose)//打印栈
{
  if(s == NULL) {
    return;
  }

  if(choose == 1) {
    size_t i = 0;
    for(; i < s->Stack1; i+=2) {
      printf("%c ",s->data[i]);
    }
  } else {
    size_t i = 1;
    for(; i < s->Stack2; i+=2) {
      printf("%c ",s->data[i]);
    }
  }
  printf("\n");
  return;
}

下面是测试代码：

//测试代码如下

void TestPush()
{
  HEAD;
  _2Stack s;
  _2Stack_ByArrayInit(&s);
  _2Stack_ByArrayPush(&s,'a',1);
  _2Stack_ByArrayPush(&s,'b',1);
  _2Stack_ByArrayPush(&s,'c',1);
  _2Stack_ByArrayPush(&s,'d',1);
  _2Stack_ByArrayPrint(&s, 1);

  _2Stack_ByArrayPush(&s,'x',2);
  _2Stack_ByArrayPush(&s,'y',2);
  _2Stack_ByArrayPush(&s,'z',2);
  _2Stack_ByArrayPush(&s,'n',2);
  _2Stack_ByArrayPrint(&s, 2);

  _2Stack_ByArrayEmpty(&s, 1);
  _2Stack_ByArrayPrint(&s, 1);
}

void TestPop()
{
  HEAD;
  _2Stack s;
  _2Stack_ByArrayInit(&s);
  _2Stack_ByArrayPop(&s, 2);
  _2Stack_ByArrayPrint(&s, 1);

  _2Stack_ByArrayPush(&s,'a',1);
  _2Stack_ByArrayPush(&s,'b',1);
  _2Stack_ByArrayPush(&s,'c',1);
  _2Stack_ByArrayPush(&s,'d',1);
  _2Stack_ByArrayPrint(&s, 1);
  _2Stack_ByArrayPop(&s, 1);
  _2Stack_ByArrayPrint(&s, 1);

  _2Stack_ByArrayPush(&s,'x',2);
  _2Stack_ByArrayPush(&s,'y',2);
  _2Stack_ByArrayPush(&s,'z',2);
  _2Stack_ByArrayPush(&s,'n',2);
  _2Stack_ByArrayPrint(&s, 2);
  _2Stack_ByArrayPop(&s, 2);
  _2Stack_ByArrayPop(&s, 2);
  _2Stack_ByArrayPrint(&s, 2);
}

void TestTop()
{
  HEAD;
  _2Stack s;
  StackType value;
  int ret;
  _2Stack_ByArrayInit(&s);
  ret = _2Stack_ByArrayTop(&s, &value, 1);
  printf("expected ret -1, actual ret %d\n",ret);
  _2Stack_ByArrayPush(&s,'a',1);
  _2Stack_ByArrayPush(&s,'b',1);
  _2Stack_ByArrayPush(&s,'c',1);
  _2Stack_ByArrayPush(&s,'d',1);
  _2Stack_ByArrayPrint(&s, 1);
  ret = _2Stack_ByArrayTop(&s, &value, 1);
  printf("expected ret 1, actual ret %d\n",ret);
  printf("expected value d, actual ret %c\n",value);

  _2Stack_ByArrayPush(&s,'x',2);
  _2Stack_ByArrayPush(&s,'y',2);
  _2Stack_ByArrayPush(&s,'z',2);
  _2Stack_ByArrayPush(&s,'n',2);
  _2Stack_ByArrayPrint(&s, 2);
  ret = _2Stack_ByArrayTop(&s, &value, 2);
  printf("expected ret 1, actual ret %d\n",ret);
  printf("expected value n, actual ret %c\n",value);
}

int main()
{
  TestPush();
  TestPop();
  TestTop();

  printf("\n");
  printf("\n");
  printf("\n");
  printf("\n");
  printf("\n");
  return 0;
}

欢迎大家共同讨论，如有错误及时联系作者指出，并改正。谢谢大家！

标签：

相关文章