자료구조 스택(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. 스택의 활용

- 괄호검사나 수식계산에 사용된다.