데이터 구조 - 스 택 (배열 설명)

스 택 은 자주 사용 하 는 데이터 구조 이다.스 택 이라는 데이터 구 조 는 배열 이나 링크 두 가지 방식 으로 묘사 할 수 있 습 니 다. 스 택 의 특징 때문에 배열 은 스 택 의 자주 사용 되 는 표현 형식 입 니 다. 본 고 는 주로 스 택 의 배열 형식 을 소개 하고 디지털 간 전환 의 예 를 통 해 스 택 의 구축, 스 택 과 스 택 등 기본 적 인 조작 을 소개 합 니 다.
1. 스 택 은 선형 표 의 삽입 과 삭제 작업 을 같은 끝 에 놓 고 진행 하면 스 택 데이터 구 조 를 얻 을 수 있 습 니 다. 이것 은 후진 선 출 (last in first out) 의 데이터 구조 입 니 다.스 택 은 특수 한 선형 표 로 삽입 (스 택/스 택) 과 삭제 (스 택/스 택) 작업 은 모두 표 의 같은 끝 에서 진행 된다.이 한쪽 은 창고 지붕 이 라 고 하고, 다른 한쪽 은 창고 바닥 이 라 고 한다.프린터 트 레이 의 인쇄 지 사용 상황 은 스 택 작업 으로 볼 수 있다.스 택 의 배열 설명 에 대한 추상 적 인 데이터 형식 은 다음 과 같 습 니 다.

class Stack
{  public:
    Stack(int size);    //    ，      ，    
    char pop();         //  
void push(char e);  //  ，       ，        
void empty()        //      
    char* stack;        //      ，      
private:
    int size;         //    
    int top;          //    
};

배열 을 이용 하여 스 택 에 대해 설명 합 니 다. 이런 추상 적 인 데이터 유형 은 기본 적 인 스 택 초기 화, 스 택 입, 스 택 출 등 작업 과 스 택 지붕, 스 택 의 크기 표 시 를 포함 합 니 다.데이터 보호 로 인해 스 택 과 스 택 의 크기 를 private 변수 로 정의 합 니 다. 이 변수 가 필요 하 다 면 Public 함수 gettop () 함 수 를 추가 하여 스 택 으로 돌아 갈 수 있 습 니 다.
2. 인 스 턴 스 스 택 의 작업 에서 가장 중요 한 것 은 스 택 에 들 어가 고 스 택 을 나 가 는 작업 입 니 다.다음은 실례 를 들 어 설명 하 겠 습 니 다.1. 이것 은 간단 한 스 택 의 설립, 입 스 택 과 출 스 택 의 예 입 니 다.이 예 를 통 해 스 택 의 배열 설명 형식 을 익 힙 니 다./스 택 의 배열 설명, (스 택 에 들 어가 고 스 택 을 나 가 며 동적 으로 스 택 의 길 이 를 증가 합 니 다)

#include<iostream>
#include<cmath>
using namespace std;
class Stack
{
public:
    Stack(int initialCapacity=10)        //    
    {
        size=initialCapacity;
        stack= new char[size];
        top=-1;
    }
    void push(char element);       //  
// char pop(char* element); //       ，       
/*char Stack::pop(char* element) { element=&stack[top--]; return *element; } */
    char pop()                         //            
    {
        if(top==-1)
        {
            cout<<"     ！"<<endl;
            exit(0);
        }
        return stack[top--];
    } 
    int top;                             //    
    int size;                            //    
    char* stack;                         //    
};
//        
void Stack::push(char element)
{
    if(top==size-1)
    {   
        size*=2;
        char* p=new char[size];
        for(int i=0;i<=top;i++)
            p[i]=stack[i];
        delete[] stack;
        stack=p;
    }
    stack[++top]=element;
}

int main()
{
    Stack stack; 
    for(int i=0;i<stack.size;i++)         //10     
        stack.push('a'+i);
    for( i=0;i<20;i++)   //20     ，      。    i        
        cout<<stack.pop()<<endl;
    return 0;
}

수의 진법 간 의 상호 전환//스 택 의 배열 설명, 2 진 이 10 진법 과 8 진수/스 택 이 배열 로 설명 할 때 최소 하나의 배열 변수 (포인터) 가 스 택 stack 으로 필요 합 니 다. 스 택 꼭대기 에 top 을 표시 하고 스 택 의 크기 size

가 필요 합 니 다.

#include<iostream>
#include<cmath>
using namespace std;

class Stack
{
public:
    Stack(int size)        //    ，      ，    
    {
        this->size=size;    //         size，   this    
        stack=new char[this->size]; 
        top=-1;
    }

    char pop()                    //  
    {
        if(top==-1)
        {
            cout<<"    ！"<<endl;
            exit(0);
        }
        return stack[top--];    
    }

void push(char e)      //  ，       ，        
    {
        if(top==size-1)
        {       
            size=size+10;
            char*p=new char[size];
            for(int i=0;i<size;i++)
                p[i]=stack[i];
            delete[] stack;
            stack=p;
        }
        stack[++top]=e;
    }

private:
    int size;         //    
    int top;          //    
    char* stack;      //      ，      

};

int main()
{
    Stack s(5);                     //    ，   5，      
    int o[20];                     //        

    char binary[100];              //           
    cout<<"Please input the binary number:"<<" ";
    cin>>binary;
// cout<<binary;

//**************      
    int len=strlen(binary);            //        
// cout<<len<<endl;

    for(int i=0;i<len;i++)      //       ，       0  
        s.push(binary[i]);  

    int sum=0;
    for( i=0;i<len;i++)       //     
        sum=sum+int(s.pop()-'0')*pow(2,i);
    cout<<"The decimal number is: "<<sum<<endl; 

    for( i=0;i<len;i++)   //       ，             
        s.push(binary[i]);  

//*************      
    int k=0;                   //    
    for( i=0;i<len;)                    //     
    {   
        int temp=0;
        for(int j=0;j<3&&i<len;j++)
        {
            temp=temp+int(s.pop()-'0')*pow(2,j);
            i++;
        }
        //cout<<temp<<endl;
        o[k++]=temp;        //            
    }

    cout<<"The octal number is: "; 
    for(i=k-1;i>=0;i--)     //      
        cout<<o[i];

    cout<<endl;
    return 0;
}