title: 【锐格】数据结构-栈和队列
tags:

  • 锐格
  • 数据结构
    abbrlink: 11bfbc93
    date: 2021-10-22 14:23:01

欢迎加入NEFU计算机编程交流群：523539085

顺序栈

4909

  1. #include<iostream>
  2. using namespace std;
  4. struct Node {
  5.     int data;
  6.     Node *next;
  7. };
  9. class SeqStack {
  10. private:
  11.     int *array;
  12.     int maxSize;
  13.     int top;
  14.     void stackFull();
  15. public:
  16.     SeqStack(int sz=0);
  17.     void Push(const int &x);
  18.     bool Pop(int &x);
  19.     bool getTop(int &x);
  20.     bool isEmpty() const
  21.     {
  22.         return (top==-1)?true:false;
  23.     }
  24.     bool isFull() const
  25.     {
  26.         return (top==maxSize-1)?true:false;
  27.     }
  28.     int getSize() const
  29.     {
  30.         return top+1;
  31.     }
  32. };
  34. SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
  35. {
  36.     array = new int[maxSize];
  37. }
  39. void SeqStack::Push(const int &x)
  40. {
  41.     if (this->isFull())
  42.         this->stackFull();
  43.     array[++top] = x;
  44. }
  46. bool SeqStack::Pop(int &x)
  47. {
  48.     if (this->isEmpty())
  49.         return false;
  50.     x = array[top--];
  51.     return true;
  52. }
  54. bool SeqStack::getTop(int &x)
  55. {
  56.     if (this->isEmpty())
  57.         return false;
  58.     x = array[top];
  59.     return true;
  60. }
  62. void SeqStack::stackFull()
  63. {
  64.     maxSize = maxSize*2;
  65.     int *temp = new int[maxSize];
  66.     int i;
  67.     for (i=0;i<=top;i++)
  68.         temp[i] = array[i];
  69.     delete []array;
  70.     array = temp;
  71. }
  73. class LinkList {
  74. private:
  75.     Node *first;
  76. public:
  77.     LinkList();
  78.     void Insert(const int &x);
  79.     int Length();
  80.     void Reverse();
  81.     void output();
  82. };
  84. LinkList::LinkList()
  85. {
  86.     first = new Node();
  87.     first->next = NULL;
  88. }
  90. void LinkList::Insert(const int &x)
  91. {
  92.     Node *t = first;
  93.     while (t->next!=NULL)
  94.         t = t->next;
  95.     Node *n = new Node();
  96.     n->data = x;
  97.     n->next = t->next;
  98.     t->next = n;
  99. }
  101. int LinkList::Length()
  102. {
  103.     int count=0;
  104.     Node *t = first;
  105.     while (t->next!=NULL) {
  106.         t = t->next;
  107.         count++;
  108.     }
  109.     return count;
  110. }
  112. void LinkList::Reverse()
  113. {
  114.     //write your code here
  115.     SeqStack S(Length());
  116.     Node *p=first->next;
  117.     int x;
  118.     //output();
  119.     first->next=NULL;
  120.     //output();
  121.     while(p!=NULL)
  122.     {
  123.         S.Push(p->data);
  124.         p=p->next;
  125.     }
  126.     //output();
  127.     while(!S.isEmpty())
  128.     {
  129.         S.Pop(x);
  130.         Insert(x);
  131.     }
  132. }
  134. void LinkList::output()
  135. {
  136.     Node *t = first;
  137.     while (t->next!=NULL) {
  138.         t=t->next;
  139.         cout << t->data << " ";
  140.     }
  141.     cout << endl;
  142. }
  144. int main()
  145. {
  146.     LinkList l;
  147.     int x;
  148.     cin >> x;
  149.     while (x!=-1) {
  150.         l.Insert(x);
  151.         cin >> x;
  152.     }
  153.     l.output();
  154.     l.Reverse();
  155.     l.output();
  156.     return 0;
  157. }

