🦃一.栈

🐔（1）什么是栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈，出数据也在栈顶。

🐣（2）栈的实现：

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。因为栈即插入和删除（入栈和出战栈）都是在线性表的尾部进行操作，数组的尾部的插如和删除的时间复杂度都是 O(1) ,而如果是链式结构，去实现栈结构，针对尾插和尾删的时间复杂度都是 O(n) ,而双向循环带头的链表，虽然可以解决这个问题，但是.......

我们将栈的实现分为以下各个部分：

1.栈的定义 (StactInit)

typedef int STDateType;  //数据类型
typedef struct Stact
{
  STDateType* date; //数组
  int capacity;   //栈的容量
  int top;      //栈内数据的个数
}ST;
ST* StactInit()
{
  ST* Stact = (ST*)malloc(sizeof(ST));  //创建栈的结构
    //栈的结构初始化
  Stact->capacity = 4; 
  Stact->top = 0;
  Stact->date = (STDateType*)malloc(sizeof(STDateType)*Stact->capacity);
    //返回栈
  return Stact;
}

2.栈的销毁 (StactDestroy)

void StactDestory(ST* Stact)
{
  assert(Stact);
  //先释放数组申请的空间
  free(Stact->date);
  Stact->date = NULL;
  Stact->capacity = 0;
  Stact->top = 0;
  //在释放栈的结构体空间
  free(Stact);
}

3.栈的StactPushBank操作 (入栈)

void StactPushBank(ST* Stact, STDateType x)
{
  //断言Stact,当进行Push时，栈结构必须存在(Stact!=NULL)，
  //如果不存也就是栈是空(Stact==NULL),那Push的操作就是非法的
  assert(Stact);
  //每次对栈的底层是数组，所以每次都要检查是否需要扩容
  if (Stact->capacity == Stact->top)
  {
    STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
    if (tmp==NULL)
    {
      perror("realloc");
      exit(-1);
    }
    Stact->date = tmp;
    Stact->capacity *= 2;
  }
  //将x入栈，数组的栈内数据的个数加一
  Stact->date[Stact->top++] = x;
}

4.栈的StactPopBank操作 (出栈)

void StactPopBank(ST* Stact)
{
  assert(Stact);
  //当栈已经空了，还去出栈就是非法了
  assert(!StactEmpty(Stact));  
  Stact->top--;
}

5.栈的 StactTop (得到栈顶元素)

STDateType StactTop(ST* Stact)
{
  assert(Stact);
  //当栈已经空了，无法获取栈顶元素
  assert(!StactEmpty(Stact));
  return Stact->date[Stact->top - 1];
}

6.栈的StactSize (元素个数)

int StactSize(ST* Stact)
{
  assert(Stact);
  return Stact->top;
}

7.栈的判空 (StactEmpty)

bool StactEmpty(ST* stact)
{
  assert(stact);
  //当栈内数据个数为0时，栈为空
  return stact->top == 0;
}

测试：

void Print(ST* Stact)
{
  assert(Stact);
  for (int i = 0; i < Stact->top; i++)
  {
    printf("%d ", Stact->date[i]);
  }
  printf("\n");
}
int main()
{
  ST* Stact= StactInit();
  StactPushBank(Stact, 100); 
  StactPushBank(Stact, 200); 
  StactPushBank(Stact, 300); 
  StactPushBank(Stact, 400); 
  Print(Stact);
  printf("StactSize:%d\n",StactSize(Stact));
  //Pop一次
  StactPopBank(Stact);
  Print(Stact);
  printf("StactSize:%d\n", StactSize(Stact));
  StactDestory(Stact);
  return 0;
}

🌱（3）.栈的应用

（1）例题

若进栈序列为 1,2,3,4 ，进栈过程中可以出栈，则下列不可能的一个出栈序列是（）

A 1,4,3,2

B 2,3,4,1

C 3,1,4,2

D 3,4,2,1

答案：C

分析：选项A，1进1出，2进3进4进，4出3出2出，所以出栈顺序1，4，3，2，选项A正确。

选项B，1进2进，2出，3进3出，4进，4出1出，所以出栈顺序2，3，4，1，选项B正确。

选项C，1进2进3进，3出，此时想要出2，就必须先出栈1，所以选项C错误。

选项D，1进2进3进，3出，4进，4出2出1出，所以出栈顺序3，4，2，1，选项D正确。

（2）例题

LeetCode ———— 20. 有效的括号

题目描述：

思路分析：

遇到左括号就进栈，遇到右括号就出栈，将出栈的左括号与右括号进行匹配，如果匹配成功就继续，如果匹配失败就返回false。

