栈和队列
目录
栈
1、栈的概念及结构
2、栈的实现
2.1 top的指向
2.2 动态增长顺序栈
2.2.1 Stack.h
2.2.2 Stack.c
2.3 链式堆栈
2.3.1 Stack.h
2.3.2 Stack.c
队列
1、队列的概念及结构
2、队列的实现
2.1 链式队列
2.1.1 Queue.h
2.1.2 Queue.c
2.2 顺序循环队列
2.2.1 Queue.h
2.2.2 Queue.c
Tips:
1、栈(一般实现顺序栈)
2、队列(一般实现链式队列)
栈
1、栈的概念及结构
栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
出栈:栈的删除操作叫做出栈。出数据也在栈顶。
2、栈的实现
栈的实现一般可以使用数组或者链表实现,相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。
2.1 top的指向
两种指向没什么区别,以下采取top指向栈顶数据的下一个位置 即 top指向待插入的位置
2.2 动态增长顺序栈
2.2.1 Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
STDataType* _a;
int _top; // 栈顶
int _capacity; // 容量
}Stack;
// 初始化栈
void StackInit(Stack* ps);
// 入栈
void StackPush(Stack* ps, STDataType data);
// 出栈
void StackPop(Stack* ps);
// 获取栈顶元素
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数
int StackSize(Stack* ps);
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps);
// 销毁栈
void StackDestroy(Stack* ps);
2.2.2 Stack.c
#include "Stack.h"
// 初始化栈
void StackInit(Stack* ps)
{
assert(ps);
ps->_a = NULL;
ps->_top = ps->_capacity = 0;
}
//动态申请
void Stackcapacity(Stack* ps)
{
if (ps->_top == ps->_capacity)
{
ps->_capacity = ps->_capacity == 0 ? 4 : 2 * ps->_capacity;
STDataType* tmp = (STDataType*)realloc(ps->_a, ps->_capacity * sizeof(STDataType));
if (tmp == NULL)
{
perror("Stackcapacity()::realloc()");
return;
}
ps->_a = tmp;
}
}
// 入栈
void StackPush(Stack* ps, STDataType data)
{
assert(ps);
Stackcapacity(ps);//动态申请
ps->_a[ps->_top] = data;
ps->_top++;
}
// 出栈
void StackPop(Stack* ps)
{
assert(ps);
if (ps->_top == 0)
{
printf("栈已空\n");
return;
}
ps->_top--;
}
// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
assert(ps);
assert(ps->_top != 0);
return ps->_a[ps->_top - 1];
}
// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
assert(ps);
return ps->_top;
}
// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
int StackEmpty(Stack* ps)
{
assert(ps);
if (ps->_top == 0)
return 1;
else
return 0;
}
// 销毁栈
void StackDestroy(Stack* ps)
{
assert(ps);
free(ps->_a);
ps->_a = NULL;
ps->_top = ps->_capacity = 0;
}
2.3 链式堆栈
2.3.1 Stack.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include "vld.h"
typedef int DataType;
typedef struct snode
{
DataType data;
struct snode* next;
}LSNode;
void StackInitiate(LSNode** head);//初始化
int StackNotEmpty(LSNode* head);//非空,返回1,否则返回0
void StackPush(LSNode* head, DataType x);//入栈
int StackPop(LSNode* head, DataType* x);//出栈,成功,返回1,否则,返回0
int StackTop(LSNode* head, DataType* x);//取栈顶元素,成功,返回1,否则,返回0
void Destroy(LSNode** head);//撤销栈
2.3.2 Stack.c
#include "LinStack.h"
void StackInitiate(LSNode** head)//初始化
{
*head = (LSNode*)malloc(sizeof(LSNode));
if (*head == NULL)
{
perror("StackInitiate():: malloc()");
return;
}
(*head)->next = NULL;
}
int StackNotEmpty(LSNode* head)//非空,返回1,否则返回0
{
if (head->next == NULL)
{
return 0;
}
else
{
return 1;
}
}
void StackPush(LSNode* head, DataType x)//入栈
{
LSNode* s = (LSNode*)malloc(sizeof(LSNode));
if (s == NULL)
{
perror("StackPush():: malloc()");
return;
}
s->data = x;
s->next = head->next;
head->next = s;
}
int StackPop(LSNode* head, DataType* x)//出栈,成功,返回1,否则,返回0
{
if (!StackNotEmpty(head))
{
printf("栈已空!\n");
return 0;
}
else
{
LSNode* del = head->next;
*x = del->data;
head->next = head->next->next;
free(del);
del = NULL;
return 1;
}
}
int StackTop(LSNode* head, DataType* x)//取栈顶元素,成功,返回1,否则,返回0
{
if (!StackNotEmpty(head))
{
printf("栈已空!\n");
return 0;
}
else
{
*x = head->next->data;
return 1;
}
}
void Destroy(LSNode** head)//撤销栈
{
/*LSNode* p = *head;
LSNode* del;
while( p != NULL)
{
del = p;
p = p->next;
free(del);
}
del = NULL;*/
while (StackNotEmpty(*head))
{
LSNode* del = *head;
*head = (*head)->next;
free(del);
}
free(*head);
*head = NULL;
}
队列
1、队列的概念及结构
队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一端称为队尾
出队列:进行删除操作的一端称为队头
2、队列的实现
队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为在数组头上出数据效率比较低。
2.1 链式队列(rear初始化为NULL,之后指向队尾元素)
2.1.1 Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int QDataType;
// 链式结构:表示队列
typedef struct QListNode
{
struct QListNode* _next;
QDataType _data;
}QNode;
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;
// 初始化队列
void QueueInit(Queue* q);
// 队尾入队列
void QueuePush(Queue* q, QDataType data);
// 队头出队列
void QueuePop(Queue* q);
// 获取队列头部元素
QDataType QueueFront(Queue* q);
// 获取队列队尾元素
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数
int QueueSize(Queue* q);
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q);
// 销毁队列
void QueueDestroy(Queue* q);
2.1.2 Queue.c
#include "Queue.h"
// 初始化队列
void QueueInit(Queue* q)
{
assert(q);
q->_front = q->_rear = NULL;
q->size = 0;
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
assert(q);
QNode* tmp = (QNode*)malloc(sizeof(QNode));
if (tmp == NULL)
{
perror("QueueNode()::malloc()");
return;
}
tmp->_next = NULL;
tmp->_data = data;
if (q->size == 0)
{
q->_front = q->_rear = tmp;
}
else
{
q->_rear->_next = tmp;
q->_rear = tmp;
}
q->size++;
}
// 队头出队列
void QueuePop(Queue* q)
{
assert(q);
if (q->size == 0)
{
printf("队列已空\n");
return;
}
QNode* del = q->_front;
q->_front = q->_front->_next;
if (q->_front == NULL)
{
q->_rear = NULL;
}
free(del);
del = NULL;
q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
assert(q);
assert(q->_front);
return q->_front->_data;
}
// 获取队列队尾元素
QDataType QueueBack(Queue* q)
{
assert(q);
assert(q->_rear);
return q->_rear->_data;
}
// 获取队列中有效元素个数
int QueueSize(Queue* q)
{
return q->size;
}
// 检测队列是否为空,如果为空返回非零结果,如果非空返回0
int QueueEmpty(Queue* q)
{
if (q->size == 0)
return 1;
else
return 0;
}
// 销毁队列
void QueueDestroy(Queue* q)
{
while (q->_front)
{
QNode* del = q->_front;
q->_front = q->_front->_next;
free(del);
}
q->_rear = NULL;
q->size = 0;
}
2.2 顺序循环队列(rear初始化为0,指向待插入元素的位置)
2.2.1 Queue.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define MaxQueueSize 6
typedef char DataType;
typedef struct
{
DataType queue[MaxQueueSize];
int front;
int rear;
int count;
}SeqCQueue,*pSeqCQueue;
void QueueInitiate(pSeqCQueue pmyQueue);//初始化队列
int QueueNotEmpty(SeqCQueue myQueue);//队列非空返回1,否则返回0
int QueueAppend(pSeqCQueue pmyQueue,DataType x);//入列,成功返回1,否则返回0
int QueueDelete(pSeqCQueue pmyQueue, DataType* x);//出列,成功返回1,否则返回0
int QueueGet(SeqCQueue myQueue, DataType* y);//取队头元素,成功返回1,否则返回0
2.2.2 Queue.c
#include "Queue.h"
void QueueInitiate(pSeqCQueue pmyQueue)//初始化队列
{
pmyQueue->front = 0;
pmyQueue->rear = 0;
pmyQueue->count = 0;
}
int QueueNotEmpty(SeqCQueue myQueue)//队列非空返回1,否则返回0
{
if (myQueue.count == 0)
return 0;
else
return 1;
}
int QueueAppend(pSeqCQueue pmyQueue,DataType x)//入列,成功返回1,否则返回0
{
if (pmyQueue->count == MaxQueueSize)
{
printf("队列已满!\n");
return 0;
}
else
{
pmyQueue->queue[pmyQueue->rear] = x;
pmyQueue->rear = (pmyQueue->rear + 1) % MaxQueueSize;
pmyQueue->count++;
return 1;
}
}
int QueueDelete(pSeqCQueue pmyQueue, DataType* x)//出列,成功返回1,否则返回0
{
if (!QueueNotEmpty(*pmyQueue))
{
printf("队列已空!\n");
return 0;
}
else
{
*x = pmyQueue->queue[pmyQueue->front];
pmyQueue->front = (pmyQueue->front + 1) % MaxQueueSize;
pmyQueue->count--;
return 1;
}
}
int QueueGet(SeqCQueue myQueue, DataType* y)//取队头元素,成功返回1,否则返回0
{
if (!QueueNotEmpty(myQueue))
{
printf("队列已空!\n");
return 0;
}
else
{
*y = myQueue.queue[myQueue.front];
return 1;
}
}
Tips:
1、栈(一般实现顺序栈)
1.1 n个元素 依次进栈出栈的情况有多少种?
1.2 无论多简单都要写成一个函数,规范,不容易出错,如:stack.arr[top],不一定是栈顶元素,因为不知道top是哪种指向
1.3 在实现括号匹配时,注意 栈是后进先出 且可以边进边出,然后注意多种情况
2、队列(一般实现链式队列)
2.1 在实现循环队列时,注意 怎么循环(%),返回队尾元素小心越界