4908

从上一道题cv就行

  1. #include<iostream>
  2. using namespace std;
  4. class SeqStack {
  5. private:
  6.     int *array;
  7.     int maxSize;
  8.     int top;
  9.     void stackFull();
  10. public:
  11.     SeqStack(int sz=0);
  12.     void Push(const int &x);
  13.     bool Pop(int &x);
  14.     bool getTop(int &x);
  15.     bool isEmpty() const
  16.     {
  17.         return (top==-1)?true:false;
  18.     }
  19.     bool isFull() const
  20.     {
  21.         return (top==maxSize-1)?true:false;
  22.     }
  23.     int getSize() const
  24.     {
  25.         return top+1;
  26.     }
  27.     int getMaxSize() const
  28.     {
  29.         return maxSize;
  30.     }
  31.     void MakeEmpty()
  32.     {
  33.         top = -1;
  34.     }
  35. };
  37. SeqStack::SeqStack(int sz):top(-1),maxSize(sz)
  38. {
  39.     //write your code here
  40.     array=new int[maxSize];
  41. }
  43. void SeqStack::Push(const int &x)
  44. {
  45.     //write your code here
  46.     if(this->isFull())
  47.         this->stackFull();
  48.     array[++top]=x;
  49. }
  51. bool SeqStack::Pop(int &x)
  52. {
  53.     //write your code here
  54.     if(this->isEmpty())
  55.         return false;
  56.     x=array[top--];
  57.     return true;
  58. }
  60. bool SeqStack::getTop(int &x)
  61. {
  62.     //write your code here
  63.     if(this->isEmpty())
  64.         return false;
  65.     x=array[top];
  66.     return true;
  67. }
  69. void SeqStack::stackFull()
  70. {
  71.     //write your code here
  72.     maxSize*=2;
  73.     int *tmp=new int[maxSize];
  74.     for(int i=0;i<=top;i++)
  75.         tmp[i]=array[i];
  76.     delete []array;
  77.     array=tmp;
  78. }
  80. int main()
  81. {
  82.     int x;
  83.     SeqStack ss(4);
  84.     ss.Push(1);
  85.     ss.Push(2);
  86.     ss.Push(3);
  87.     ss.Push(4);
  88.     ss.Push(5);
  89.     ss.Pop(x);
  90.     cout << x << endl;
  91.     cout << ss.getSize() << endl;
  92.     cout << ss.getMaxSize() << endl;
  93.     return 0;
  94. }

4873待解决

4870

  1. #include<stdio.h>
  3. #define maxsize 10000
  5. typedef struct
  6. {
  7.     int data[maxsize];      //存放栈中元素
  8.     int top;                //栈顶指针
  9. }SqStack;
  11. //初始化栈
  12. void initStack(SqStack &st)
  13. {
  14.     st.top = -1;
  15. }
  17. //进栈算法
  18. int Push(SqStack &st, int x)
  19. {
  20.     if(st.top == maxsize - 1)
  21.         return 0;
  22.     ++(st.top);  //先移动指针再进栈
  23.     st.data[st.top] = x;
  24.     return 1;
  25. }
  27. //出栈算法
  28. int Pop(SqStack &st , int &x)
  29. {
  30.     if(st.top == -1)
  31.         return 0;
  32.     x = st.data[st.top];
  33.     --(st.top);
  34.     return 1;
  35. }
  37. void isEmpty(SqStack st)
  38. {
  39.  //write your own codes
  40.  if(st.top==-1)
  41.     printf("Stack is empty\n");
  42.  else
  43.     printf("Stack is not empty\n");
  44. }
  46. int main()
  47. {
  48.     int n , i , e;
  49.     SqStack S;
  50.     initStack(S);
  51.     isEmpty(S);              //需要写的函数
  52.     scanf("%d",&n);
  53.     for(i = 0 ; i < n; ++i)
  54.     {
  55.         scanf("%d",&e);
  56.         Push(S,e);
  57.     }
  58.     isEmpty(S);
  59.     scanf("%d",&n);
  60.     for(int i = 0 ;i < n ; ++i)
  61.         Pop(S,e);
  62.     isEmpty(S);
  63.     return 0;
  64. }

