#include<iostream>
#include<cstdlib>

上大器晚成篇用链表达成了stack,那篇大家使用数组来积累数据,数组更便于精通,直接贴代码

用数组表示栈

//栈的数组达成

//stack包含两个元素:最顶的位置,保存数据的数组
特性:
1. pop:当元素数量为0的时候输出-1,否则输出数组最高位的值,并将数组的长度-1
2. push:首先将数组的长度伸长1,然后将值放在这个位置
public class Stack{
    private int topOfStack = 0;
    private int[] theArray =new int[1000];

    public int pop(){
         if(topOfStack == 0){
              return -1;
         }
         return theArray[topOfStack--];
    }      

     public void push(int val){
         theArray[++topOfStack] = val;
    }
}

using namespace std;
int *Array=NULL; 
int Count=0;

率先、代码实现

选料用数组表示栈内容必须先行估摸栈的最大容积。在Java中,数组意气风发旦创造,其尺寸是爱莫能助转移的,而数组织设立置过大大概会浪费多量内部存款和储蓄器,设置过小又或许会溢出。

#include <cstdio>
#include <cstdlib>
//#define _OJ_
#define stack_size 100

 

void Initial(int Size卡塔尔国; //开端化栈
void Push(int Element); //入栈 
int GetStackLenth(void卡塔尔国;//获取栈的个数 
void GetTopOfStack(void卡塔尔(قطر‎;//栈顶成分 
void Pop(void);          //出栈 
void Traverse(void);     //遍历 
void Destory(void卡塔尔;      //释放栈的内部存款和储蓄器 

图片 1图片 2

所以大家期望可以动态调解数组a[i]的抑扬顿挫,使得它既可以够保存全体因素,又未必浪费过多的上空。

typedef struct Lnode
{
    int base;
    int top;
    int *elem;
} Lnode, *stack;

int main()   ///测试 
{
int a[8]={15,65,13,81,26,34,88,55};
int Choose;
Initial(100卡塔尔;   //栈的开头化:开发 
for(int i=0;i<8;i++)
   Push(a[i]卡塔尔;  //数组的数各类入栈 
Traverse(卡塔尔(قطر‎;   //栈的遍历:从栈顶到栈尾依次输出 
cout <<endl <<“请输入你的选取:\n1.出栈 2.结束”
<<endl ;
while(1)
{
cin >>Choose ;
switch(Choose)
{
case 1:
Pop();                          break;
case 2:
                               break;
default :
cout <<“输入选项有误!” <<endl ; break ;
}
if(Choose==2) break;
}
Traverse(卡塔尔(قطر‎;   //发生变化后再次遍历,比对从前的栈
Destory(State of Qatar;    //用完就自由内部存款和储蓄器 
return 0;
}

 1 #pragma once 2 #include <iostream> 3 using namespace std; 4 template <typename T> class StackArray { 5 public: 6     StackArray(int size) { 7         this->top = -1; 8         this->maxSize = size; 9         elements = new T[size];10     }11     ~StackArray() {12         delete [] elements;13     }14     bool push;15     T pop();16     bool isEmpty();17     void print();18 19 private:20     int top = -1;21     int maxSize;22     T* elements;23 24 };25 26 template<typename T>27 bool StackArray<T>::push {28     if (top==maxSize)29     {30         return false;31     }32     elements[++top] = data;33     return true;34 }35 36 template<typename T>37 T StackArray<T>::pop() {38     if (top==-1)39     {40         exit(-1);41     }42     return elements[top--];43 }44 45 template<typename T>46 bool StackArray<T>::isEmpty() {47     return top == -1;48 }49 50 template<typename T>51 void StackArray<T>::print() {52     int loop = top;53     while (loop>=0)54     {55         cout << elements[loop] << endl;56         loop--;57     }58 }

 

stack
creat_list(stack s)
{
    s = (stack) malloc (sizeof(Lnode));
    s->elem = (int*) malloc (stack_size * sizeof(int));
    s->top = s->base = -1;
    return s;
}

void Initial(int Size)
{
Array=(int *)malloc(sizeof(int)*Size卡塔尔;  //Size是栈的容纳个数 
if(Array==NULL)
   cout <<“空间欠缺! ” <<endl ; 
}

View Code

率先,实现叁个主意将栈移动到另二个轻重差别的数组中。

int
isEmpty(stack s)
{
    if(s->top == s->pop)
        return 1;
    else
        return 0;
}

void Push(int Element)  //入栈 
{
Array[Count++]=Element; 
}

其次、测量检验运转

1 private void resize(int max) {
2         
3         Item[] temp = (Item[]) new Object[max];
4         for (int i = 0; i < N; i++) {
5             temp[i] = a[i];
6         }
7         a = temp;
8     }

void
push(stack s,int x)
{
    if(!isEmpty(s))
    s->elem[++s->top] = x;
}

int GetStackLenth(void卡塔尔国  //获得栈的个数 
{
return Count ;
}

图片 3图片 4

 

int
pop(stack s)
{
    if(!isEmpty(s))
    int e;
    e = s->elem[s->top–];
    return e;
}

void GetTopOfStack(void卡塔尔国 //拿到栈顶成分 
{
if(GetStackLenth()==0)
   cout <<“空栈 ” <<endl ;
else 
   cout <<“栈顶成分为 ” <<Array[Count-1] ; 
}

 1 #include "pch.h" 2 #include "StackArray.h" 3 #include <iostream> 4 using namespace std; 5  6 int main() 7 { 8     StackArray<int> stack(10); 9     stack.push(1);10     stack.push(3);11     stack.push(10);12     stack.push(40);13     stack.pop();14     stack.push(30);15 16     stack.print();17 18     std::cout << "Hello World!\n"; 19 }

 然后在push(卡塔尔(قطر‎中检查测验数组是或不是太小。若无剩余的长空,就将数组的尺寸加倍。

int main(int argc, char const *argv[]) {
#ifndef _OJ_  //ONLINE_JUDGE
    freopen(“input.txt”, “r”, stdin);
#endif

void Pop(void)  //出栈 
{
if(GetStackLenth()==0)
   cout <<“空栈!不可能开展出栈操作 ” <<endl ;
else
   Array[Count–]=0 ;
}

View Code

 

    int i, n, x;
    stack s;
    s = creat_list(s);
    scanf(“%d”, &n);
    for(i = 0;i < n; i++) {
    scanf(“%d”, &x);
    push(s,x);
     }

void Traverse(void) //遍历 
{
int Lenth=GetStackLenth();
if(Lenth==0)
   cout <<“空栈! ” <<endl ;
else 
   while(Lenth–)
       cout <<Array[Lenth] <<‘ ‘ ;
   cout <<endl <<“遍历实现 ” ;
GetTopOfStack();
}

图片 5

1  public void push(Item item) {
2 
3         if (N == a.length) resize(2*a.length);    
4         a[N++] = item;                         
5 
6     }

     for(i = 0;i < n; i++) {
     printf(“%d\n”, pop(s));
      }

void Destory(void)
{
delete Array;
}

 

    return 0;
}

 

恍如的,在pop(State of Qatar中,先删除栈顶成分,然后若是栈大小小于数组的十分之八三就将数组的长度减半(那样数COO度被扣除之后约为半满,在下一次亟待转移数组大小以前还是可以够够进行多次push(卡塔尔国和pop(State of Qatar操作卡塔尔国。

 

1  public Item pop() {
2         
3         Item item = a[--N];
4         a[N] = null;                              //避免对象游离(见标注)
5        
6         if (N > 0 && N == a.length/4) resize(a.length/2);
7         return item;
8     }

 

 

 注:在对pop(卡塔尔的兑现中,被弹出的要素的援引如故存在于数组中。它世代不会再被访问了,但Java的杂质回搜集器无法精晓那或多或少,除非该引用被覆盖。这种气象(保存一个不必要的对象的援引卡塔尔(قطر‎称为游离。

在此边,只需将被弹出的数组成分的值设置为null就可以。

 

 下边给出用数组表示栈的代码完结:

   下压(LIFOState of Qatar栈(能够动态调度数组大小的达成卡塔尔国:

 

 1 public class ResizingArrayStack<Item> implements Iterable<Item> {
 2     private Item[] a;        
 3     private int N;           
 4 
 5     public ResizingArrayStack() {
 6         a = (Item[]) new Object[2];
 7         N = 0;
 8     }
 9 
10 
11     public boolean isEmpty() {
12         return N == 0;
13     }
14 
15 
16     public int size() {
17         return N;
18     }
19 
20 
21     private void resize(int capacity) {
22         assert capacity >= N;
23         Item[] temp = (Item[]) new Object[capacity];
24         for (int i = 0; i < N; i++) {
25             temp[i] = a[i];
26         }
27         a = temp;
28     }
29 
30 
31     public void push(Item item) {
32         if (N == a.length) resize(2*a.length);    
33         a[N++] = item;                            
34     }
35 
36     public Item pop() {
37         Item item = a[--N];
38         a[N] = null;                              
39 
40         if (N > 0 && N == a.length/4) resize(a.length/2);
41         return item;
42     }
43 
44 
45     public Item peek() {
46         return a[--N];
47     }
48 
49 
50     public Iterator<Item> iterator() {
51         return new ReverseArrayIterator();
52     }
53 
54     private class ReverseArrayIterator implements Iterator<Item> {
55         private int i;
56 
57         public ReverseArrayIterator() {
58             i = N;
59         }
60 
61         public boolean hasNext() {
62             return i >= 0;
63         }
64 
65         public void remove() {
66             throw new UnsupportedOperationException();
67         }
68 
69         public Item next() {
70             return a[--i];
71         }
72     }
73 
74 }

 

 

用数组表示栈的独特之处:

      每项操作的用时都与集中大小非亲非故;

      空间须求总是不当先集合大小乘以二个常数。

用数组表示栈的劣势:

     
有些push(卡塔尔国和pop(卡塔尔(قطر‎操作会调解数组的大小:那项操作的耗费时间和栈大小成正比。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图