devbox
空白诗007
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构：栈和队列_数据结构栈和队列

作者：空白诗007 | 2024-08-13 16:48:42

赞

踩

数据结构栈和队列

五.栈与队列

栈定义：用来存储函数调用时各个函数的参数，返回地址及临时变量等。
特点：先进后出，不考虑排序。
队列特点：先进先出。
题目：用两个栈实现一个队列，队列申明如下，实现它的两个函数appendTail和deleteHead，即：队列的尾部插入节点，头部删除节点。

思路：自定义一个函数模板CQueue，它有public属性或方法：构造函数，析构函数，在尾部添加节点void appendTail（const T& node），删除队列的头节点T deleteHead().私有属性：stack<T> stack1;stack<T>stack2;由于定义CQueue,为模板的原因，在尾部添加节点实现函数为:template< typename T> void cQueue<T>::appendTail(const T& node){stack1.push(node)},删除队列头部的节点template<T> T cQueue<T> ::deleteHead（）如果stack2<=0，当stack1.size()满足大于0时，将stack1,中的所有元素压入stack2.如果stack2==0,抛空。定义一个T类型的head并且赋初值为stack2.top，stack2.pop(),返回Head。

  1. #include <iostream>  
  2. #include <stack>  
  3. #include <exception>  
  4. using namespace std;  
  5.   
  6. template <typename T> class CQueue  
  7. {  
  8. public:  
  9.     CQueue(void);  
  10.     ~CQueue(void);  
  11.   
  12.     // 在队列末尾添加一个结点  
  13.     void appendTail(const T& node);  
  14.   
  15.     // 删除队列的头结点  
  16.     T deleteHead();  
  17.   
  18. private:  
  19.     stack<T> stack1;  
  20.     stack<T> stack2;  
  21. };  
  22.   
  23. //成员函数定义.  
  24. template <typename T>   
  25. CQueue<T>::CQueue(void)  
  26. {  
  27. }  
  28.   
  29. template <typename T>   
  30. CQueue<T>::~CQueue(void)  
  31. {  
  32. }  
  33.   
  34. //向队列中插入元素.  
  35. template <typename T>   
  36. void CQueue<T>::appendTail(const T& node)  
  37. {  
  38.     stack1.push(node);  
  39. }  
  40.   
  41. //从队列中删除元素.  
  42. template <typename T>   
  43. T CQueue<T>::deleteHead()  
  44. {  
  45.     //先判断stack2是否为空.  
  46.     //若其不为空，则从中弹出元素；  
  47.     //若为空，则将stack1中元素依次弹出并存入stack2中.  
  48.     if(stack2.size() <= 0)  
  49.         while (stack1.size() > 0)  
  50.         {//当stack2为空时，将stack1中所有元素存入stack2中.  
  51.             T data = stack1.top();  
  52.             stack1.pop();  
  53.             stack2.push(data);  
  54.         }  
  55.         if(stack2.size() == 0)  
  56.             throw new exception("queue is empty!");  
  57.   
  58.         T head = stack2.top();  
  59.         stack2.pop();  
  60.   
  61.         return head;  
  62. }  
  63.   
  64. //测试函数.  
  65. void Test(char actual, char expected)  
  66. {  
  67.     if(actual == expected)  
  68.         cout << "Test passed." << endl;  
  69.     else  
  70.         cout << "Test failed.\n" << endl;  
  71. }  
  72.   
  73. int main()  
  74. {  
  75.     CQueue<char> queue;  
  76.   
  77.     queue.appendTail(‘a‘);  
  78.     queue.appendTail(‘b‘);  
  79.     queue.appendTail(‘c‘);  
  80.   
  81.     char head = queue.deleteHead();  
  82.     Test(head, ‘a‘);  
  83.   
  84.     head = queue.deleteHead();  
  85.     Test(head, ‘b‘);  
  86.   
  87.     queue.appendTail(‘d‘);  
  88.     head = queue.deleteHead();  
  89.     Test(head, ‘c‘);  
  90.   
  91.     queue.appendTail(‘e‘);  
  92.     head = queue.deleteHead();  
  93.     Test(head, ‘d‘);  
  94.   
  95.     head = queue.deleteHead();  
  96.     Test(head, ‘e‘);  
  97.   
  98.     return 0;  
  99. }