4869

cv大法好

  1. #include<stdio.h>
  3. #define maxsize 10000
  5. typedef struct
  6. {
  7.     int data[maxsize];      //存放栈中元素
  8.     int top;                //栈顶指针
  9. }SqStack;
  11. //初始化栈
  12. void initStack(SqStack &st)
  13. {
  14.     st.top = -1;
  15. }
  17. //进栈算法
  18. int Push(SqStack &st, int x)
  19. {
  20.     if(st.top == maxsize - 1)
  21.         return 0;
  22.     ++(st.top);  //先移动指针再进栈
  23.     st.data[st.top] = x;
  24.     return 1;
  25. }
  27. //出栈算法
  28. int Pop(SqStack &st , int &x)
  29. {
  30.     if(st.top == -1)
  31.         return 0;
  32.     x = st.data[st.top];
  33.     --(st.top);
  34.     return 1;
  35. }
  37. bool isEmpty(SqStack st)
  38. {
  39.  //write your own codes
  40.  if(st.top==-1)
  41.     return true;
  42.  return false;
  43. }
  45. //输出栈中的元素
  46. int print_S(SqStack st)
  47. {
  48.     if( isEmpty(st) )
  49.     {
  50.         printf("Stack is Empty");
  51.         return 0;
  52.     }
  53.     int iPointer = st.top;
  54.     while(iPointer != -1)
  55.     {
  56.         printf("%d ",st.data[iPointer]);
  57.         --iPointer;
  58.     }
  59.     printf("\n");
  60.     return 1;
  61. }
  63. int main()
  64. {
  65.     int n , i , e;
  66.     SqStack S;
  67.     initStack(S);
  68.     scanf("%d",&n);
  69.     for(i = 0 ; i < n; ++i)
  70.     {
  71.         scanf("%d",&e);
  72.         Push(S,e);                          //要写的函数：进栈操作
  73.     }
  74.     print_S(S);
  75.     scanf("%d",&n);
  76.     for(int i = 0 ;i < n ; ++i)
  77.     {
  78.         Pop(S,e);                          //要写的函数：出栈操作
  79.         printf("%d ",e);
  80.     }
  81.     printf("\n");
  82.     print_S(S);
  83.     return 0;
  84. }

4868

cvcv

  1. #include<stdio.h>
  3. #define maxsize 10000
  5. typedef struct
  6. {
  7.     int data[maxsize];      //存放栈中元素
  8.     int top;                //栈顶指针
  9. }SqStack;
  11. //初始化栈
  12. void initStack(SqStack &st)
  13. {
  14.     st.top = -1;
  15. }
  17. //进栈算法
  18. int Push(SqStack &st, int x)
  19. {
  20.     if(st.top == maxsize - 1)
  21.         return 0;
  22.     ++(st.top);  //先移动指针再进栈
  23.     st.data[st.top] = x;
  24.     return 1;
  25. }
  27. bool isEmpty(SqStack st)
  28. {
  29.  //write your own codes
  30.  if(st.top==-1)
  31.     return true;
  32.  return false;
  33. }
  35. //输出栈中的元素
  36. int print_S(SqStack st)
  37. {
  38.     if( isEmpty(st) )
  39.     {
  40.         printf("Stack is Empty");
  41.         return 0;
  42.     }
  43.     int iPointer = st.top;
  44.     while(iPointer != -1)
  45.     {
  46.         printf("%d ",st.data[iPointer]);
  47.         --iPointer;
  48.     }
  49.     printf("\n");
  50.     return 1;
  51. }
  53. int main()
  54. {
  55.     int n , i , e;
  56.     SqStack S;
  57.     initStack(S);
  58.     scanf("%d",&n);
  59.     for(i = 0 ; i < n; ++i)
  60.     {
  61.         scanf("%d",&e);
  62.         Push(S,e);
  63.     }
  64.     print_S(S);    //需要写出的函数：打印栈
  65.     return 0;
  66. }

