<数据结构>栈和队列. 顺序表实现栈,单链表实现队列.

简介: <数据结构>栈和队列. 顺序表实现栈,单链表实现队列

一.栈


1.概念:

栈是一种只能从栈顶入,栈顶出的一种数据结构。先进入的后出来(像弹夹一样)

2.实现一个栈

经过分析,我们用顺序表实现栈是最高效的。

(1)头文件声明

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
 
typedef int STtype;
 
typedef struct Stark
{
  STtype* a;
  int top;
  int capacity;
}ST;
 
//初始化
void STInit(ST* ps);
//入栈
void STPush(ST* ps,STtype x);
//出栈
void STPop(ST* ps);
//得到栈顶数据
STtype STTop(ST* ps);
//统计栈内元素个数
int STSize(ST* ps);
//判断栈是否为空
bool STEmpty(ST* ps);
//打印栈
void STPrint(ST* ps);
//销毁
void STDestory(ST* ps);

(2)函数实现源文件

#define _CRT_SECURE_NO_WARNINGS  1
#include"Stark.h"
void STInit(ST* ps)
{
  assert(ps);
  ps->a = (STtype*)malloc(4 * sizeof(STtype));
  ps->top = 0;
  ps->capacity = 4;
}
 
void STPush(ST* ps, STtype x)
{
  assert(ps);
  //增容
  if (ps->top == ps->capacity)
  {
    STtype* tmp = (STtype*)realloc(ps->a, (ps->capacity + 4) * sizeof(STtype));
    if (tmp == NULL)
    {
      perror("STpush::realloc");
      return;
    }
    else
    {
      ps->a = tmp;
      ps->capacity *= 2;
    }
  }
  ps->a[ps->top] = x;
  ps->top++;
}
 
void STPop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  ps->top--;
}
 
STtype STTop(ST* ps)
{
  assert(ps);
  assert(ps->top > 0);
  return ps->a[ps->top - 1];
}
 
int STSize(ST* ps)
{
  assert(ps);
  return ps->top;
}
 
bool STEmpty(ST* ps)
{
  if (ps->top == 0)
    return true;
  else
    return false;
}
 
void STPrint(ST* ps)
{
  int i = 0;
  for (i = ps->top - 1; i >= 0; i--)
  {
    printf("%d ", ps->a[i]);
  }
}
 
void STDestory(ST* ps)
{
  free(ps->a);
  ps->a = NULL;
  ps->top = 0;
  ps->capacity = 0;
}

(3)测试代码

#define _CRT_SECURE_NO_WARNINGS  1
#include"Stark.h"
void test1()
{
  ST st;
  STInit(&st);
  STPush(&st, 1);
  STPush(&st, 2);
  STPush(&st, 3);
  STPush(&st, 4);
  STPush(&st, 5);
  STPop(&st);
  while (!STEmpty(&st))
  {
    printf("%d", STTop(&st));
    STPop(&st);
  }
}
 
 
int main()
{
  test1();
  return 0;
}

二.队列


1.概念:

队列是一种队尾入,队头出的数据结构。先进去的先出来。用单链表实现较为高效(头删和尾插)

2.实现一个队列

(1)头文件声明

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType a;
}QNode;
 
typedef struct Queue
{
  QNode* head;
  QNode* tail;
}Queue;
 
void QueueInit(Queue* pq);
void QueueDestory(Queue* pq);
//队尾入
void QueuePush(Queue* pq, QDataType x);
//队头出
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//取数据的个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

(2)函数实现源文件

#define _CRT_SECURE_NO_WARNINGS  1
#include"Queue.h"
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = NULL;
  pq->tail = NULL;
}
void QueueDestory(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = NULL;
  pq->tail = NULL;
}
//尾插
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("QueuePush::malloc");
    return;
  }
  //对新开的结点初始化
  newnode->a = x;
  newnode->next = NULL;
  if (pq->tail == NULL)
  {
    pq->head = newnode;
    pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = pq->tail->next;
  }
}
 
//头删
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  //如果只有一个元素,会导致tail被free 变成野指针的问题
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = NULL;
    pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}
 
//取队头数据
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(pq->head);
  return pq->head->a;
}
 
//取队尾数据
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(pq->tail);
  return pq->tail->a;
}
 
//取数据的个数
int QueueSize(Queue* pq)
{
  assert(pq);
  int size = 0;
  QNode* cur = pq->head;
  while (cur)
  {
    size++;
    cur = cur->next;
  }
  return size;
}
 
//判空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}

(3)测试代码

#define _CRT_SECURE_NO_WARNINGS  1
#include"Queue.h"
void test1()
{
  Queue pq;
  QueueInit(&pq);
  QueuePush(&pq, 1);
  QueuePush(&pq, 2);
  QueuePush(&pq, 3);
  QueuePush(&pq, 4);
  QueuePush(&pq, 5);
  int sz = QueueSize(&pq);
  while (!QueueEmpty(&pq))
  {
    printf("%d ", QueueFront(&pq));
    QueuePop(&pq);
  }
  printf("\n%d\n", sz);
 
}
 
 
int main()
{
  test1();
  return 0;
}


目录
相关文章
|
3天前
数据结构——栈和队列
数据结构——栈和队列
7 1
|
6天前
|
存储 算法 调度
数据结构与算法-栈篇
数据结构与算法-栈篇
12 3
|
3天前
|
存储 机器学习/深度学习 算法
【数据结构与算法】:手搓顺序表(Python篇)
【数据结构与算法】:手搓顺序表(Python篇)
|
3天前
|
存储 算法 C++
【数据结构与算法】:带你手搓顺序表(C/C++篇)
【数据结构与算法】:带你手搓顺序表(C/C++篇)
|
3天前
数据结构 栈 / 队列(第9天)
数据结构 栈 / 队列(第9天)
|
3天前
|
存储 算法 程序员
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
【C++进阶】深入STL之 栈与队列:数据结构探索之旅
12 4
|
4天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
14天前
|
存储 缓存 算法
【数据结构】栈和队列的模拟实现(两个方式实现)
【数据结构】栈和队列的模拟实现(两个方式实现)
|
6天前
数据结构初阶 栈
数据结构初阶 栈
10 1
|
11天前
|
算法
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
数据结构和算法学习记录——栈和队列作业(实现链栈上的进栈、实现链栈上的退栈、实现链队上的入队列)
13 0

热门文章

最新文章