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

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

一.栈


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天前
|
存储
数据结构—顺序表(如果想知道顺序表的全部基础知识点,那么只看这一篇就足够了!)
数据结构—顺序表(如果想知道顺序表的全部基础知识点,那么只看这一篇就足够了!)
|
4天前
|
Python
数据结构===队列
数据结构===队列
|
18小时前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
4天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
8 1
|
7天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1
|
3天前
|
缓存 调度
栈和队列的区别
栈和队列的区别
5 0
|
4天前
|
存储 程序员 编译器
堆和栈的区别
堆和栈的区别
|
4天前
|
C++
【洛谷 P1739】表达式括号匹配 题解(栈)
该编程题目要求检查给定的包含字母、运算符和括号的表达式是否括号匹配。输入为一行表达式,以`@`结束。如果括号匹配,输出`YES`,否则输出`NO`。样例包括一个匹配和一个不匹配的表达式。解决方案是使用栈,遇到左括号入栈,遇到右括号时判断栈是否为空,栈空则输出`NO`,否则出栈。当读到`@`时,栈空则输出`YES`,否则输出`NO`。提供的AC代码使用C++实现,通过`stack`处理括号匹配。
7 0
|
4天前
|
存储 Java Python
数据结构===栈
数据结构===栈
|
5天前
|
索引
栈的数组实现
栈的数组实现
5 0

热门文章

最新文章