栈与队列-C语言
- C语言
- 2024-04-20
- 3611热度
- 0评论
栈与队列-C语言
初始化栈-入栈-出栈
通过代码依次实现初始化栈，判断栈是否为空，压栈，获取栈顶元素，弹栈。此处规定S.top=-1时，栈为空。
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 50
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
//初始化栈
void InitStack(SqStack &S){
S.top=-1; //代表栈为空
}
//判断栈是否为空
bool StackEmpty(SqStack S){
if(S.top==-1)
{
return true;
} else
{
return false;
}
}
//入栈
bool Push(SqStack &S, ElemType x){
if(S.top==MaxSize-1)
{
return false;
}
S.data[++S.top]=x; //先存入数据，栈顶指针再加
return true;
}
//出栈
bool Pop(SqStack &S, ElemType &x){
if(-1==S.top) //栈为空无法出栈，这样的写法是为了避免书写错误，将常量放在前面如果只写一个等号代码会报错
{
return false;
}
x=S.data[S.top--]; //先弹出，栈顶指针再减
return true;
}
//读取栈顶元素
bool GetTop(SqStack &S, ElemType &x){
if(-1==S.top)
{
return false;
}
x=S.data[S.top];
return true;
}
int main(){
SqStack S;
InitStack(S);
bool ret;
ret= StackEmpty(S);
if(ret)
{
printf("Stack is Empty");
}
Push(S,3);
Push(S,4);
Push(S,5);
ElemType T; //接收输出的元素或弹出的元素
ret= GetTop(S,T);
if(ret)
{
printf("Stack Top Elem is %d\n",T);
}
ret= Pop(S,T);
if(ret)
{
printf("Pop Elem is %d\n",T);
}
return 0;
}循环队列
初始化循环队列，判断循环队列是否为空，入队，出队。注意代码执行结束可以通过调试来观察循环队列内的元素。
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 5
typedef int ElemType;
typedef struct {
ElemType data[MaxSize]; // 数组，存储MaxSize-1个元素
int front, rear; // 队列头、队列尾
} SqQueue;
// 初始化队列
void InitQueue(SqQueue &Q) {
Q.rear = Q.front = 0;
}
// 判断队列是否为空
bool IsEmpty(SqQueue Q) {
return Q.rear == Q.front;
}
// 入队
bool EnQueue(SqQueue &Q, ElemType x) {
if ((Q.rear + 1) % MaxSize == Q.front) {
return false;
}
Q.data[Q.rear] = x;
Q.rear = (Q.rear + 1) % MaxSize;
return true;
}
// 出队
bool DeQueue(SqQueue &Q, ElemType &x) {
if (Q.rear == Q.front) {
return false;
}
x = Q.data[Q.front];
Q.front = (Q.front + 1) % MaxSize;
return true;
}
// 遍历队列内的元素并输出
void ListQueue(SqQueue Q) {
int i = Q.front;
while (i != Q.rear) {
printf("%d\n", Q.data[i]);
i = (i + 1) % MaxSize;
}
}
int main() {
SqQueue Q;
InitQueue(Q);
bool ret; // 存储返回值
ret = IsEmpty(Q);
if (ret) {
printf("SqQueue is empty\n");
} else {
printf("SqQueue is not empty\n");
}
EnQueue(Q, 3);
EnQueue(Q, 4);
EnQueue(Q, 5);
EnQueue(Q, 6);
ret = EnQueue(Q, 7);
if (ret) {
printf("EnQueue Success\n");
} else {
printf("EnQueue Fail\n");
}
ElemType E; // 存储出队元素
ret = DeQueue(Q, E);
if (ret) {
printf("DeQueue Elem is %d\n", E);
} else {
printf("DeQueue Fial\n");
}
EnQueue(Q, 8);
if (ret) {
printf("EnQueue Success\n");
} else {
printf("EnQueue Fail\n");
}
printf("Elements in Queue:\n");
ListQueue(Q);
return 0;
}
通过断点调试，可以观察到当前front和rear指向的位置和当前出队的元素，如下图所示
队列(链表实现)
实现的步骤依次为初始化队列、入队、出队、和展示队列元素。代码执行结束可以通过调试来观察队列内元素。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LinkNode{
ElemType data;
struct LinkNode *next;
}LinkNode;
typedef struct {
LinkNode *front,*rear; //链表头、链表尾
}LinkQueue; //先进先出
//初始化队列
void InitQueue(LinkQueue &Q){
Q.front=Q.rear=(LinkNode *) malloc(sizeof(LinkNode)); //头指针和尾指针指向头结点
Q.front->next=NULL; //头指针的next指针指向空
}
//队列判空
bool IsEmpty(LinkQueue Q){
if(Q.front==Q.rear)
{
return true;
} else
{
return false;
}
}
//入队，尾插法
void EnQueue(LinkQueue &Q, ElemType x){
LinkNode *s=(LinkNode *) malloc(sizeof(LinkNode));
s->data=x;
s->next=NULL;
Q.rear->next=s; //rear指针的next指针始终指向尾部
Q.rear=s; //rear指针指向结点的最后一个元素
}
//出队，头删法
bool DeQueue(LinkQueue &Q,ElemType &x){
if(Q.front==Q.rear)
{
return false;
}
LinkNode *p=Q.front->next; //头结点无数据，front指针next指针指向的节点才有数据，并赋值给指针p
x=p->data; //将准备删除的元素的数据取出，赋值给x
Q.front->next=p->next; //断链
if(Q.rear==p) //删除的元素为队列的最后一个元素
{
Q.rear=Q.front; //将队列置为空
}
free(p); //释放节点
return true; //由于是bool类型的子函数，所以要返回值，否则编译器会出现警告
}
// 展示当前队列元素
void ListElem(LinkQueue Q) {
LinkNode *p = Q.front->next; // 从队列的第一个元素开始遍历
while (p != NULL) {
printf("%3d", p->data);
p = p->next;
}
}
int main(){
LinkQueue Q;
InitQueue(Q);
bool ret; //存储判断条件
ret=IsEmpty(Q);
if(ret)
{
printf("Queue is empty\n");
} else
{
printf("Queue is not empty\n");
}
EnQueue(Q,3);
EnQueue(Q,4);
EnQueue(Q,5);
EnQueue(Q,6);
EnQueue(Q,7);
ElemType element; //存储出队元素
ret= DeQueue(Q,element);
if(ret)
{
printf("DeQueue elem is %d\n",element);
} else
{
printf("DeQueue fail\n");
}
ListElem(Q);
return 0;
}下面附带两道题目，供读者自行练习
一、设计一个队列，要求满足：
①初始时队列为空。
②入队时，允许增加队列占用空间。
③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减。
④入队操作和出队操作的时间复杂度始终保持为O(1)。
(1)该队列应选择链式存储结构还是顺序存储结构？
(2)给出判断队空和队满的条件？
(3)画出第一个元素入队后的队列状态？
(4)给出入队操作和出队操作的基本过程？
答：
（1）选择链式存储结构（两段式单向循环链表）是更好的选择。因为链表的结点可以动态地分配和释放，使得队列的大小可以灵活地扩展和收缩，而且入队和出队操作的时间复杂度为 O(1)。
（2）初始时，创建一个只有一个空闲结点的两段式单向循环链表，头指针front和尾指针rear均指向空闲节点。队空的判断条件为front==rear。队满的判断条件为front=rear->next。
（3）如下图所示
（4）入队操作：若front==rear->next，队满，则在rear后面插入一个新的空闲结点，入队元素保存到rear所指的结点中，rear=rear->next，随后返回。出队操作：若front==rear，队空，出队失败，返回失败。若队列不为空。取front所指结点中的元素e，front=front->next，随后返回e。
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
//入队
void EnQueue(LinkList front, LinkList &rear, ElemType val){
LinkList p;
if(rear->next==front)
{
//队满，申请一个结点的空间，放入队列
p=(LinkList) malloc(sizeof(LNode));
rear->data=val; //把入队元素放入rear指向的结点
rear->next=p; //新申请的结点作为队列的最后一个结点
p->next=front;
rear=p;
} else
{
rear->data=val;
rear=rear->next;
}
}
//出队
void DeQueue(LinkList &front, LinkList &rear){
if(front==rear)
{
printf("Queue is empty\n");
}else
{
printf("DeQueue elem is %d\n",front->data);
front=front->next;
}
}
void CircleQueue(LinkList &front, LinkList &rear){
//队列头和队列尾都指向一个结点，这时队列即是空的，也是满的
front=(LinkList) malloc(sizeof(LNode));
rear=front;
rear->next=front;
//入队
EnQueue(front,rear,3);
EnQueue(front,rear,4);
//出队
DeQueue(front,rear);
DeQueue(front,rear);
DeQueue(front,rear);
}
int main(){
LinkList front,rear;
CircleQueue(front,rear);
return 0;
}提示：在入队操作时，else分支语句会被执行吗？
二、新建一个栈，读取标准输入3个整数3 4 5，入栈3 4 5，依次出栈，打印 5 4 3，新建循环队列（Maxsize为5），读取标准输入3 4 5 6 7，入队7时，队满，打印false，然后依次出队，输出 3 4 5 6。
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 5
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int top;
}SqStack;
void InitStack(SqStack &S){
S.top=-1;
}
bool Push(SqStack &S, ElemType x){
if(S.top==MaxSize-1)
{
return false;
}
S.data[++S.top]=x;
return true;
}
bool Pop(SqStack &S, ElemType &x){
if(-1==S.top)
{
return false;
}
x=S.data[S.top--];
return true;
}
typedef struct {
ElemType data[MaxSize];
ElemType front,rear;
}SqQueue;
void InitQueue(SqQueue &Q){
Q.rear=Q.front=0;
}
bool EnQueue(SqQueue &Q, ElemType x){
if((Q.rear+1)%MaxSize==Q.front)
{
return false;
}
Q.data[Q.rear]=x;
Q.rear=(Q.rear+1)%MaxSize;
return true;
}
bool DeQueue(SqQueue &Q, ElemType &x){
if(Q.rear==Q.front)
{
return false;
}
x=Q.data[Q.front];
Q.front=(Q.front+1)%MaxSize;
return true;
}
int main(){
SqStack S;
bool flag;
ElemType m;
InitStack(S);
int i,num;
for(i=0;i<3;i++)
{
scanf("%d",&num);
Push(S,num);
}
for(i=0;i<3;i++)
{
Pop(S,m);
printf("%2d",m);
}
printf("\n");
SqQueue Q;
InitQueue(Q);
for(i=0;i<5;i++)
{
scanf("%d",&num);
flag= EnQueue(Q,num);
if(false==flag)
{
printf("elem %d enqueue is fail\n",num);
}
}
ElemType elem;
for(i=0;i<4;i++)
{
DeQueue(Q,elem);
printf("%2d",elem);
}
printf("\n");
return 0;
}