总结：

栈：

  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <stack>
  5. using namespace std;
  6. int main()
  7. {
  8.     stack<int> st;
  9.     /*
  10.         对栈的操作无非就是：验证是否为空、返回栈中元素数目、对栈顶元素删除、获取以及压入新元素
  11.         st.empty();    验证是否为空
  12.         st.size();    栈中元素个数
  13.         st.pop();        删除栈顶元素，无返回值
  14.         st.push();    将新元素压入栈中
  15.         st.top();        返回栈顶元素
  17.         st.size()为st对象调用stack类size函数
  18.         st->size()针对于指针对象指向size函数
  19.     */
  20.     if(st.empty()){
  21.         cout<<"stack is empty"<<endl;        
  22.         cout<<"刚进行初始化stack的大小:  "<<st.size()<<endl;                //输出size
  23.         st.push(111);
  24.         st.push(222);                        //压入栈顶,必须是同类型的int值
  25.         cout<<"push后的stack大小:  "<<st.size()<<endl;
  26.         cout<<"取出stack顶元素:  "<<st.top()<<endl<<endl;
  27.         //取出stack中所有元素
  28.         while(st.size()>0){
  29.             cout<<st.top()<<endl;
  30.             st.pop();
  31.             //因声明的是stack静态对象st，不用考虑内存泄漏
  32.         }
  33.         cout<<"stack size : "<<st.size()<<endl;
  34.     }
  35.     getchar();　　　　　　　　　　//程序暂停等待用户输入任意字符,让命令行窗口不会一闪而过
  36.     return 0;
  37. }

队列：

  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <iostream>
  4. #include <queue>
  5. using namespace std;
  6. int main(){
  7.     queue<int> p;
  8.     /*
  9.     q.empty()               如果队列为空
  10.     q.size()                返回队列中元素的个数  
  11.     q.pop()                 删除队列首元素无返回值
  12.     q.front()               返回队首元素的值，但不删除该元素  
  13.     q.push()                在队尾压入新元素  
  14.     q.back()                返回队列尾元素的值，但不删除该元素  
  15.     */
  16.     if(p.empty()){
  17.         cout<<"pop is empty"<<endl;        
  18.         cout<<"刚进行初始化pop的大小:  "<<p.size()<<endl;                //输出size
  19.         p.push(111);
  20.         p.push(222);                        //压入栈顶,必须是同类型的int值
  21.         cout<<"push后的pop大小:  "<<p.size()<<endl;
  22.         cout<<"取出pop顶元素:  "<<p.front()<<endl<<endl;
  23.         //取出pop中所有元素
  24.         while(p.size()>0){
  25.             cout<<p.front()<<endl;
  26.             p.pop();
  27.             //因声明的是pop静态对象p，不用考虑内存泄漏
  28.         }
  29.         cout<<"pop size : "<<p.size()<<endl;
  30.     }
  31.     getchar();
  32.     return 0;
  33. }