链式栈

4225

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<malloc.h>
  5. #define TRUE 1
  6. #define FALSE 0
  7. #define s top
  9. typedef int Status;
  11. typedef struct Node
  12. {
  13.     char data;
  14.     struct Node *next;
  15. }Node;
  17. Node *top;
  19. const Status isEmpty()
  20. {
  21.     return (top==NULL)?TRUE:FALSE;
  22. }
  24. void Push(const char x)
  25. {
  26.     Node *n = (struct Node *)malloc(sizeof(struct Node));
  27.     n->data = x;
  28.     n->next = top;
  29.     top = n;
  30. }
  32. Status Pop(char *x)
  33. {
  34.     if (isEmpty())
  35.         return FALSE;
  36.     *x = top->data;
  37.     Node *t = top;
  38.     top = top->next;
  39.     free(t);
  40.     return TRUE;
  41. }
  43. Status getTop(char *x)
  44. {
  45.     if (isEmpty())
  46.         return FALSE;
  47.     *x = top->data;
  48.     return TRUE;
  49. }
  51. Status match(char f[]) {
  52.     char* p = f;
  53.     char ch;
  54.     while (*p != '\0') {
  55.         if (*p == 39) {//单引号
  56.             ++p;
  57.             while (*p != 39)//小括号
  58.                 ++p;
  59.             ++p;
  60.         }
  61.         else if (*p == 34) {//双引号
  62.             ++p;
  63.             while (*p != 34)//小括号
  64.                 ++p;
  65.             ++p;
  66.         }
  67.         else {
  68.             switch (*p) {
  69.             case '(':
  70.             case '{':
  71.             case '[':Push(*p); break;
  72.             case ')':getTop(&ch);
  73.                 if (ch == '(')
  74.                     Pop(&ch);
  75.                 else return 0;
  76.                 break;
  77.             case '}':getTop(&ch);
  78.                 if (ch == '{')
  79.                     Pop(&ch);
  80.                 else return 0;
  81.                 break;
  82.             case ']':getTop(&ch);
  83.                 if (ch == '[')
  84.                     Pop(&ch);
  85.                 else return 0;
  86.             }
  87.             ++p;
  88.         }
  89.     }
  90.     if (isEmpty())//如果栈为空，表示括号都已经匹配
  91.         return 1;
  92.     else
  93.         return 0;
  94. }
  96. int main()
  97. {
  98.     top = NULL;
  99.     char str[100];
  100.     gets(str);
  101.     if (match(str))
  102.         printf("YES\n");
  103.     else
  104.         printf("NO\n");
  105.     return 0;
  106. }

栈与递归

4227

  1. #include<stdio.h>
  3. // write your code here
  4. int sum(int a[],int x)
  5. {
  6.     if(x<1)    return 0;
  7.     return a[x-1]+sum(a,--x);
  8. }
  10. int main()
  11. {
  12.     int a[6],i;
  13.     for (i=0;i<6;i++)
  14.         scanf("%d", a+i);
  15.     printf("%d\n", sum(a, 6));
  16.     return 0;
  17. }

4226

  1. #include<stdio.h>
  3. // write your code here
  4. int max(int a[], int x)
  5. {
  6.     if(x<1) return -1;
  7.     int tmp=max(a, x-1);
  8.     return a[x-1]>tmp?a[x-1]:tmp;
  9. }
  11. int main()
  12. {
  13.     int a[6],i;
  14.     for (i=0;i<6;i++)
  15.         scanf("%d", a+i);
  16.     printf("%d\n", max(a, 6));
  17.     return 0;
  18. }

