栈和队列的基本操作

待我称王封你为后i 2023-10-17 16:26 82阅读 0赞

对栈实现初始化，插入栈顶元素，删除栈顶元素，遍历栈，清空栈等基本操作

1 #include <stdio.h>
 2 #include <malloc.h>
 3 #include <stdlib.h>
 4 
 5 #define true 1
 6 #define false 0
 7 
 8 
 9 typedef struct Node
 10 {
 
 11 int data;
 12 struct Node *pNext;
 13 }NODE, *PNODE;
 14 
 15 typedef struct Stack
 16 {
 
 17 PNODE pTop;
 18 PNODE pBottom;
 19 }STACK, *PSTACK;
 20 
 21 void init(PSTACK pS);
 22 void push(PSTACK pS, int val);
 23 void traverse(PSTACK pS);
 24 int pop(PSTACK pS , int *val);
 25 void clear(PSTACK pS);
 26 int empty(PSTACK pS);
 27 
 28 int main(void)
 29 {
 
 30 STACK S ;
 31 int val;
 32 int i;
 33 
 34 init(&S);
 35 
 36 push(&S,1);
 37 push(&S,2);
 38 push(&S,3);
 39 push(&S,4);
 40 push(&S,5);
 41 push(&S,6);
 42 
 43 traverse(&S);
 44 
 45 if(pop(&S ,&val))
 46 {
 
 47 printf("遍历成功，出栈元素为%d\n",val);
 48 }
 49 else
 50 {
 
 51 printf("出栈失败！\n");
 52 }
 53 traverse(&S);
 54 
 55 clear(&S);
 56 
 57 traverse(&S);
 58 
 59 return 0 ;
 60 }
 61 
 62 //栈的初始化
 63 void init(PSTACK pS)
 64 {
 
 65 pS -> pTop = (PNODE)malloc(sizeof(NODE));
 66 
 67 if(NULL == pS -> pTop)
 68 {
 
 69 printf("动态内存分配失败！");
 70 exit(-1);
 71 }
 72 else
 73 {
 
 74 pS -> pBottom = pS -> pTop;
 75 pS -> pTop -> pNext = NULL;
 76 }
 77 
 78 return ;
 79 }
 80 
 81 //插入元素到栈顶
 82 void push(PSTACK pS , int val)
 83 {
 
 84 PNODE pNew = (PNODE)malloc(sizeof(NODE));
 85 
 86 pNew -> data = val;
 87 pNew -> pNext = pS -> pTop;
 88 pS -> pTop = pNew;
 89 
 90 return ;
 91 }
 92 
 93 //遍历栈S
 94 void traverse(PSTACK pS)
 95 {
 
 96 PNODE p = pS -> pTop;
 97 
 98 printf("栈内元素为：");
 99 while(p != pS -> pBottom)
 100 {
 
 101 printf("%d\t", p -> data);
 102 p = p -> pNext;
 103 }
 104 
 105 printf("\n");
 106 return ;
 107 }
 108 
 109 //判断栈是否为空
 110 int empty(PSTACK pS)
 111 {
 
 112 if(pS -> pTop == pS -> pBottom)
 113 {
 
 114 return true;
 115 }
 116 else
 117 return false;
 118 }
 119 
 120 //删除栈顶元素并将其值赋给*val
 121 int pop(PSTACK pS , int *val)
 122 {
 
 123 if(empty(pS))
 124 {
 
 125 return false;
 126 }
 127 else
 128 {
 
 129 PNODE r = pS -> pTop;
 130 *val = r -> data;
 131 pS -> pTop = r -> pNext;
 132 free(r);
 133 r = NULL;
 134 }
 135 }
 136 
 137 //清空栈S
 138 void clear(PSTACK pS)
 139 {
 
 140 if(empty(pS))
 141 {
 
 142 return;
 143 }
 144 else
 145 {
 
 146 PNODE p = pS -> pTop;
 147 PNODE q = NULL;
 148 
 149 while(p != pS -> pBottom)
 150 {
 
 151 q = p -> pNext;
 152 free(p);
 153 p = q ;
 154 }
 155 
 156 pS -> pTop = pS -> pBottom;
 157 
 158 return;
 159 }
 160 } 1.链式队列 //队列结点结构体 typedef struct QNode { QElemType data;   QNode *next; }*Queueptr; ------------------------------ //指向结点的指针 struct LinkQueue {  Queueptr front,rear; } 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 void InitQueue(LinkQueue &Q) 
 { // 构造一个空队列Q 
 if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)))) 
 exit(OVERFLOW); 
 Q.front->next=NULL; 
 } 
 
 void DestroyQueue(LinkQueue &Q) 
 { // 销毁队列Q(无论空否均可) 
 while(Q.front) 
 { 
 Q.rear=Q.front->next; 
 free(Q.front); 
 Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空 
 } 
 } 
 
 void ClearQueue(LinkQueue &Q) 
 { // 将Q清为空队列 
 QueuePtr p,q; 
 Q.rear=Q.front; 
 p=Q.front->next; 
 Q.front->next=NULL;//只留下头结点 
 while(p) 
 { 
 q=p; 
 p=p->next; 
 free(q); 
 } 
 } 
 
 Status QueueEmpty(LinkQueue Q) 
 { // 若Q为空队列，则返回TRUE，否则返回FALSE 
 if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆 
 return TRUE; 
 else 
 return FALSE; 
 } 
 
 int QueueLength(LinkQueue Q) 
 { // 求队列的长度 
 int i=0; 
 QueuePtr p; 
 p=Q.front; 
 while(Q.rear!=p) 
 { 
 i++; 
 p=p->next; 
 } 
 return i; 
 } 
 
 Status GetHead(LinkQueue Q,QElemType &e) 
 { // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR 
 QueuePtr p; 
 if(Q.front==Q.rear) 
 return ERROR; 
 p=Q.front->next; 
 e=p->data; 
 return OK; 
 } 
 
 void EnQueue(LinkQueue &Q,QElemType e) 
 { // 插入元素e为Q的新的队尾元素 
 QueuePtr p; 
 if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败 
 exit(OVERFLOW); 
 p->data=e; 
 p->next=NULL; 
 Q.rear->next=p; 
 Q.rear=p; 
 } 
 
 Status DeQueue(LinkQueue &Q,QElemType &e) 
 { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR 
 QueuePtr p; 
 if(Q.front==Q.rear) 
 return ERROR; 
 p=Q.front->next; 
 e=p->data; 
 Q.front->next=p->next; 
 if(Q.rear==p) 
 Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值 
 free(p); 
 return OK; 
 } 
 
 void QueueTraverse(LinkQueue Q,void(*vi)(QElemType)) 
 { // 从队头到队尾依次对队列Q中每个元素调用函数vi() 
 QueuePtr p; 
 p=Q.front->next; 
 while(p) 
 { 
 vi(p->data); 
 p=p->next; 
 } 
 printf("\n"); 
 }   
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 <span style="font-size:18px;color:#000066;">void InitQueue(LinkQueue &Q)   
 { // 构造一个空队列Q   
   if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))   
     exit(OVERFLOW);   
   Q.front->next=NULL;   
 }   
    
 void DestroyQueue(LinkQueue &Q)   
 { // 销毁队列Q(无论空否均可)   
   while(Q.front)   
   {   
     Q.rear=Q.front->next;   
     free(Q.front);   
     Q.front=Q.rear;//释放一块内存要做两点：1.释放指向它的指针。2.将该指针指向空   
   }   
 }   
    
 void ClearQueue(LinkQueue &Q)   
 { // 将Q清为空队列   
   QueuePtr p,q;   
   Q.rear=Q.front;   
   p=Q.front->next;   
   Q.front->next=NULL;//只留下头结点   
   while(p)   
   {   
     q=p;   
     p=p->next;   
     free(q);   
   }   
 }   
    
 Status QueueEmpty(LinkQueue Q)   
 { // 若Q为空队列，则返回TRUE，否则返回FALSE   
   if(Q.front->next==NULL)//注意不要把链式队列的判空条件与循环队列混淆   
     return TRUE;   
   else   
     return FALSE;   
 }   
    
 int QueueLength(LinkQueue Q)   
 { // 求队列的长度   
   int i=0;   
   QueuePtr p;   
   p=Q.front;   
   while(Q.rear!=p)   
   {   
     i++;   
     p=p->next;   
   }   
   return i;   
 }   
    
 Status GetHead(LinkQueue Q,QElemType &e)   
 { // 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR   
   QueuePtr p;   
   if(Q.front==Q.rear)   
     return ERROR;   
   p=Q.front->next;   
   e=p->data;   
   return OK;   
 }   
    
 void EnQueue(LinkQueue &Q,QElemType e)   
 { // 插入元素e为Q的新的队尾元素   
   QueuePtr p;   
   if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败   
     exit(OVERFLOW);   
   p->data=e;   
   p->next=NULL;   
   Q.rear->next=p;   
   Q.rear=p;   
 }   
    
 Status DeQueue(LinkQueue &Q,QElemType &e)   
 { // 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR   
   QueuePtr p;   
   if(Q.front==Q.rear)   
     return ERROR;   
   p=Q.front->next;   
   e=p->data;   
   Q.front->next=p->next;   
   if(Q.rear==p)   
     Q.rear=Q.front;//如果只有一个节点，那么删除这个节点后rear指针也就丢了，需重新赋值   
   free(p);   
   return OK;   
 }   
    
 void QueueTraverse(LinkQueue Q,void(*vi)(QElemType))   
 { // 从队头到队尾依次对队列Q中每个元素调用函数vi()   
   QueuePtr p;   
   p=Q.front->next;   
   while(p)   
   {   
     vi(p->data);   
     p=p->next;   
   }   
   printf("\n");   
 }   
 
 
 
 
 2.顺序队列---循环队列 结构体定义如下: struct SqQueue {QElemType *base;//指向开辟的空间的首地址   int front;   int rear; } 
 
 
 
 
 
 
 
 
 
 
 
 [cpp] 
 
 
 view plain
 
 
 copy
 
 
 print
 
 
 ?
 
 
 
 
 
 
 
 
 
 
 
 
 void InitQueue(SqQueue &Q) 
 { // 构造一个空队列Q 
 Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType)); 
 if(!Q.base) // 存储分配失败 
 exit(OVERFLOW); 
 Q.front=Q.rear=0; 
 } 
 
 void DestroyQueue(SqQueue &Q) 
 { // 销毁队列Q，Q不再存在 
 if(Q.base) 
 free(Q.base); 
 Q.base=NULL; 
 Q.front=Q.rear=0; 
 } 
 
 void ClearQueue(SqQueue &Q) 
 { // 将Q清为空队列 
 Q.front=Q.rear=0; 
 } 
 
 Status QueueEmpty(SqQueue Q) 
 { // 若队列Q为空队列，则返回TRUE；否则返回FALSE 
 if(Q.front==Q.rear) // 队列空的标志 
 return TRUE; 
 else 
 return FALSE; 
 } 
 
 int QueueLength(SqQueue Q) 
 { // 返回Q的元素个数，即队列的长度 
 return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE; 
 } 
 
 Status GetHead(SqQueue Q,QElemType &e) 
 { // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR 
 if(Q.front==Q.rear) // 队列空 
 return ERROR; 
 e=Q.base[Q.front];//等价于e=*(Q.base+Q.front) 
 return OK; 
 } 
 
 Status EnQueue(SqQueue &Q,QElemType e) 
 { // 插入元素e为Q的新的队尾元素 
 if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满 
 return ERROR; 
 Q.base[Q.rear]=e;//等价于*(Q.base+Q.rear)=e 
 Q.rear=(Q.rear+1)%MAX_QSIZE; 
 return OK; 
 } 
 
 Status DeQueue(SqQueue &Q,QElemType &e) 
 { // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR 
 if(Q.front==Q.rear) // 队列空 
 return ERROR; 
 e=Q.base[Q.front]; 
 Q.front=(Q.front+1)%MAX_QSIZE; 
 return OK; 
 } 
 
 void QueueTraverse(SqQueue Q,void(*vi)(QElemType)) 
 { // 从队头到队尾依次对队列Q中每个元素调用函数vi() 
 int i; 
 i=Q.front; 
 while(i!=Q.rear) 
 { 
 vi(Q.base[i]); 
 i=(i+1)%MAX_QSIZE; 
 } 
 printf("\n"); 
 }