[자료구조] Stacks
자료구조
Introduction
스택
스택은 항목이 한쪽 끝(최상부)에서만 삽입 및 제거가 될 수 있도록 정렬된 항목을 데이터 구조다. 따라서 Last-In First-Out(LIFO) 후입선출의 특징이 있다.
STL Stack Class Template
(c++ STL설명 : https://www.geeksforgeeks.org/the-c-standard-template-library-stl/)
- pop() : 1개 빼기 파라미터가 없다.
- push(const Item& entry) : insert
- empty() : 비우기
- size() : 크기
- top() : top 파라미터 출력
- etc. : 등등
Stack Errors :
- stack overflow : full stack에서 아이템을 푸시 하려고 시도한 결과
- stack underflow : 빈 스택에서 아이템을 pop하려고 시도한 결과
Stack Applications
Balanced Parentheses(밸런스 있는 괄호)
스택을 사용해 표현식을 검사하여 다음과 같이 괄호가 일치하는지 확인하는 함수를 작성할 수 있다.
(( X + Y * ( Z + 7 )) * (A + B )) balanced.
(( X + Y * ( Z + 7 ) * ( A + B )) not balanced.
Checking Balanced Parentheses
1. 표현식의 다음 문자 c에서 읽는다.
2. If c가 괄호가 아닌 경우 1로 이동.
3. Else If c가 왼쪽 괄호일 경우, c를 스택 위에 밀어 넣는다.
4. Else If c가 오른쪽 괄호일 경우 해당하는 왼쪽 괄호를 스택에서 팝 한다.
5. 식의 끝에 도달할 때까지 동일한 과정을 반복한다.
// FILE: parens.cpp
// 스택을 위한 작은 데모 프로그램입니다.
#include <cstdlib> // Provides EXIT_SUCCESS
#include <iostream> // Provides cin, cout
#include <stack> // Provides stack
#include <string> // Provides string
using namespace std;
// PROTOTYPE for a function used by this demonstration program
bool is_balanced(const string& expression);
// Postcondition: true return은 지정된 식의 괄호가 균형을 이루고 있음을 나타낸다.
// 그렇지 않으면 return이 false다.
int main( )
{
string user_input;
cout << "Type a string with some parentheses:\n";
getline(cin, user_input);
if (is_balanced(user_input))
cout << "Those parentheses are balanced.\n";
else
cout << "Those parentheses are not balanced.\n";
cout << "That ends this balancing act.\n";
return EXIT_SUCCESS;
}
bool is_balanced(const string& expression)
// Library facilities used: stack, string
{
// Meaningful names for constants
const char LEFT_PARENTHESIS = '(';
const char RIGHT_PARENTHESIS = ')';
stack<char> store; // Stack to store the left parentheses as they occur
string::size_type i; // An index into the string
char next; // The next character from the string
bool failed = false; // Becomes true if a needed parenthesis is not found
for (i = 0; !failed && (i < expression.length( )); ++i)
{
next = expression[i];
if (next == LEFT_PARENTHESIS)
store.push(next);
else if ((next == RIGHT_PARENTHESIS) && (!store.empty( )))
store.pop( ); // Pops the corresponding left parenthesis.
else if ((next == RIGHT_PARENTHESIS) && (store.empty( )))
failed = true;
}
return (store.empty( ) && !failed);
}
Array 구현
Stack template class
- Two member variables
1. data[CAPACITY] array
2. used number of items
Constructor, Push, Pop, Top, Empty, Size를 정의한다.
다음 코드들은 위 내용에 대한 헤더파일, 템플릿 파일, cpp파일이다.
헤더파일
// FILE: stack1.h (part of the namespace main_savitch_7A)
// TEMPLATE CLASS PROVIDED: stack<Item>
//
// TEMPLATE PARAMETER, TYPEDEFS and MEMBER CONSTANTS for the stack<Item> class:
// The template parameter, Item, is the data type of the items in the stack,
// also defined as stack<Item>::value_type. It may be any of the C++ built-in
// types (int, char, etc.), or a class with a default constructor, a copy
// constructor, and an assignment operator. The definition
// stack<Item>::size_type is the data type of any variable that keeps track of
// how many items are in a stack. The static const CAPACITY is the
// maximum capacity of a stack for this first stack implementation.
// NOTE:
// Many compilers require the use of the new keyword typename before using
// the expressions stack<Item>::value_type and stack<Item>::size_type.
// Otherwise the compiler doesn't have enough information to realize that it
// is the name of a data type.
//
// CONSTRUCTOR for the stack<Item> template class:
// stack( )
// Postcondition: The stack has been initialized as an empty stack.
//
// MODIFICATION MEMBER FUNCTIONS for the stack<Item> class:
// void push(const Item& entry)
// Precondition: size( ) < CAPACITY.
// Postcondition: A new copy of entry has been pushed onto the stack.
//
// void pop( )
// Precondition: size( ) > 0.
// Postcondition: The top item of the stack has been removed.
//
// CONSTANT MEMBER FUNCTIONS for the stack<Item> class:
// bool empty( ) const
// Postcondition: Return value is true if the stack is empty.
//
// size_type size( ) const
// Postcondition: Return value is the total number of items in the stack.
//
// Item top( ) const
// Precondition: size( ) > 0.
// Postcondition: The return value is the top item of the stack (but the
// stack is unchanged. This differs slightly from the STL stack (where
// the top function returns a reference to the item on top of the stack).
//
// VALUE SEMANTICS for the stack<Item> class:
// Assignments and the copy constructor may be used with stack<Item>
// objects.
#ifndef MAIN_SAVITCH_STACK1_H
#define MAIN_SAVITCH_STACK1_H
#include <cstdlib> // Provides size_t
namespace main_savitch_7A
{
template <class Item>
class stack
{
public:
// TYPEDEFS AND MEMBER CONSTANT -- See Appendix E if this fails to compile.
typedef std::size_t size_type;
typedef Item value_type;
static const size_type CAPACITY = 30;
// CONSTRUCTOR
stack( ) { used = 0; }
// MODIFICATION MEMBER FUNCTIONS
void push(const Item& entry);
void pop( );
// CONSTANT MEMBER FUNCTIONS
bool empty( ) const { return (used == 0); }
size_type size( ) const { return used; }
Item top( ) const;
private:
Item data[CAPACITY]; // Partially filled array
size_type used; // How much of array is being used
};
}
#include "stack1.template" // Include the implementation.
#endif
template 파일
// FILE: stack1.template
// TEMPLATE CLASS IMPLEMENTED: stack<Item> (see stack1.h for documentation)
// This file is included in the header file, and not compiled separately.
// INVARIANT for the stack class:
// 1. The number of items in the stack is in the member variable used.
// 2. The actual items of the stack are stored in a partially-filled
// array data[0]..data[used-1]. The stack elements appear from the
// bottom (at data[0]) to the top (at data[used-1]).
#include <cassert> // Provides assert
namespace main_savitch_7A
{
template <class Item>
const typename stack<Item>::size_type stack<Item>::CAPACITY;
template <class Item>
void stack<Item>::push(const Item& entry)
// Library facilities used: cassert
{
assert(size( ) < CAPACITY);
data[used] = entry;
++used;
}
template <class Item>
void stack<Item>::pop( )
// Library facilities used: cassert
{
assert(!empty( ));
--used;
}
template <class Item>
Item stack<Item>::top( ) const
// Library facilities used: cassert
{
assert(!empty( ));
return data[used-1];
}
}
다음 코드는 실습해보는 main.cpp파일이다.
#include <cstdlib> // Provides EXIT_SUCCESS
#include <iostream> // Provides cin, cout
#include "stack1.h" // Provides stack
#include <string> // Provides string
using namespace std;
using namespace main_savitch_7A;
bool is_balanced(const string& expression);
int main()
{
string user_input;
cout << "Type a string with some parentheses:\n";
getline(cin, user_input);
if (is_balanced(user_input))
cout << "Those parentheses are balanced.\n";
else
cout << "Those parentheses are not balanced.\n";
cout << "That ends this balancing act.\n";
return EXIT_SUCCESS;
}
bool is_balanced(const string& expression)
{
const char LEFT_PARENTHESIS = '(';
const char RIGHT_PARENTHESIS = ')';
stack<char> store; // Stack to store the left parentheses as they occur
string::size_type i; // An index into the string
char next; // The next character from the string
bool failed = false; // Becomes true if a needed parenthesis is not found
for (i = 0; !failed && (i < expression.length()); ++i)
{
next = expression[i];
if (next == LEFT_PARENTHESIS)
store.push(next);
else if ((next == RIGHT_PARENTHESIS) && (!store.empty()))
store.pop(); // Pops the corresponding left parenthesis.
else if ((next == RIGHT_PARENTHESIS) && (store.empty()))
failed = true;
}
return (store.empty() && !failed);
}
링크드리스트 구현
- 링크드리스트 구현을 사용하면 실행 중에 스택의 용량의 늘어나거나 줄어들 수 있다.
- 리스트의 헤드는 스택의 맨 위가 될 수 있다.
- 리스트의 헤드에 아이템을 푸시 할 수 있다.
- 리스트의 헤드에서 아이템을 팝 할 수 있다.
다음 코드는 위 내용에 대한 c++ 코드다.
Class Definition
template <class Item>
class stack
{
private:
node<Item> *top_ptr ;
…
}
Copy Constructor
template <class Item>
stack<Item>::stack(const stack<Item>& source)
{
node<Item>* tail_ptr ;
list_copy(source.top_ptr, top_ptr, tail_ptr ) ;
}
Push
template <class Item>
void stack<Item>::push(const Item& entry)
{
list_head_insert(top_ptr, entry ) ;
}
Pop
template <class Item>
void stack<Item>::pop( )
{
assert ( !empty() ) ; //비어있지 않음을 확인
list_head_remove(top_ptr) ;
}
Empty
template <class Item>
bool stack<Item>::empty( ) const
{
return top_ptr == NULL ; //head가 null이면 비어있는 stack이다.
}
Top
template <class Item>
Item stack<Item>::top( ) const
{
assert ( !empty() ) ; //비어있지 않음을 확인
return top_ptr->data() ; // top의 데이터 리턴
}
댓글남기기