栈的数组实现  (利用栈的基本操作来实现对数组的操作)　　栈：后进先出　　数组：按 (索引->值) 依次存储

  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #define maxsize 10
  5. typedef struct        //定义结构体，并且在
  6. {
  7.     int data[maxsize];    //数组大小
  8.     int top;            //栈顶坐标
  9.     int base;        //栈底坐标
  10. }seqstack;            //seqstack为结构体的别名而已，还可以使用多个别名,且多个别名创建的对象使用的不是同一个内存空间, 并根据数组的结构定义成员
  11. seqstack * s;            //栈
  12. void initstack(seqstack * s)
  13. {
  14.     s->top = 0;
  15.     s->base = 0;
  16. }
  17. int empty(seqstack * s)
  18. {
  19.     if(s->top == s->base)
  20.         return 1;
  21.     else
  22.         return 0;
  23. }
  24. //入栈：赋值 , 索引++
  25. void  push(seqstack * s, int x)
  26. {
  27.     if(s->top >= maxsize-1)
  28.     {
  29.         printf("ERROR!\n");
  30.     }
  31.     else
  32.     {
  33.         s->data[s->top] = x;
  34.         s->top++;
  35.     }
  36. }
  37. //获取栈顶元素data[s->top--]  这里需要top--是因为入栈时top索引++了
  38. void  pop(seqstack * s)
  39. {
  40.     if(empty(s))
  41.     {
  42.         printf("ERROR!\n");
  43.     }
  44.     else
  45.     {
  46.         s->top--;
  47.         printf("%d\n",s->data[s->top]);
  48.     }
  49. }
  50. int main()
  51. {
  52.     seqstack * s;
  53.     //（seqstack *）强转，malloc(size)申请大小为size动态内存空间，sizeof(seqstack)，seqstack类型占多少字节sizeof的值就是多大，如：sizeof(int) = 4
  54.     s = (seqstack *)malloc(sizeof(seqstack));
  55.     //此时s为空，s为指针对象，会以传址的方式将s传递给initstack函数
  56.     initstack(s);
  57.     push(s,1);
  58.     push(s,3);
  59.     pop(s);
  60.     push(s,2);
  61.     pop(s);
  62.     pop(s);
  63.     pop(s);
  64.     return 0;
  65. }

栈的链表实现        (利用栈的基本操作来实现对链表的操作)

  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #include <stdlib.h>
  5. typedef struct node
  6. {
  7.     int data;
  8.     struct node *next;
  9. }node,linkstack;                    //使用多个别名,在这里node为节点
  10. //初始化
  11. void InitStack(linkstack * top)        
  12. {
  13.     top->next = NULL;
  14. }
  15. //是否为空   只用想想链表的结构就很清楚了，节点与节点之间通过指针关联，只要top->next为NULL即可
  16. int IsEmpty(linkstack * top)
  17. {
  18.     if(top->next == NULL) return 1;
  19.     return 0;
  20. }
  21. //入栈：新建一个节点赋值，让新节点的next指针指向NUll,栈内top->next指向新节点即可
  22. int Push(linkstack * top, int x)
  23. {
  24.     node * p;    
  25.     p = (node *)malloc(sizeof(node));
  26.     if(p == NULL) return 0;
  27.     p->data = x;
  28.     p->next = top->next;            //top->next = null
  29.     top->next = p;
  30.     return 1;
  31. }
  32. //删除栈顶元素：
  33. int Pop(linkstack * top, int *x)
  34. {
  35.     node * p;
  36.     if(IsEmpty(top))
  37.     {
  38.         printf("ERROE!\n");
  39.         return 0;
  40.     }
  41.     p = top->next;
  42.     *x = p->data;
  43.     top->next = p->next;
  44.     free(p);
  45.     return 1;
  46. }
  47. int main()
  48. {
  49.     int x;
  50.     linkstack * s;
  51.     s = (linkstack *)malloc(sizeof(linkstack));
  52.     InitStack(s);
  53.     Push(s,1);
  54.     Push(s,3);
  55.     Pop(s,&x);
  56.     printf("%d\n",x);
  57.     Push(s,2);
  58.     Pop(s,&x);
  59.     printf("%d\n",x);
  60.     Pop(s,&x);
  61.     printf("%d\n",x);
  62.     Pop(s,&x);
  63.     return 0;
  64. }
  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #define maxsize 66　　　　//定义变量
  5. typedef struct　　　　　　//type define 结构定义
  6. {
  7.     int data[maxsize];
  8.     int front,rear;　　　//front来记录列首,rear来记录列尾
  9. }sequeue;
  10. sequeue *q;　　　　　　　　　　//循环链表
  11. void initqueue(sequeue *q)
  12. {
  13.     q->front = -1;　　　　　　//q指针指向sequeue对象中的front方法
  14.     q->rear = -1;
  15. }
  16. int del(sequeue *q)　　　　　
  17. {
  18.     if(q->front == q->rear)　　　　　　//列首列尾元素是否相等，若相等则是空的循环队列和数组
  19.         return NULL;
  20.     else
  21.     {
  22.         q->front++;　　　　　　　　　　//->优先级比++大，故先执行->然后++
  23.         return q->data[q->front];　　//实现对数组的删除操作,没调用此方法一次就让front记录的值+1　　
  24.     }
  25. }
  26. int insertqueue(sequeue *q,int x)　　　　//向队列中插入元素，思路：先判断列尾是否超出maxsize大小，然后让索引rear+1，对应的给数组data[rear+1]赋值,来实现插入
  27. {
  28.     if(q->rear >= maxsize-1)
  29.         return NULL;
  30.     else
  31.     {
  32.         (q->rear)++;　　　　　　　　　　　　//列尾+1
  33.         q->data[q->rear] = x;
  34.         return 1;
  35.     }
  36. }
  37. int empty(sequeue * q)　　　　　　　　　　//简单判断队列是否为空，也就是数组data是否为空
  38. {
  39.     if(q->front == q->rear)
  40.         return 0;
  41.     else
  42.         return 1;　　　　　　　　　　　　　//这里也可扩展，返回队列元素大小,前提是需要让rear递增
  43. }
  44. void print(sequeue * q)　　　　　　　　　　//遍历输出数据元素
  45. {
  46.     if(q->front == q->rear)
  47.         printf("ERROR!\n");
  48.     else
  49.     {
  50.         while(empty(q))
  51.         {
  52.             q->front++;
  53.             printf("%d\n",q->data[q->front]);
  54.         }
  55.     }
  56. }
  57. int main()
  58. {
  59.     int i;
  60.     sequeue *q;
  61.     q  = (sequeue *)malloc(sizeof(sequeue));
  62.     initqueue(q);
  63.     for(i = 0; i < 6; i++)
  64.         insertqueue(q,i);
  65.     printf("front is %d\n\n",del(q));
  66.     printf("Then the last data is:\n");
  67.     print(q);
  68.     return 0;
  69. }

