자료구조 스택(stack)
자료구조를 다시한번 보고있다.
직접 구현해보면서 정리한 내용정리해놓기.
1. 스택
- 자료의 입출력이 후입선출의 형태로 일어나는 자료구조
- 맨위에서 push(입력), pop(출력)이 일어난다.
2. ADT
객체 : 후입선출의 접근방법을 유지하는 요소들의 모음
연산 :
- push(x) : x를 스택의 맨위에 넣는다
- pop() : 스택이 비어있지 않으면 맨위 요소를 꺼낸다.
- isEmpty() : 스택이 비어있으면 true, 아니면 false를 리턴한다.
- peek() : 스택이 비어있지 않으면 맨위 요소를 꺼낸다. (pop은 꺼내면서 스택의 요소를 삭제하지만 peek은 요소를 삭제하지 않는다.)
- isFull() : 스택이 가득 차있으면 true, 아니면 false를 리턴한다.
- size() : 현재 스택의 모든 요소의 개수를 리턴한다.
- display() : 스택을 출력해준다.
3. 스택의 구현
- 배열이나 연결리스트로 스택을 구현할 수 있다.
- ADT를 바탕으로 직접 구현한 템플릿, 배열을 이용한 스택...
arrayStack.zip#include <iostream>
#include <cstdlib>
#define STACKSIZE 5
using namespace std;
template<typename T>
class arrayStack
{
int top;
T data[STACKSIZE];
public:
arrayStack() { top = -1; };
~arrayStack() {};
void push(T x);
T pop();
T peek();
bool isEmpty();
bool isFull();
int size();
void display() ;
};
template<typename T>
inline void arrayStack<T>::push(T x)
{
if (isFull())
{
cout << "stack is full" << endl;
exit(1);
}
else
{
top++;
data[top] = x;
// display();
}
}
template<typename T>
inline T arrayStack<T>::pop()
{
if (isEmpty())
{
cout << "error : stack is empty" << endl;
exit(1);
}
else
{
return data[top--];
}
}
template<typename T>
inline T arrayStack<T>::peek()
{
if (isEmpty())
{
cout << "error : stack is empty" << endl;
exit(1);
}
return data[top];
}
template<typename T>
inline bool arrayStack<T>::isEmpty()
{
if (top == -1)
return true;
return false;
}
template<typename T>
inline bool arrayStack<T>::isFull()
{
if (top + 1 == STACKSIZE)
return true;
return false;
}
template<typename T>
inline int arrayStack<T>::size()
{
return top + 1;
}
template<typename T>
inline void arrayStack<T>::display()
{
cout << "--------------------";
cout << endl;
for (int i = 0; i < top + 1; i++)
{
cout << data[i] << " ";
}
cout << endl;
cout << "--------------------" << endl;
}
4. 스택의 활용
- 괄호검사나 수식계산에 사용된다.