C/C++ 数据结构 - 栈

1.栈 

https://blog.csdn.net/CSDN___CSDN/article/details/82918436

1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 typedef struct link_node
  5 {
  6     int info;
  7     struct link_node *next;
  8 }N;
  9  
 10 /*创建一个空的链式栈*/
 11 N *init()
 12 {
 13     return NULL;
 14 }
 15  
 16 /*对链式栈进行初始化*/
 17 N *creat(N *top)
 18 {
 19     int x;
 20     N *p;
 21     printf("以输入-1为结束\n");
 22     scanf("%d",&x);
 23     while(x!=-1)
 24     {
 25         p=(N*)malloc(sizeof(N));
 26         p->info=x;
 27         p->next=top;
 28         top=p;
 29         scanf("%d",&x);
 30     }
 31     return top;
 32 }
 33  
 34 /*取得链式栈的栈顶结点值*/
 35 int read(N *top)
 36 {
 37     if(!top)
 38     {
 39         printf("\n该链式栈是空的\n");
 40     }
 41     return top->info;
 42 } 
 43  
 44 /*输出链式栈中各结点的值*/
 45 void display(N *top)
 46 {
 47     N *p=top;
 48     if(!top)
 49     {
 50         printf("该链式栈是空的\n");
 51     }
 52     else
 53     {
 54         while(p)
 55         {
 56             printf("%d  ",p->info);
 57             p=p->next;
 58         }
 59         printf("\n");
 60     }
 61 }
 62  
 63 /*链式栈的插入操作*/
 64 N *insert(N *top,int x)
 65 {
 66     N *q=top,*p;
 67     p=(N*)malloc(sizeof(N));
 68     p->info=x;
 69     p->next=top;
 70     top=p;
 71     return top;
 72 }
 73  
 74 /*链式栈的删除操作*/
 75 N *dele(N *top)
 76 {
 77     N *p=top;
 78     if(!top)
 79     {
 80         printf("\n该链式栈是空的，无法进行删除\n");return NULL; 
 81     }
 82     top=top->next;
 83     free(p);
 84     return top; 
 85 } 
 86 
 87 int main()
 88 {
 89     N* top = init();
 90     top = creat(top);
 91     display(top);
 92     int i = read(top);
 93     printf("%d\n",i);
 94     top = insert(top,5);
 95     display(top);
 96     top = dele(top);
 97     display(top);
 98     
 99     return 0;
100 }

2.栈c++实现

https://blog.csdn.net/zichen_ziqi/article/details/80807989

1 #include <iostream>
 2 using namespace std;
 3 
 4 template <class T>
 5 class stack{
 6 private:
 7     struct Node{
 8         T data;
 9         struct Node *next;
10     };
11     Node *head;
12     int len;
13 public:
14     stack()
15     {
16         head = NULL;
17         len = 0;
18     }
19     //创建一个栈
20     void create()
21     {
22         int x;
23         Node *p;
24         cout << "以输入-1为结束" << endl;
25         cin >> x ;
26         while(x!=-1)
27         {
28            p=new Node;
29            p->data=x;
30            p->next=head;
31            head=p;
32            cin >> x ;
33            len++;
34         }
35     }
36     //入栈
37     void push(T x)
38     {
39         Node *q = new Node;
40         q->data = x;
41         q->next = head;
42         len++;
43     }
44     //出栈
45     T top()
46     {
47         Node *p;
48         T data;
49         data = head->data;
50         p = head;
51         head = head->next;
52         delete(p);
53         len--;
54         return data;
55     }
56     //返回栈内元素的个数
57     int size()
58     {
59         return len;
60     }
61 };
62 
63 int main() 
64 {
65     stack<int> s;
66     s.create();
67     s.push(7);
68     cout << s.size() << endl;
69     cout << s.top() << endl;
70     cout << s.size() << endl;
71     
72     return 0;
73 }

3.用两个栈实现队列的功能

https://blog.csdn.net/weixin_40671425/article/details/83006485

