스택(Stack) 김진수 kjsspace@daum.net

스택 들어온 시간 순으로 데이터를 쌓아갈 때 가장 위에 즉, 가장 최근에 삽입된 위치에 있는 데이터를 삭제하거나 아니면 거기에 이어서 새로운 데이터를 삽입할 수 있도록 하는 추상 자료형 후입선출(後入先出) LIFO(Last-In, First-Out)

주요작업 Create: 새로운 스택을 만들기 Destroy: 사용되던 스택을 파기하기 Push: 스택 탑 바로 위에 새로운 데이터를 삽입하기 Pop: 스택 탑 데이터를 삭제하기 GetTop: 스택 탑 데이터를 검색하기 IsEmpty: 현재 스택이 비어있는지를 확인하기 IsFull: 현재 스택이 꽉 차 있는지를 확인하기 GetSize: 현재 스택에 들어가 있는 데이터의 개수를 알려주기

Stack (Array)

Stack(Linked List)

스택(배열이용) class StackArray }; { public: StackArray(void); StackArray(const StackArray & S); //복사생성자 ~StackArray(void); void Push(int Item); bool IsEmpty(void); bool IsFull(void); private: int Top; int Stack[100]; };

Top = S.Top; // Top 인덱스를 복사 StackArray::StackArray( )          // 생성자 함수      {  Top = 0;                             //탑 인덱스 0으로 초기화 } StackArray::StackArray(const stackClass& S)  // 복사생성자 { Top = S.Top;                          // Top 인덱스를 복사 for (int Index = 0; Index <= S.Top; ++ Index)  // 인덱스 0부터 S.Top까지      Stack[Index] = S.Stack[Index];    // 배열 요소 복사 StackArray::~StackArray( )            // 소멸자 함수 {                                        // 실행할 일 없음 bool StackArray::IsEmpty( )     // 빈 스택인지 확인하는 함수 return (Top = = 0);         // 탑 인덱스 0 이면 TRUE

bool StackArray::IsFull( ) // 꽉찬 스택인지 확인하는 함수 { return (Top = = 100);     // 탑 인덱스 100이면 TRUE } void StackArray:: Push(int Item) // Item 값을 스택에 삽입 Top=Top+1; Stack[Top]=Item; int StackArray:: Pop( ) return Stack[Top--]; }   

Stack Test #1 void main() #include<iostream> #include"StackArray.h" using namespace std; void main() { StackArray st; for(int i=1;i<=10;i++) st.Push(i); cout << st.Pop() << endl; }

Stack Test #2 void main() #include<iostream> #include"StackArray.h" using namespace std; void main() { StackArray st1; for(int i=1;i<=10;i++) st1.Push(i); StackArray st2(st1); cout << st2.Pop() << endl; }

스택(Linked List) class Node { public: Node(void); }; ~Node(void); int data; Node *next; };

#include "Node.h“ data = 0; } next = NULL; Node::Node(void){

class StackClass #include"Node.h" { public: StackClass(void); private: Node *head; void Push(int item); int Pop(void); bool isEmpty(void); bool isFull(void); };

#include "StackClass.h" #include <iostream> StackClass::StackClass(void){ head = new Node; } StackClass::~StackClass(void){ delete head; void StackClass::Push(int item){ Node *newNode = new Node; if(newNode!=NULL){ newNode->next = head; head->data = item; head = newNode;

int StackClass::Pop(void){ if(!isEmpty()){ Node *current = head->next; head = head->next; return current->data; } return 9999; bool StackClass::isEmpty(void){ return (head->next==NULL); bool StackClass::isFull(void){ return false;

Stack Test#3 int main() { StackClass *a = new StackClass; #include<iostream> #include"StackClass.h" using namespace std; int main() { StackClass *a = new StackClass; for(int i=1;i<=10;i++) a->Push(i); cout << a->Pop() << endl; delete a; return 0; }

Stack 사용예

“ 2 5 + 3 * 1 – “ 의 연산

후위표기법 계산 blog.daum.net/kjsspace