//栈结构
typedef char STDateType;
typedef struct Stact
{
  STDateType* date;
  int capacity;
  int top;
}ST;
ST* StactInit();
void StactPushBank(ST* Stact, STDateType x);
int StactSize(ST* Stact);
void StactDestory(ST* Stact);
void StactPopBank(ST* Stact);
STDateType StactTop(ST* Stact);
bool StactEmpty(ST* stact);
ST* StactInit()
{
  ST* Stact = (ST*)malloc(sizeof(ST));
  Stact->capacity = 4;
  Stact->top = 0;
  Stact->date = (STDateType*)malloc(sizeof(STDateType) * Stact->capacity);
  return Stact;
}
void StactPushBank(ST* Stact, STDateType x)
{
  assert(Stact);
  if (Stact->capacity == Stact->top)
  {
    STDateType* tmp = (STDateType*)realloc(Stact->date, Stact->capacity * 2);
    if (tmp == NULL)
    {
      perror("realloc");
      exit(-1);
    }
    Stact->date = tmp;
    Stact->capacity *= 2;
  }
  Stact->date[Stact->top++] = x;
}
bool StactEmpty(ST* stact)
{
  assert(stact);
  return stact->top == 0;
}
STDateType StactTop(ST* Stact)
{
  assert(Stact);
  assert(!StactEmpty(Stact));
  return Stact->date[Stact->top - 1];
}
void StactPopBank(ST* Stact)
{
  assert(Stact);
  assert(!StactEmpty(Stact));
  Stact->top--;
}
void StactDestory(ST* Stact)
{
  assert(Stact);
  free(Stact->date);
  Stact->date = NULL;
  Stact->capacity = 0;
  Stact->top = 0;
  free(Stact);
}
int StactSize(ST* Stact)
{
  assert(Stact);
  return Stact->top;
}
bool isValid(char* s) {
  //创建栈
  ST* stact = StactInit();
  while (*s)
  {
    //遇到左括号进栈
    if (*s == '(' || *s == '{' || *s == '[')
    {
      StactPushBank(stact, *s);
      s++;
    }
    else
    { //遇到右括号出栈，如果出栈的括号时，
      //栈中已经空，此时括号匹配已经失败
      if (StactEmpty(stact))
      {
        StactDestory(stact);
        return false;
      }
      //如果栈不为空，出栈的左括号，与遇到的右括号匹配
      //如果匹配成功就，继续向后走，匹配失败就返回false
      char ch = StactTop(stact);
      StactPopBank(stact);
      if ((ch == '(' && *s == ')') ||
        (ch == '[' && *s == ']') ||
         ch == '{' && *s == '}')
      {
        s++;
      }
      else
      {
        StactDestory(stact);
        return false;
      }
    }
  }
  //当括号匹配匹配完时，如果栈中还有括号，
  //也就意味着匹配失败。
  if (!StactEmpty(stact))
  {
    StactDestory(stact);
    return false;
  }
  StactDestory(stact);
  return true;
}

🌾二.队列

🌲（1）什么是队列

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾出队列：进行删除操作的一端称为队头。

🌵 (2)队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

1.队列的定义——QueueInit

由于队列是，队尾入数据，队头出数据，为了方便数据的入队，我们除了队头指针，还会设计一个队尾指针。

typedef int QUDateType;
typedef struct QueueNode
{
  QUDateType date;
  struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
  QueueNode* head;
  QueueNode* tail;
  int size;
}Queue;
void QueueInit(Queue* pque)
{
  assert(pque);
  pque->head = NULL;
  pque->tail = NULL;
  pque->size = 0;
}
int main()
{
  Queue Q;
  QueueInit(&Q);
  return 0;
}

2.入队操作——QueuePush

void QueuePush(Queue* pque,QUDateType x)
{
  //断言队列结构，当进行入队操作时，队列结构一定不能为空
  assert(pque);
  //申请空间
  QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
  if (newnode == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  //赋值
  newnode->date = x;
  newnode->next = NULL;
  //如果队列为空，此时入队的就是第一个数据，也将是队列的头尾数据
  if (pque->head == NULL)
  {
    pque->head = pque->tail = newnode;
  }
  //如果队列不为空，就将数据连接到队尾巴后面
  else
  {
    pque->tail->next = newnode;
    pque->tail = newnode;
  }
  //队列中数据个数加一
  pque->size++;
}

3.队列销毁——QueueDestroy

void QueueDestroy(Queue* pque)
{
  assert(pque);
  QueueNode* cur = pque->head;
  while (cur)
  {
    QueueNode* nextnode = cur->next;
    free(cur);
    cur = nextnode;
  }
  pque->head = pque->tail = NULL;
}

4.得到对头数据——QueueFront

QUDateType QueueFront(Queue*pque)
{
  assert(pque);
  assert(!QueueEmpty(pque));
  return pque->head->date;
}

5.队列判空——QueueEmpty

bool QueueEmpty(Queue* pque)
{
  assert(pque);
  return pque->head == NULL && pque->tail == NULL;
}

6.删除对头数据——QueuePop

void QueuePop(Queue* pque)
{
  assert(pque);   //队列结构不能为空
  assert(!QueueEmpty(pque));   //删除数据时队列不能为空 
  //队列中只有一个数据的时候
  if (pque->head->next == NULL)
  {
    free(pque->head);
    pque->tail = pque->head = NULL;
  }
  //队列中数据个数大于1
  else
  {
    QueueNode* popnode = pque->head;
    pque->head = pque->head->next;
    free(popnode);
  }
  //数据个数减一
  pque->size--;
}

7.得到队尾数据——QueueBack

QUDateType QueueBack(Queue* pque)
{
  assert(pque);
  assert(!QueueEmpty(pque));
  return pque->tail->date;
}

8.得到队列中数据个数——QueueSize

int QueueSize(Queue* pque)
{
  assert(pque);
  return pque->size;
}

测试：

int main()
{
  Queue Q;
  QueueInit(&Q);
  //插如100 .200 300 ，400 ，
  QueuePush(&Q, 100);
  QueuePush(&Q, 200);
  QueuePush(&Q, 300);
  QueuePush(&Q, 400);
  //输出队头数据
  printf("%d ", QueueFront(&Q));
  //输出队尾数据
  printf("%d ", QueueBack(&Q));
  //输出队列数据个数
  printf("%d \n", QueueSize(&Q));
  //输出队列中的数据
  while (!QueueEmpty(&Q))
  {
    printf("%d ", Q.head->date);
    QueuePop(&Q);
  }
  //队列销毁
  QueueDestroy(&Q);
  return 0;
}

数据结构——栈，队列，及其结构特点应用。1

🦃一.栈

🐔（1）什么是栈

🐣（2）栈的实现：

🌱（3）.栈的应用

🌾二.队列

🌲（1）什么是队列

🌵 (2)队列的实现

热门文章

最新文章

相关课程

相关电子书