4228

  1. #include <stdio.h>
  3. // write your code here
  4. float average(float a[],int n,int y)
  5. {
  6.     if (n == 1)
  7.         return a[0];
  8.     else
  9.         return ((n - 1) * average(a, n - 1, y) + a[n - 1]) / n;
  10. }
  12. int main()
  13. {
  14.     float a[6];
  15.     int i;
  16.     for (i=0;i<6;i++)
  17.         scanf("%f", a+i);
  18.     printf("%.2f\n", average(a, 6, 6));
  19.     return 0;
  20. }

队列

4236

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<malloc.h>
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  10. typedef struct Node {
  11.         int data;
  12.         struct Node *next;
  13. }Node, *pNode;
  15. pNode p;
  17. void InitQueue()
  18. {
  19.     p = (struct Node *)malloc(sizeof(struct Node));
  20.     p->next = p;
  21. }
  23. void EnQueue(const int x)
  24. {
  25.     // write your code here
  26.     Node *s;
  27.     s = (Node *)malloc(sizeof(Node));
  28.     s->data = x;
  29.     if (p == NULL)
  30.     {
  31.         p = s;
  32.         p->next = p;
  33.     }
  34.     else
  35.     {
  36.         s->next = p->next; //将s作为*p之后的结点
  37.         p->next = s;
  38.         p = s; //*p指向*s
  39.     }
  40. }
  42. const Status isEmpty()
  43. {
  44.     // write your code here
  46. }
  48. Status DeQueue(int *x)
  49. {
  50.     // write your code here
  51.     Node *s;
  52.     if (p == NULL)
  53.         return 0;
  54.     if (p->next == NULL)
  55.     { //只有一个结点的情况
  56.         *x = p->data;
  57.         free(p);
  58.         p = NULL;
  59.     }
  60.     else
  61.     { //将*p之后结点的data域值赋给x，然后删除之
  62.         s = p->next;
  63.         *x = s->data;
  64.         p->next = s->next;
  65.         free(s);
  66.     }
  67.     return 1;
  68. }
  70. const void Print()
  71. {
  72.     Node *t = p->next;
  73.     while (t->next!=p->next) {
  74.         printf("%d ", t->next->data);
  75.         t = t->next;
  76.     }
  77.     printf("\n");
  78. }
  80. int main()
  81. {
  82.     InitQueue();
  83.     int x;
  84.     EnQueue(1);
  85.     EnQueue(2);
  86.     EnQueue(3);
  87.     DeQueue(&x);
  88.     EnQueue(4);
  89.     DeQueue(&x);
  90.     DeQueue(&x);
  91.     DeQueue(&x);
  92.     EnQueue(5);
  93.     Print();
  94.     return 0;
  95. }

4915

  1. #include<iostream>
  2. using namespace std;
  4. struct Node {
  5.     int data;
  6.     Node *next;
  7. };
  9. class LinkList {
  10. private:
  11.     Node *first;
  12. public:
  13.     LinkList();
  14.     void Insert(const int &x);
  15.     Node *First();
  16.     int Length(Node *n);
  17. };
  19. LinkList::LinkList()
  20. {
  21.     first = new Node();
  22.     first->next = NULL;
  23. }
  25. void LinkList::Insert(const int &x)
  26. {
  27.     Node *t = first;
  28.     while (t->next!=NULL)
  29.         t = t->next;
  30.     Node *n = new Node();
  31.     n->data = x;
  32.     n->next = t->next;
  33.     t->next = n;
  34. }
  36. Node *LinkList::First()
  37. {
  38.     return first;
  39. }
  41. //write your code here
  42. int LinkList::Length(Node *n)
  43. {
  44.     if(n==NULL) return -1;
  45.     return 1+Length(n->next);
  46. }
  48. int main()
  49. {
  50.     LinkList l;
  51.     int x;
  52.     cin >> x;
  53.     while (x!=-1) {
  54.         l.Insert(x);
  55.         cin >> x;
  56.     }
  57.     //write your code here
  58.     printf("%d\n", l.Length(l.First()));
  59.     return 0;
  60. }

