스택이란 무엇인가요? 자세히 설명해주세요
1. 기본 개념
컴퓨터 과학에서 스택은 테이블 끝에서만 삽입 또는 삭제 작업으로 제한되는 선형 테이블입니다.
스택은 한쪽 끝에서만 삽입하고 삭제할 수 있는 특수 선형 목록인 데이터 구조입니다. 먼저 들어온 데이터가 스택의 맨 아래로 푸시되고, 마지막 데이터가 스택의 맨 위에 놓이게 되는 원리에 따라 데이터를 저장합니다. 스택의 맨 위에서부터(마지막 데이터가 먼저 읽혀짐)
스택은 동일한 끝에서 삽입 및 삭제 작업을 허용하는 특수 선형 목록입니다. 삽입 및 삭제 작업이 가능한 쪽을 스택의 맨 위, 다른 쪽 끝을 맨 아래라고 합니다. 스택의 맨 아래는 고정되어 있으며 스택의 요소 수가 0일 때 스택의 맨 위는 부동합니다. , 이를 빈 스택이라고 합니다. 삽입을 일반적으로 PUSH라고 하고, 삭제를 팝핑(POP)이라고 합니다. 스택은 후입선출 테이블(LIFO 테이블)이라고도 합니다.
스택은 함수 호출 시 중단점을 저장하는 데 사용할 수 있습니다.
스택 모델 2. 기본 알고리즘
1. PUSH 알고리즘
① TOP ≥ n이면 오버플로 정보가 제공되고 오류 처리(푸시 전) 스택이 가득 찼는지 먼저 확인하세요. 가득 차면 오버플로됩니다. 그렇지 않으면 ②를 수행하세요.
②TOP=TOP+1을 설정하세요(스택 포인터가 1씩 증가하여 다음을 가리킵니다). 푸시 주소);
③S(TOP)=X, end (X는 새로 푸시된 요소);
2. 팝오프(POP) 알고리즘
①TOP≤ 0이면 언더플로우 정보가 제공되고 오류 처리가 수행됩니다(스택을 팝하기 전에 스택이 비어 있는지 확인하고, 비어 있으면 언더플로우하고, 비어 있지 않으면 ②를 수행).
②X=S(TOP), (스택에서 튀어나온 후의 요소는 다음에 할당됩니다.
3. 스택 구현
파스칼로 구현
1. 배열 유형
Const
m= 스택 항목 수의 상한
stack=array[1..m] stype {스택 유형}
Var
Var
p>s:stack;{stack}
top:integer; {스택의 최상위 포인터}
2. type
const
m=스택 항목 수의 상한
type
stack=record
elem: elemtp의 배열[1..m]
top:0..m; {스택 상단 포인터}
end;
Var
s:stack;{stack}
C/C++ 스택의 일부 기본 작업:
C 코드:
/*
@**2009/09 /24
기본 스택 작업
*/
#include #define MaxSize 100 using 네임스페이스 std; typedef struct { int data[MaxSize]; int top; }SqStack; void InitStack(SqStack *st) //초기화 스택 { st->top=-1; } int StackEmpty(SqStack *st) //스택이 비어 있는지 판단 { return (st->top==-1 ); } void Push(SqStack *st,int x) //요소가 스택 { if(st ->top==MaxSize-1) printf("스택 오버플로!\n"); else { st->top++; st->data[st->top]=x; } } void Pop(SqStack *st) //스택 팝 { if(st->top ==-1) printf("스택 언더플로우\n"); else st->top--; } int Gettop(SqStack *st) // 스택의 최상위 요소를 가져옵니다 { if(st->top==-1 ) { printf("스택이 비어 있습니다 \n"); 0을 반환; } else return st->data[st->top]; } void Display(SqStack *st) //다음의 요소를 인쇄합니다. 스택 { int i; printf("스택의 요소: "); for(i=st- >top;i>=0;--i) printf("%d ",st->data[i]); printf("\n"); } int main() {< /p> SqStack L; SqStack *st=&L; InitStack(st); printf("스택 비어 있음: %d\ n",StackEmpty(st)); for(int i=1;i<10;++i) Push(st,i); Display(st); printf("스택을 한 번 취소합니다\n"); Pop(st); printf("The 스택의 최상위 요소 :%d\n",Gettop(st)); Pop(st); Display(st); return 0; }