데이터 구조 - 스 택 의 배열 실현

3144 단어 데이터 구조
스 택 은 먼저 들 어간 후에 나 오 는 데이터 구조 로 컴퓨터 표현 식 에서 값 을 구 할 때 자주 사용 하 는 데이터 구조 입 니 다.구체 적 으로 제시: 미래 문 제 를 판단 해 야 판단 할 때 현재 의 데 이 터 를 저장 해 야 한다. 스 택 은 바로 이러한 데이터 구조 로 현재 데 이 터 를 저장 해 야 할 때 먼저 스 택 에 누 르 고 사용 할 때 팝 업 된다.스 택 도 일정한 제약 을 가 진 선형 표 로 볼 수 있 고 삽입 과 삭 제 는 모두 같은 위치 (스 택 꼭대기) 에 작용 한다.
1. 스 택 에 대한 정의:
1. 스 택 에 저 장 된 데이터 형식;
2. 창고 지붕;
3. 창고 의 최대 용량;
C 언어 구현:
struct SNode{     ElementType *Data;        /* 스 택 데이터 */    Position Top;            /* 창고 꼭대기 포인터 */    int MAXSIZE;            /* 창고 의 최대 용량 */  };
2. 빈 창고 만 들 기
빈 스 택 을 만 들 려 면 먼저 스 택 의 크기 를 정 한 다음 스 택 지붕 을 초기 화 해 야 합 니 다.
Stack Create_Stack(int MaxSize) {     Stack S = (Stack)malloc(sizeof(struct SNode));     S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType));     S->Top = -1;        /* Top = - 1 빈 창고 */    S->MAXSIZE = MaxSize;  }
창고
스 택 을 쌓 는 것 은 실제 적 으로 스 택 꼭대기 에 데 이 터 를 삽입 하고 스 택 꼭대기 에 1 을 추가 하 는 것 입 니 다. 스 택 을 쌓 기 전에 스 택 이 꽉 찼 는 지 여 부 를 판단 해 야 합 니 다.
Bool Push(Stack S, ElementType X) {     if( ISFull(S) ){         printf ("창고 가득");        return false;     }     else{         S->Data[++(S->Top)]    = X;         return true;     }     } 
창고 에서 나오다
스 택 을 나 가 는 것 은 실제 적 으로 스 택 의 데 이 터 를 삭제 하 는 것 입 니 다. 스 택 의 지붕 은 동시에 1 을 줄 입 니 다. 스 택 을 나 가기 전에 스 택 의 빈 공간 을 판단 해 야 합 니 다.
ElementType Pop(Stack S) {     if( ISEmpty(S) ){         printf ("창고 비 움");        exit(false);     }     else{         return S->Data[(S->Top)--];     }     }  
결론: 사실 스 택 도 특수 한 선형 표 로 많이 사용 하면 익숙 합 니 다. 다음 에 인 스 턴 스 를 드 리 겠 습 니 다.

#include 
#include 

#define false 0
#define true 1 

typedef int ElementType;
typedef int Position;
typedef int Bool;

typedef struct SNode *Stack;
struct SNode{
	ElementType *Data;		/*      */
	Position Top;			/*      */
	int MAXSIZE;			/*        */  
};

Stack Create_Stack(int MaxSize);
Bool ISEmpty(Stack S);
Bool ISFull(Stack S);
Bool Push(Stack S, ElementType X);
ElementType Pop(Stack S);

int main()
{
	Stack S;
	int MaxSize;
	int i;
	scanf("%d",&MaxSize);
	S = Create_Stack(MaxSize);
	
	for( i = 1; !ISFull(S) ; i++)
		Push(S,i);
	for( ;!ISEmpty(S); ) 
		printf("%d
",Pop(S)); return 0; } /* ** */ Stack Create_Stack(int MaxSize) { Stack S = (Stack)malloc(sizeof(struct SNode)); S->Data = (ElementType *)malloc(MaxSize * sizeof(ElementType)); S->Top = -1; /* Top =-1 */ S->MAXSIZE = MaxSize; } /* ** */ Bool ISEmpty(Stack S) { return S->Top == -1 ; } /* ** */ Bool ISFull(Stack S) { return S->Top == S->MAXSIZE - 1; } /* ** */ Bool Push(Stack S, ElementType X) { if( ISFull(S) ){ printf("
"); return false; } else{ S->Data[++(S->Top)] = X; return true; } } /* ** */ ElementType Pop(Stack S) { if( ISEmpty(S) ){ printf("
"); exit(false); } else{ return S->Data[(S->Top)--]; } }

 

좋은 웹페이지 즐겨찾기