4872

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. typedef struct QNode
  5. {
  6.     int data;
  7.     struct QNode *next;
  8. }QNode,*QueuePtr;
  10. typedef struct{
  11.     QueuePtr front;
  12.     QueuePtr rear;
  13. }LinkQueue;
  16. int InitQueue(LinkQueue &Q)
  17. {
  18.     Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
  19.     if( !Q.front) exit(0);
  20.     Q.front->next = NULL;
  21.     return 1;
  22. }
  24. int EnQueue(LinkQueue &Q, int e)
  25. {
  26.     QNode* p=(QueuePtr)malloc(sizeof(QNode));
  27.     //printf("--\n");
  28.     p->data=e;
  29.     p->next=NULL;
  30.     Q.rear->next=p;
  31.     Q.rear=p;
  32.     return 1;
  33. }
  35. int DeQueue(LinkQueue &Q,int &e)
  36. {
  37.     QNode *p=Q.front->next;
  38.     Q.front->next=p->next;
  39.     if(p==Q.rear)   Q.rear==Q.front;
  40.     e=p->data;
  41.     free(p);
  42.     return 1;
  43. }
  44. int main()
  45. {
  46.     int m,n;
  47.     int i,e;
  48.     LinkQueue Q;
  49.     InitQueue(Q);
  50.     scanf("%d",&n);
  51.     for(i = 0 ; i < n ; ++i)
  52.     {
  53.         scanf("%d",&e);
  54.         EnQueue(Q,e);
  55.     }
  56.     scanf("%d",&m);
  57.     for(i = 0 ; i < m ; ++i)
  58.     {
  59.         DeQueue(Q,e);
  60.         printf("%d ",e);
  61.     }
  62.     printf("\n");
  63.     return 0;
  64. }

4235

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<malloc.h>
  5. #define TRUE 1
  6. #define FALSE 0
  8. typedef int Status;
  10. int *q;
  11. int maxSize;
  12. int front;
  13. int rear;
  14. int tag;
  16. const Status isFull()
  17. {
  18.     // write your code here
  19.     if(rear%maxSize==front&&tag==1)
  20.         return 1;
  21.     return 0;
  22. }
  24. const Status isEmpty()
  25. {
  26.     // write your code here
  27.     if(rear==front&&tag==0)
  28.         return 1;
  29.     return 0;
  30. }
  32. void InitStack(int sz)
  33. {
  34.     maxSize = sz;
  35.     q = (int *)malloc(maxSize*sizeof(int));
  36.     front = 0;
  37.     rear = 0;
  38.     tag = 0;
  39. }
  41. void output()
  42. {
  43.     int i;
  44.     for (i=0;i<maxSize;i++)
  45.         printf("%d ", q[i]);
  46. }
  48. Status EnQueue(int x)
  49. {
  50.     // write your code here
  51.     if(isFull())    return 0;
  52.     q[rear]=x;
  53.     rear=(rear+1)%maxSize;
  54.     if(rear==front) tag=1;
  55.     return 1;
  56. }
  58. Status DeQueue(int x)
  59. {
  60.     // write your code here
  61.     if(isEmpty())   return 0;
  62.     x=q[front];
  63.     front=(front+1)%maxSize;
  64.     if(rear==front) tag==0;
  65.     return 1;
  66. }
  68. int main()
  69. {
  70.     InitStack(4);
  71.     int m;
  72.     EnQueue(1);
  73.     DeQueue(m);
  74.     DeQueue(m);
  75.     EnQueue(2);
  76.     EnQueue(0);
  77.     EnQueue(4);
  78.     EnQueue(5);
  79.     DeQueue(m);
  80.     DeQueue(m);
  81.     EnQueue(6);
  82.     output();
  83.     return 0;
  84. }