队列的数组实现(利用数组的数据结构来对队列进行操作)　　　先想想数组的实现原理
原理：
front           ->            rear           (假设队列顺序从左往右)
data[front]  ->             data[rear] (如果对队列中front、rear操作，则相应的数据元素、大小也随之变化) 
  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #define maxsize 66　　　　//定义变量
  5. typedef struct　　　　　　//type define 结构定义
  6. {
  7.     int data[maxsize];
  8.     int front,rear;　　　//front来记录列首,rear来记录列尾
  9. }sequeue;
  10. sequeue *q;　　　　　　　　　　//循环链表
  11. void initqueue(sequeue *q)
  12. {
  13.     q->front = -1;　　　　　　//q指针指向sequeue对象中的front方法
  14.     q->rear = -1;
  15. }
  16. int del(sequeue *q)　　　　　
  17. {
  18.     if(q->front == q->rear)　　　　　　//列首列尾元素是否相等，若相等则是空的循环队列和数组
  19.         return NULL;
  20.     else
  21.     {
  22.         q->front++;　　　　　　　　　　//->优先级比++大，故先执行->然后++
  23.         return q->data[q->front];　　//实现对数组的删除操作,没调用此方法一次就让front记录的值+1　　
  24.     }
  25. }
  26. int insertqueue(sequeue *q,int x)　　　　//向队列中插入元素，思路：先判断列尾是否超出maxsize大小，然后让索引rear+1，对应的给数组data[rear+1]赋值,来实现插入
  27. {
  28.     if(q->rear >= maxsize-1)
  29.         return NULL;
  30.     else
  31.     {
  32.         (q->rear)++;　　　　　　　　　　　　//列尾+1
  33.         q->data[q->rear] = x;
  34.         return 1;
  35.     }
  36. }
  37. int empty(sequeue * q)　　　　　　　　　　//简单判断队列是否为空，也就是数组data是否为空
  38. {
  39.     if(q->front == q->rear)
  40.         return 0;
  41.     else
  42.         return 1;　　　　　　　　　　　　　//这里也可扩展，返回队列元素大小,前提是需要让rear递增
  43. }
  44. void print(sequeue * q)　　　　　　　　　　//遍历输出数据元素
  45. {
  46.     if(q->front == q->rear)
  47.         printf("ERROR!\n");
  48.     else
  49.     {
  50.         while(empty(q))
  51.         {
  52.             q->front++;
  53.             printf("%d\n",q->data[q->front]);
  54.         }
  55.     }
  56. }
  57. int main()
  58. {
  59.     int i;
  60.     sequeue *q;
  61.     q  = (sequeue *)malloc(sizeof(sequeue));
  62.     initqueue(q);
  63.     for(i = 0; i < 6; i++)
  64.         insertqueue(q,i);
  65.     printf("front is %d\n\n",del(q));
  66.     printf("Then the last data is:\n");
  67.     print(q);
  68.     return 0;
  69. }