1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 #define STACK_INIT_SIZE 10
 5  
 6 typedef struct stack{
 7     int *base;
 8     int *top;
 9     int stacksize;
10 }stack;
11  
12 int initStack(stack *s)//构造一个空栈
13 {
14     s->base = (int *)malloc(sizeof(stack)*STACK_INIT_SIZE);
15     if(s->base == NULL)
16         exit(-1);
17     s->top = s->base;
18     s->stacksize = STACK_INIT_SIZE;
19     return 1;
20 }
21  
22 void push(stack *s,int num)//压栈
23 {
24     *s->top++ = num;//注意 优先级
25 }
26  
27 int pop(stack *s)//弹栈
28 {
29     if(s->base == s->top)//空栈，无栈可弹
30         return -1;
31     return *(--s->top);
32 }
33 
34 int main()
35 {
36     stack s1,s2;
37     initStack(&s1);
38     initStack(&s2);
39     int nums[] = {1,2,3,4,5,6};
40     printf("压入栈 1\n");
41     for(int i=0;i<6;i++)
42     {
43         push(&s1,*(nums + i));
44     }
45     printf("出队的顺序为:\n");
46     for(int i=0;i<6;i++)
47     {
48         push(&s2,pop(&s1));
49     }
50     for(int i=0;i<6;i++)
51     {
52         printf("%d \t",pop(&s2));
53     }
54     return 0;
55 }

4.栈的最小的值

https://blog.csdn.net/ltc0106/article/details/105779396

 1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 #define STACK_TYPE int
  5  
  6 typedef struct STACK_NODE
  7 {
  8     STACK_TYPE value;
  9     struct STACK_NODE *next;
 10     struct STACK_NODE *next_min;
 11 }Stack_Node;
 12  
 13 //data栈
 14 static Stack_Node *stack;
 15 //只指向最小数的栈
 16 static Stack_Node *stack_min;
 17 
 18 void create_stack()
 19 {
 20     stack = NULL;
 21     stack_min = NULL;
 22 }
 23 
 24 void push(int value)
 25 {
 26     Stack_Node *new_node;
 27     new_node = (Stack_Node *)malloc(sizeof(Stack_Node));
 28     //更新data栈
 29     new_node->value = value;
 30     new_node->next = stack; //单向循环链表
 31     stack = new_node;
 32     //更新min栈
 33     if(stack_min == NULL ||value < stack_min->value )
 34     {
 35         new_node->next_min = stack_min;
 36         stack_min = new_node;
 37     }
 38     else
 39     {
 40         new_node->next_min = NULL;
 41     }
 42 }
 43 
 44 int pop()
 45 {
 46     STACK_TYPE value;
 47     Stack_Node *first_node;
 48  
 49     if(stack_min == stack)
 50         stack_min = stack->next_min;
 51         
 52     first_node = stack;
 53     stack = first_node->next;
 54     value = first_node->value;
 55  
 56     free(first_node);
 57     return value;
 58 }
 59 
 60 int top()
 61 {
 62     return stack->value;
 63 }
 64  
 65  
 66 int min()
 67 {
 68     return stack_min->value;
 69 }
 70 
 71 int main()
 72 {
 73     create_stack();
 74     push(5);
 75     printf("min:%d\n",min());
 76     push(4);
 77     printf("min:%d\n",min());
 78     push(3);
 79     printf("min:%d\n",min());
 80     push(5);
 81     printf("min:%d\n",min());
 82     push(1);
 83     printf("min:%d\n",min());
 84     push(90);
 85  
 86     printf("min:%d\n",min());
 87     printf("pop:%d\n",pop());
 88     printf("min:%d\n",min());
 89     printf("pop:%d\n",pop());
 90     printf("min:%d\n",min());
 91     printf("pop:%d\n",pop());
 92     printf("min:%d\n",min());
 93     printf("pop:%d\n",pop());
 94     printf("min:%d\n",min());
 95     printf("pop:%d\n",pop());
 96     printf("min:%d\n",min());
 97     printf("pop:%d\n",pop());
 98  
 99     return 0;
100 }