队列的链表实现  (利用链表的数据结构来实现对队列的操作)　　先想想链表的实现原理，要知道链表中某个节点，那就必须要知道它上一个节点

节点： [值 | 指针] (指向下一个节点的内存地址)

front           ->            rear           (假设队列顺序从左往右)

  1. #include <stdafx.h>
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. typedef struct node　　　　　　　　//节点
  5. {
  6.     int data;　　　　　　　　　　　　//值
  7.     struct node * next;　　　　　　//指针
  8. }linklist;　　　　　　　　　　　　　//节点对象　　　　　　　　　　　　　
  9. typedef struct
  10. {
  11.     linklist * front, * rear;　　//定义结构对象的两个指针，front表示上一个节点，rear表示下一个节点
  12. }linkqueue;　　　　　　　　　　　　　　
  13. linkqueue * q;　　　　　　　　　　　//链表　　　　　　　　　
  14. //建立队列
  15. void initqueue(linkqueue * q)
  16. {
  17.     q->front = (linkqueue *)malloc(sizeof(linklist));　　//动态分配,初始化为0
  18.     q->front->next = NULL;　　　　　　　　　　　　　　　　　　//将首节点中指向下一节点的指针置空
  19.     q->rear = q->front;　　　　　　　　　　　　　　　　　　　　//队列首位
  20. }
  21. //判断队列空否
  22. int empty(linkqueue * q)
  23. {
  24.     if(q->front == q->rear)
  25.         return 1;
  26.     else
  27.         return 0;
  28. }
  29. //入队列     先定义一个与listlink相同的节点对象，然后再将它加入链表队列中(rear->next指向新建的节点)
  30. void inqueue(linkqueue * q, int x)
  31. {
  32.     q->rear->next = (linklist *)malloc(sizeof(linklist));　　　　//q->rear->next本来是NULL的，现在将对它赋予节点对象，也就连接了rear和rear->next
  33.     q->rear->next->data = x;　　　　　　　　　　　　　　　　　　　　
  34.     q->rear = q->rear->next;　　　　　　　　　　　　　　　　　　　　//让rear没有下一个节点
  35.     q->rear->next = NULL;　　　　　　　　　　　　　　　　　　　　　　　//确定操作的rear节点位于链尾
  36. }
  37. //出队列    从front节点开始一节一节的取,此方法每调用一个就取一个,一直取到最后一个时,就会一直返回q->rear
  38. int outqueue(linkqueue * q)
  39. {
  40.     linklist * s;
  41.     if(empty(q))
  42.         return NULL;
  43.     else
  44.     {
  45.         s = q->front->next;
  46.         printf("%d\n",s->data);
  47.         if(s == q->rear)
  48.             q->front = q->rear;
  49.         else
  50.             q->front->next = s->next;
  51.         free(s);
  52.         return 1;
  53.     }
  54. }
  55. //main
  56. int main()
  57. {
  58.     int i;
  59.     linkqueue * l;
  60.     l = (linkqueue *)malloc(sizeof(linkqueue));
  61.     initqueue(l);
  62.     for(i = 0; i < 10; i++)
  63.         inqueue(l,i);
  64.     for(i = 0; i < 10; i++)
  65.         outqueue(l);
  66.     
  67.     return 0;
  68. }


声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/空白诗007/article/detail/975697
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号